Advanced

Improving numerical accuracy of Grobner basis polynomial equation solvers

Byröd, Martin LU ; Josephson, Klas LU and Åström, Karl LU (2007) IEEE 11th International Conference on Computer Vision, 2007. ICCV 2007 In Proceedings of the IEEE 11th International Conference on Computer Vision p.449-456
Abstract
This paper presents techniques for improving the numerical stability of Grobner basis solvers for polynomial equations. Recently Grobner basis methods have been used succesfully to solve polynomial equations arising in global optimization e.g. three view triangulation and in many important minimal cases of structure from motion. Such methods work extremely well for problems of reasonably low degree, involving a few variables. Currently, the limiting factor in using these methods for larger and more demanding problems is numerical difficulties. In the paper we (i) show how to change basis in the quotient space R[x]/I and propose a strategy for selecting a basis which improves the conditioning of a crucial elimination step, (ii) use this... (More)
This paper presents techniques for improving the numerical stability of Grobner basis solvers for polynomial equations. Recently Grobner basis methods have been used succesfully to solve polynomial equations arising in global optimization e.g. three view triangulation and in many important minimal cases of structure from motion. Such methods work extremely well for problems of reasonably low degree, involving a few variables. Currently, the limiting factor in using these methods for larger and more demanding problems is numerical difficulties. In the paper we (i) show how to change basis in the quotient space R[x]/I and propose a strategy for selecting a basis which improves the conditioning of a crucial elimination step, (ii) use this technique to devise a Grobner basis with improved precision and (iii) show how solving for the eigenvalues instead of eigenvectors can be used to improve precision further while retaining the same speed. We study these methods on some of the latest reported uses of Grobner basis methods and demonstrate dramatically improved numerical precision using these new techniques making it possible to solve a larger class of problems than previously. (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
keywords
numerical stability, Gröbner basis, polynomial equations
in
Proceedings of the IEEE 11th International Conference on Computer Vision
pages
449 - 456
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE 11th International Conference on Computer Vision, 2007. ICCV 2007
external identifiers
  • wos:000255099300059
  • scopus:50649098598
ISSN
1550-5499
ISBN
978-1-4244-1631-8
DOI
10.1109/ICCV.2007.4408885
language
English
LU publication?
yes
id
0928ebba-b346-4146-a0bc-9a8fcc7f3b66 (old id 1407302)
date added to LUP
2008-01-08 16:29:04
date last changed
2017-06-04 04:29:52
@inproceedings{0928ebba-b346-4146-a0bc-9a8fcc7f3b66,
  abstract     = {This paper presents techniques for improving the numerical stability of Grobner basis solvers for polynomial equations. Recently Grobner basis methods have been used succesfully to solve polynomial equations arising in global optimization e.g. three view triangulation and in many important minimal cases of structure from motion. Such methods work extremely well for problems of reasonably low degree, involving a few variables. Currently, the limiting factor in using these methods for larger and more demanding problems is numerical difficulties. In the paper we (i) show how to change basis in the quotient space R[x]/I and propose a strategy for selecting a basis which improves the conditioning of a crucial elimination step, (ii) use this technique to devise a Grobner basis with improved precision and (iii) show how solving for the eigenvalues instead of eigenvectors can be used to improve precision further while retaining the same speed. We study these methods on some of the latest reported uses of Grobner basis methods and demonstrate dramatically improved numerical precision using these new techniques making it possible to solve a larger class of problems than previously.},
  author       = {Byröd, Martin and Josephson, Klas and Åström, Karl},
  booktitle    = {Proceedings of the IEEE 11th International Conference on Computer Vision},
  isbn         = {978-1-4244-1631-8},
  issn         = {1550-5499},
  keyword      = {numerical stability,Gröbner basis,polynomial equations},
  language     = {eng},
  pages        = {449--456},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Improving numerical accuracy of Grobner basis polynomial equation solvers},
  url          = {http://dx.doi.org/10.1109/ICCV.2007.4408885},
  year         = {2007},
}