Abstract

This paper presents a new fast approach to improving stabil- ity in polynomial equation solving. Gr¨obner basis techniques for equation solving have been applied successfully to several geometric computer vi- sion problems. However, in many cases these methods are plagued by numerical problems. An interesting approach to stabilising the compu- tations is to study basis selection for the quotient space In this paper, the exact matrix computations involved in the solution proce- dure are clarified and using this knowledge we propose a new fast basis selection scheme based on QR-factorization with column pivoting. We also propose an adaptive scheme for truncation of the Gr¨obner basis to further improve stability. The new basis selection strategy is studied on some of the latest reported uses of Gr¨obner basis methods in computer vision and we demonstrate a fourfold increase in speed and nearly as good over-all precision as the previous SVD-based method. Moreover, we get typically get similar or better reduction of the largest errors1 .