On the verification of polynomial system solvers

doi:10.1007/s11704-008-0006-y

Front. Comput. Sci.

0, Vol.

Issue () : 55-66 https://doi.org/10.1007/s11704-008-0006-y

On the verification of polynomial system solvers

CHEN Changbo, MORENO MAZA Marc, PAN Wei, XIE Yuzhen

The University of Western Ontario;

Download: PDF(160 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract 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.

Issue Date: 05 March 2008

Cite this article:

MORENO MAZA Marc,CHEN Changbo,PAN Wei, et al. On the verification of polynomial system solvers[J]. Front. Comput. Sci., 0, (): 55-66.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-008-0006-y
https://academic.hep.com.cn/fcs/EN/Y0/V/I/55

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 http://www.nag.co.uk/projects/FRISCO.html
10	Wang D Epsilon0.618http://www-calfor.lip6.fr/wang/epsilon
11	Manubens M Montes A Improving DISPGB AlgorithmUsing the Discriminant Ideal, 2006http://www.citebase.org/abstract?id=oai:arXiv.org:math/0601763
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, http://www.csd.uwo.ca/∼moreno
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

Viewed

Full text

Abstract

Cited

Shared

Discussed