Singly-Bordered Block-Diagonal Form for Minimal Problem Solvers

The Gröbner basis method for solving systems of polynomial equations became very popular in the computer vision community as it helps to find fast and numerically stable solutions to difficult problems. In this paper, we present a method that potentially significantly speeds up Gröbner basis solvers. We show that the elimination template matrices used in these solvers are usually quite sparse and that by permuting the rows and columns they can be transformed into matrices with nice block-diagonal structure known as the singly-bordered block-diagonal (SBBD) form. The diagonal blocks of the SBBD matrices constitute independent subproblems and can therefore be solved, i.e. eliminated or factored, independently.