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
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:
https://lup.lub.lu.se/record/1245447
- author
- Byröd, Martin
LU
; Josephson, Klas
LU
and Åström, Karl
LU
- organization
- publishing date
- 2008
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science
- volume
- 5305
- pages
- 130 - 143
- publisher
- Springer
- conference name
- The 10th European Conference on Computer Vision
- conference location
- Marseille, France
- conference dates
- 2008-10-12 - 2008-10-18
- external identifiers
-
- wos:000260633500010
- scopus:56749183305
- ISSN
- 1611-3349
- 0302-9743
- 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
- 2016-04-01 11:36:05
- date last changed
- 2025-01-14 11:22:25
@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 = {{1611-3349}},
language = {{eng}},
pages = {{130--143}},
publisher = {{Springer}},
title = {{A Column-Pivoting Based Strategy for Monomial Ordering in Numerical Gröbner Basis Calculations}},
url = {{https://lup.lub.lu.se/search/files/2555463/1245448.pdf}},
doi = {{10.1007/978-3-540-88693-8_10}},
volume = {{5305}},
year = {{2008}},
}