PDF(160 KB)
On the verification of polynomial system solvers
- CHEN Changbo, MORENO MAZA Marc, PAN Wei, XIE Yuzhen
Author information
+
The University of Western Ontario;
Show less
History
+
Published |
05 Mar 2008 |
Issue Date |
05 Mar 2008 |
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.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
This is a preview of subscription content, contact
us for subscripton.
References
1. Grabmeier J Kaltofen E Weispfenning V Computer Algebra HandbookBerlinSpringer 2003
2. Aubry P Lazard D Moreno Maza M On the theories of triangular setsJournal of Symbolic Computation 1999 28(1–2)105124
3. Wang D Computingtriangular systems and regular systemsJournalof Symbolic Computation 2000 30(2)221236
4. Donati L Traverso C Experimenting the Gröbnerbasis algorithm with the ALPI systemProceedingsof ISSACNew YorkACM Press 1989 192198
5. Aubry P Moreno Maza M Triangular sets for solvingpolynomial systems: a comparative implementation of four methodsJournal of Symbolic Computation 1999 28(1–2)125154
6. Backelin J Fröberg R How we proved that there areexactly 924 cyclic 7-rootsWatt S MProceedings of ISSACNew YorkACM Press 1991 103111
7. Sit W Computationson quasi-algebraic setsProceedings of IMACSACA 1998
8. Lemaire F Moreno Maza M Xie Y The regularChains libraryKotsireasI SProceedings of Maple Conference2005 2005 355368
9. The Computational Mathematics Group. The BasicMathlibrary NAG Ltd, Oxford, UK 1998
10. Wang D Epsilon0.618
11. Manubens M Montes A Improving DISPGB AlgorithmUsing the Discriminant Ideal, 2006
12. The SymbolicData Project. 2000–2006 http://www.SymbolicData.org
13. Wang D EliminationMethodsBerlinSpringer 2001
14. Boulier F Lemaire F Moreno Maza M Well known theorems on triangular systemsProceedings of Transgressive Computing 2006SpainUniversity of Granada 2006
15. Moreno Maza M Ontriangular decompositions of algebraic varietiesTechnical Report TR 4/99, NAG Ltd, Oxford, UK, 1999
16. Eisenbud D CommutativeAlgebra. GTM 150BerlinSpringer 1994
17. Hartshorne R AlgebraicGeometryBerlinSpringer-Verlag 1997
18. O'Halloran J Schilmoeller M Gröbner bases for constructiblesetsJournal of Communications in Algebra 2002 30(11)54795483
19. Chen C Golubitsky O Lemaire F et al.Comprehensive triangular decompositionProceedings of Computer Algebra in Scientific ComputingBerlinSpringer,LNCS 2007 477073101