A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations

Summary, in English

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.

• Author: Martin Byröd; Klas Josephson; Karl Åström
• Department/s: Mathematics (Faculty of Engineering); Mathematical Imaging Group
• Publishing year: 2008
• Language: English
• Pages: 130-143
• Publication/Series: Lecture Notes in Computer Science
• Volume: 5305
• Full text: - 257 kB; Download statistics
• Links: http://dx.doi.org/10.1007/978-3-540-88693-8_10
• Document type: Conference paper
• Publisher: Springer
• Topic: Computer Vision and Robotics (Autonomous Systems); Mathematics
• Conference name: The 10th European Conference on Computer Vision
• Conference date: 2008-10-12 - 2008-10-18
• Conference place: Marseille, France
• Status: Published
• Research group: Mathematical Imaging Group
• ISBN/ISSN/Other: ISSN: 0302-9743; ISSN: 1611-3349