×

Triangular sets for solving polynomial systems: a comparative implementation of four methods. (English) Zbl 0943.12004

The problem the authors deal with is the following: Given a finite family \({\mathcal F}\) of multivariate polynomials over a field \(k\), they want to describe the affine variety \(V({\mathcal F})\) (that is, the common zeros of \({\mathcal F}\) in an algebraic closure of \(k\)). To do so, they want to obtain, from the family \({\mathcal F}\), simpler systems of polynomials, that is to say a finite family of polynomial sets related to \({\mathcal F}\) with particular properties. These sets are generically known as triangular sets and their properties may differ depending on the definition of triangular set used. The authors are interested in the different known methods for solving polynomial systems by means of this kind of sets. They present four of these methods based on the works of W. Wu [Kexue Tongbao 31, 1-5 (1986; Zbl 0602.14001)], D. Lazard [Discrete Appl. Math. 33, 147-160 (1991; Zbl 0753.13013)], M. Kalkbrener [Three contributions to elimination theory. Ph. D. Thesis, Johannes Kepler University, Linz (1992; Zbl 0773.13008)] and D. Wang [J. Symb. Comput. 16, 83-114 (1993; Zbl 0803.13016)]. They implement them with the same material and software conditions. Afterwards, they apply these four implementations to several well-known examples and compare the timings, the degrees of the outputs and the dimensions obtained.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
13P15 Solving polynomial systems; resultants
68W30 Symbolic computation and algebraic computation

Software:

ALDOR; AXIOM
PDFBibTeX XMLCite

References:

[1] P. Aubry, 1999
[2] Aubry, P.; Lazard, D.; Maza, M. Moreno: On the theories of triangular sets. J. symb. Comput. 28, 105-124 (1999) · Zbl 0943.12003
[3] Boege, W.; Gebauer, R.; Kredel, H.: Some examples for solving systems of algebraic equations by calculating Gröbner bases. J. symb. Comput. 2, 83-98 (1986) · Zbl 0602.65032
[4] Broadbery, P. A.; Dooley, S. S.; Iglio, P.; Morisson, S. C.; Steinbach, J. M.; Sutor, R. S.; Watt, S. M.: AXIOM library compiler user guide. (1994)
[5] M. Bronstein, Proceedings SYMSAC’86, Char, B. W. 1986, ACM Press, New York, 247, 249
[6] B. Buchberger, 1965
[7] Chou, S.: Mechanical geometry theorem proving. (1988) · Zbl 0661.14037
[8] S. Chou, X. Gao, Proceedings CADE-10, Kaiserslautern, Germany, 1990, Springer Verlag, 207, 220
[9] S. Chou, X. Gao, Proceedings ISAAC’92, Berkeley, CA, 1992, ACM Press, New York, 335, 341
[10] Collart, S.; Kalkbrener, M.; Mall, D.: Converting bases with the Gröbner walk. J. symb. Comput. 24, 465-470 (1997) · Zbl 0908.13020
[11] Cox, D.; Little, J.; O’shea, D.: Ideals, varieties, and algorithms. (1992)
[12] S. Czapor, K. Geddes, Proceedings SYMSAC’86, 1986, B.W. Char, Waterloo, 425, 440
[13] J. Della Dora, C. Discrescenzo, D. Duval, Proceedings EUROCAL 85, 1985, Springer-Verlag, 289, 290
[14] L. Donati, C. Traverso, Proceedings ISSAC’89, 1989, ACM Press, New York, 192, 198
[15] European Commission
[16] J.-C. Faugère, 1994
[17] Faugère, J. -C.; Gianni, P.; Lazard, D.; Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. symb. Comput. 16, 329-344 (1993) · Zbl 0805.13007
[18] Faugère, J. -C.; De Saint-Martin, F. Moreau; Rouillier, F.: Design of nonseparable bidimensional wavelets and filter banks using Gröbner bases techniques. IEEE SP trans. Signal process 46 (1998)
[19] G. Gallo, B. Mishra, Proceedings MEGA’90, Lavorno, Italy, 1990, Birkhaüser, 119, 142
[20] Gianni, P.: Properties of Gröbner basis under specializations. (1987) · Zbl 1209.13033
[21] A. Giovinni, T. Mora, G. Niesi, L. Robbiano, C. Traverso, Proceedings ISSAC’91, 1991, ACM Press, New York, 49, 54
[22] T. Gómez-Dı\acute{}az, 1994
[23] M. González-López, T. Recio, Proceedings of the 1991 SCAFI Seminar, Computer Algebra in Industry, Cohen, A. M. 1993, Wiley, New York
[24] H.-G. Gräbe, Proceedings AAECC 11, Paris, Cohen, G.Giusti, M.Mora, T. 1995, Springer Verlag, 248, 261 · Zbl 0847.00060
[25] Huynh, D.: A superexponential lower bound for Gröbner bases and church rosser commutative thue systems. Inf. control 68, 196-206 (1986) · Zbl 0612.68033
[26] Jenks, R. D.; Sutor, R. S.: AXIOM, the scientific computation system. (1992) · Zbl 0758.68010
[27] Kalkbrener, M.: Solving systems of algebraic equations by using Gröbner bases. (1987) · Zbl 1209.13003
[28] M. Kalkbrener, 1991
[29] Kalkbrener, M.: A generalized Euclidean algorithm for computing triangular representations of algebraic varieties. J. symb. Comput. 15, 143-167 (1993) · Zbl 0783.14039
[30] Kalkbrener, M.: Algorithmic properties of polynomial rings. J. symb. Comput. 26, 525-581 (1998) · Zbl 0920.68129
[31] I. Kotsireas, 1998
[32] Lazard, D.: A new method for solving algebraic systems of positive dimension. Discrete appl. Math. 33, 147-160 (1991) · Zbl 0753.13013
[33] Lazard, D.: Solving zero-dimensional algebraic systems. J. symb. Comput. 15, 117-132 (1992) · Zbl 0753.13012
[34] Z. Li, Proceedings POSSO Workshop on Software, Paris, France, 1995, Université Paris 6, 107, 122
[35] Liu, Z.: An algorithm on finding all isolated zeros of polynomial equations. MM research preprints 4, 63-76 (1989)
[36] Mayr, E.; Meyer, A.: The complexity of the word problems for commutative semigroups and ideals. Adv. math. 46, 305-329 (1982) · Zbl 0506.03007
[37] Möller, H. M.: On decomposing systems of polynomial equations with finitely many solutions. Appl. algebra eng. Commun. comput. 4, 217-230 (1993) · Zbl 0793.13013
[38] M. Moreno Maza, 1997
[39] M. Moreno Maza, Technical Report TR 4/98, 1998, NAG Ltd, Oxford, U.K
[40] M. Moreno Maza, R. Rioboo, Proceedings AAECC-11, 1995, Springer, 365, 382
[41] Ritt, J. F.: Differential equations from an algebraic standpoint. (1932) · JFM 58.0445.06
[42] Ritt, J. F.: Differential algebra. (1966)
[43] Samuel, P.; Zariski, O.: Commutative algebra. (1967) · Zbl 0121.27801
[44] Traverso, C.: Hilbert functions and the buchberger algorithm. J. symb. Comput. 22, 355-376 (1996) · Zbl 0922.13019
[45] D. M. Wang, Technical Report RISC-LINZ Series no 91-52.0, 1991, Johannes Kepler University, Linz, Austria
[46] D. M. Wang, Proceedings of the Int. Workshop on Math. Mechanisation, Beijing, China, Wu, W.-T.Cheng, M.-D. 1992, Institute of Systems Science, Academia Sinica
[47] Wang, D. M.: An elimination method based on siedenberg’s theory and its applications. Comptutational algebraic geometry, 301-328 (1993) · Zbl 0798.13013
[48] Wang, D. M.: An elimination method for polynomial systems. J. symb. Comput. 16 (1993) · Zbl 0803.13016
[49] Wang, D. M.: An implementation of the characteristic set method in Maple. Automated practical reasoning: algebraic approaches, 187-201 (1995) · Zbl 0837.68110
[50] Wang, D. M.: Solving polynomial equations: characteristic sets and triangular systems. Math. comput. Simul. 42, 339-345 (1996)
[51] Wang, D. M.: Decomposing polynomial systems into simple systems. J. symb. Comput. 25, 295-314 (1998) · Zbl 0913.12008
[52] Wu, W. T.: On zeros of algebraic equations–an application of ritt principle. Kexue tongbao 31, 1-5 (1986) · Zbl 0602.14001
[53] Wu, W. T.: A zero structure theorem for polynomial equations solving. MM research preprints 1, 2-12 (1987)
[54] Yang, L.; Zhang, J.: Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Artificial intelligence in mathematics, 147-156 (1994) · Zbl 0808.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.