Making Minimal Solvers Fast

Abstract

In this paper we propose methods for speeding up minimal solvers based on Gröbner bases and action matrix eigenvalue computations. Almost all existing Gröbner basis solvers spend most time in the eigenvalue computation. We present two methods which speed up this phase of Gröbner basis solvers: (1) a method based on a modified FGLM algorithm for transforming Gröbner bases which results in a single-variable polynomial followed by direct calculation of its roots using Sturm-sequences and, for larger problems, (2) fast calculation of the characteristic polynomial of an action matrix, again solved using Sturm-sequences. We enhanced the FGLM method by replacing time consuming polynomial division performed in standard FGLM algorithm with efficient matrix-vector multiplication and we show how this method is related to the characteristic polynomial method. Our approaches allow computing roots only in some feasible interval and in desired precision. Proposed methods can significantly speedup many existing solvers. We demonstrate them on three important minimal computer vision problems.