| Title | Improving Numerical Accuracy of Gröbner Basis Polynomial Equation Solver |
| Authors | Martin Byröd, Klas Josephson, Karl Åström |
| Full-text | Available as PDF |
| Alternative Location | http://dx.doi.org/10.1109/I..., Restricted Access |
| Publication | Proceedings of the IEEE 11th International Conference on Computer Vision |
| Year | 2007 |
| Pages | 8 |
| Document type | Conference paper |
| Conference name | IEEE 11th International Conference on Computer Vision |
| Conference Date | October 14-20 |
| Conference Location | Rio de Janeiro, Brazil |
| Status | Published |
| Quality controlled | Yes |
| Language | eng |
| Publisher | IEEE Computer Society |
| Abstract English | This paper presents techniques for improving the numerical stability of Gröbner basis solvers for polynomial equations. Recently Gröbner 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 $mathbb{R}mathbf{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 Gröbner 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 Gröbner basis methods and demonstrate dramatically improved numerical precision using these new techniques making it possible to solve a larger class of problems than previously. |
| Keywords | numerical stability, Gröbner basis, polynomial equations, |
Questions: webmaster
Last update: 2013-04-11
Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Telefon: +46 46-222 00 00 (vx)