Home  |  Centre for Mathematical Sciences  |  LTH  |  LU
Title: A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations
Authors: Byröd, Martin and Josephson, Klas and Åström, Kalle
Year: 2008
Document Type:Conference Paper
Conference: The 10th European Conference on Computer Vision
Conference location: Marseille, France
Status: In Press
Refereed: Yes
Keywords: polynomial equations
BibTeX item:BibTeX
Extra: Code available
Abstract: This paper presents a new fast approach to improving stability in polynomial equation solving. Gröbner basis techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems. An interesting approach to stabilising the computations is to study basis selection for the quotient space C[x]/I . In this paper, the exact matrix computations involved in the solution procedure 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öbner basis to further improve stability. The new basis selection strategy is studied on some of the latest reported uses of Gröbner basis methods in computer vision and we demonstrate a fourfold increase in speed and nearly as good overall precision as the previous SVD-based method. Moreover, we get typically get similar or better reduction of the largest errors.

 

Back

 

Questions: webmaster
Last updated: 2018-08-02

Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Phone: 046-222 00 00