On the verification of polynomial system solvers
Tóm tắt
We discuss the verification of mathematical software solving polynomial systems symbolically by way of triangular decomposition. Standard verification techniques are highly resource consuming and apply only to polynomial systems which are easy to solve. We exhibit a new approach which manipulates constructible sets represented by regular systems. We provide comparative benchmarks of different verification procedures applied to four solvers on a large set of well-known polynomial systems. Our experimental results illustrate the high efficiency of our new approach. In particular, we are able to verify triangular decompositions of polynomial systems which are not easy to solve.
Tài liệu tham khảo
Grabmeier J, Kaltofen E, Weispfenning V. Computer Algebra Handbook. Berlin: Springer, 2003
Aubry P, Lazard D, Moreno Maza M. On the theories of triangular sets. Journal of Symbolic Computation, 1999, 28(1–2): 105–124
Wang D. Computing triangular systems and regular systems. Journal of Symbolic Computation, 2000, 30(2): 221–236
Donati L, Traverso C. Experimenting the Gröbner basis algorithm with the ALPI system. In: Proceedings of ISSAC. New York: ACM Press, 1989, 192–198
Aubry P, Moreno Maza M. Triangular sets for solving polynomial systems: a comparative implementation of four methods. Journal of Symbolic Computation, 1999, 28(1–2): 125–154
Backelin J, Fröberg R. How we proved that there are exactly 924 cyclic 7-roots. In: Watt S M, Proceedings of ISSAC. New York: ACM Press, 1991, 103–111
Sit W. Computations on quasi-algebraic sets. In: Proceedings of IMACS ACA, 1998
Lemaire F, Moreno Maza M, Xie Y. The regularChains library. In: Kotsireas I S, ed. Proceedings of Maple Conference 2005. 2005, 355–368
The Computational Mathematics Group. The BasicMath library NAG Ltd, Oxford, UK, 1998. http://www.nag.co.uk/projects/FRISCO.html
Wang D. Epsilon 0.618. http://www-calfor.lip6.fr/wang/epsilon
Manubens M, Montes A. Improving DISPGB Algorithm Using the Discriminant Ideal, 2006. http://www.citebase.org/abstract?id5oai:arXiv.org:math/0601763
The SymbolicData Project, 2000–2006. http://www.SymbolicData.org
Wang D. Elimination Methods. Berlin: Springer, 2001
Boulier F, Lemaire F, Moreno Maza M. Well known theorems on triangular systems. In: Proceedings of Transgressive Computing 2006. Spain: University of Granada, 2006
Moreno Maza M. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK, 1999. http://www.csd.uwo.ca/:_moreno
Eisenbud D. Commutative Algebra. GTM 150. Berlin: Springer, 1994
Hartshorne R. Algebraic Geometry. Berlin: Springer-Verlag, 1997
O’Halloran J, Schilmoeller M. Gröbner bases for constructible sets. Journal of Communications in Algebra, 2002, 30(11):5479–5483
Chen C, Golubitsky O, Lemaire F, et al. Comprehensive triangular decomposition. In: Proceedings of Computer Algebra in Scientific Computing. Berlin: Springer, LNCS, 2007, 4770:73–101