Advanced

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

Byröd, Martin LU ; Josephson, Klas LU and Åström, Karl LU (2008) The 10th European Conference on Computer Vision In Lecture Notes in Computer Science 5305. p.130-143
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science
volume
5305
pages
130 - 143
publisher
Springer
conference name
The 10th European Conference on Computer Vision
external identifiers
  • wos:000260633500010
  • scopus:56749183305
ISSN
0302-9743
1611-3349
DOI
10.1007/978-3-540-88693-8_10
language
English
LU publication?
yes
id
6b6cb59b-a2dd-403d-befe-080009e8291e (old id 1245447)
date added to LUP
2008-12-01 09:33:51
date last changed
2017-11-12 03:18:14
@inproceedings{6b6cb59b-a2dd-403d-befe-080009e8291e,
  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.},
  author       = {Byröd, Martin and Josephson, Klas and Åström, Karl},
  booktitle    = {Lecture Notes in Computer Science},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {130--143},
  publisher    = {Springer},
  title        = {A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations},
  url          = {http://dx.doi.org/10.1007/978-3-540-88693-8_10},
  volume       = {5305},
  year         = {2008},
}