Abstract
In this tutorial paper, we first discuss the motivation of doing symbolic-numeric computation, with the aim of developing efficient and certified polynomial solvers. We give a quick overview of fundamental algebraic properties, used to recover the roots of a polynomial system, when we know the multiplicative structure of its quotient algebra. Then, we describe the border basis method, justifying and illustrating the approach on several simple examples. In particular, we show its usefulness in the context of solving polynomial systems, with approximate coefficients. The main results are recalled and we prove a new result on the syzygies, naturally associated with commutation properties. Finally, we describe an algorithm and its implementation for computing such border bases.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
M.E. Alonso, E. Becker, M.F. Roy and T. Wörmann. Zeros, multiplicities and idempotents for zero-dimensional systems. In L. González-Vega and T. Recio, editors, Algorithms in Algebraic Geometry and Applications, volume 143 of Prog. in Math., pages 1–15. Birkhäuser, Basel, 1996.
W. Auzinger and H.J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Proc. Intern. Conf. on Numerical Math., volume 86 of Int. Series of Numerical Math, pages 12–30. Birkhäuser, Basel, 1988.
D. Bini. Numerical computation of polynomial zeros by means of Aberth’s method. Numerical Algorithms, 13, 1996.
B. Buchberger. Gröbner bases: An algebraic method in ideal theory. In N. K. Bose, editor, Multidimensional System Theory, pages 184–232. Reidel Publishing Co., 1985.
R.M. Corless, P.M. Gianni and B.M. Trager. A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots. In W. W. Küchlin, editor, Proc. ISSAC’ 97, pages 133–140. ACM Press, New York, 1997.
D. Cox, J. Little and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1992.
J. Demmel, J. Gilbert and X.S. Li. An asynchronous parallel supernodal algorithm for sparse gaussian elimination. SIAM J. Matrix Anal. Appl., 20(4): 915–952, 1999.
M. Elkadi and B. Mourrain. Introduction à la résolution des systèmes d’équations algébriques, 2003. Notes de cours, Univ. de Nice (310 p.).
P.A. Fuhrmann. A Polynomial Approach to Linear Algebra. Springer-Verlag, Berlin, 1996.
A. Kehrein and M. Kreuzer. A characterisation of border bases. J. Pure and Applied Algebra, 196: 251–270, 2005.
A. Kehrein, M. Kreuzer and L. Robbiano. An algebraist’s view on border bases. In A. Dickenstein and I. Emiris, editors, Solving Polynomial Equations: Foundations, Algorithms, and Applications, volume 14 of Algorithms and Computation in Mathematics, pages 169–202. Springer-Verlag, Berlin, 2005.
G. Lecerf. Computing an equidimensional decomposition of an algebraic varety bymeans of geometric resolutions. In Proc. ISSAC 2000, pages 209–216. ACM Press, New York, 2000.
F.S. Macaulay. The Algebraic Theory of Modular Systems. Cambridge Univ. Press, Cambridge, 1916.
B. Mourrain. Computing isolated polynomial roots by matrix methods. J. Symbolic Computation, Special Issue on Symbolic-Numeric Algebra for Polynomials, 26(6): 715–738, 1998.
B. Mourrain. A new criterion for normal form algorithms. In M. Fossorier, H. Imai, S. Lin, and A. Poli, editors, Proc. AAECC, volume 1719 of LNCS, pages 430–443. Springer-Verlag, Berlin, 1999.
B. Mourrain and V.Y. Pan. Multivariate polynomials, duality and structured matrices. J. Complexity, 16(1): 110–180, 2000.
B. Mourrain and P. Trébuchet. Solving projective complete intersection faster. In C. Traverso, editor, Proc. Intern. Symp. on Symbolic and Algebraic Computation, pages 231–238. ACM Press, New York, 2000.
B. Mourrain and P. Trébuchet. Algebraic methods for numerical solving. In Proc. 3rd International Workshop on Symbolic and Numeric Algorithms for Scientific Computing’ 01 (Timisoara, Romania), pages 42–57, 2002.
B. Mourrain and P. Trébuchet. Generalised normal forms and polynomial system solving. In M. Kauers, editor, Proc. Intern. Symp. on Symbolic and Algebraic Computation, pages 253–260. ACM Press, New York, 2005.
B. Mourrain and P. Trébuchet. Generalised normal forms and polynomial system solving. Technical Report 5471, INRIA Sophia-Antipolis, 2005.
J. Renegar. On the computational complexity and geometry of the first order theory of reals (I, II, III). J. Symbolic Computation, 13(3): 255–352, 1992.
F. Rouillier. Solving zero-dimensional polynomial systems throuhg Rational Univariate Representation. App. Alg. Eng. Com. Comp., 9(5): 433–461, 1999.
H.J. Stetter. Eigenproblems are at the heart of polynomial system solving. SIGSAM Bulletin, 30(4): 22–25, 1996.
H.J. Stetter. Numerical Polynomial Algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004.
P. Trébuchet. Vers une résolution stable et rapide des équations algébriques. PhD thesis, Université Pierre et Marie Curie, 2002.
W.V. Vasconcelos. Computational Methods in Commutative Algebra and Algebraic Geometry, volume 2 of Algorithms and Computation in Mathematics. Springer-Verlag, New York, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Birkhäuser Verlag Basel/Switzerland
About this paper
Cite this paper
Mourrain, B. (2007). Pythagore’s Dilemma, Symbolic-Numeric Computation, and the Border Basis Method. In: Wang, D., Zhi, L. (eds) Symbolic-Numeric Computation. Trends in Mathematics. Birkhäuser Basel. https://doi.org/10.1007/978-3-7643-7984-1_14
Download citation
DOI: https://doi.org/10.1007/978-3-7643-7984-1_14
Publisher Name: Birkhäuser Basel
Print ISBN: 978-3-7643-7983-4
Online ISBN: 978-3-7643-7984-1
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)