×

Nonlinear reduction for solving deficient polynomial systems by continuation methods. (English) Zbl 0756.65080

Neither continuation methods, nor symbolic elimination methods can be directly applied to compute all finite solutions of polynomial systems, because the amount of computational time is mostly not proportional to the dimension of the system and to the number of finite solutions. The notion of \(S\)-polynomials is used to develop a reduction algorithm to lower the total degree of the deficient polynomial system, so that computing the solutions at infinity can be avoided. Applying the reduction algorithm before solving the system with continuation methods, yields a reliable solution method.
Reviewer: J.Verschelde

MSC:

65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
68W30 Symbolic computation and algebraic computation

Software:

minpack; Groebner
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Allogower, E., Georg, K. (1990): Numerical continuation methods; an introduction, Vol. 13. Springer Series in Computational Mathematics. Springer, Berlin Heidelberg New York
[2] Buchberger, B. (1985): Gröbner bases: An algorithmic method in polynomial ideal theory, chapter 6, Reidel. Dordrecht, pp. 184-232 · Zbl 0587.13009
[3] Burckel, R.B. (1979): An introduction to classical complex analysis, Vol. 1. Academic Press, New York London · Zbl 0434.30001
[4] Gebauer, R., Möller, H. M. (1988): On an installation of Buchberger’s algorithm. J. Symb. Comput,6, 275-286 · Zbl 0675.13013 · doi:10.1016/S0747-7171(88)80048-8
[5] Hearn, A.C. (1988): REDUCE user’s guide for the SUN Microsystems SUN 3 Workstations, Version 3.3. The RAND Corporation, Santa Monica, CA
[6] Lazard, D. (1983): Groebner bases, Gaussian elimination and resolution of systems of algebraic equations. Proceedings of the EUROCAL 83. Lecture Notes in Computer Science. Springer, Berlin Heidelberg New York · Zbl 0539.13002
[7] Li, T.-Y., Wang, X. (1991): Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant. Math. Comput.56, 693-710 · Zbl 0722.65028 · doi:10.1090/S0025-5718-1991-1066835-2
[8] Melenk, H., Möller, H. M., Neun, W. (1990): GROEBNER, a package for calculating Gröbner bases. Version January 1990. Available from data base REDUCE-netlib at rand. org
[9] Moré, J.J., Garbow, B.S., Hillstrom, K.E. (1981): Testing unconstrained optimization software. ACM Toms7, 17-41 · Zbl 0454.65049 · doi:10.1145/355934.355936
[10] Morgan, A. (1987): Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0733.65031
[11] Shafarevich, I.R. (1974): Basic Algebraic Geometry. Grundlehren der mathematischen Wissenschaften 213. Springer, Berlin Heidelberg New York
[12] Sweldens, W., Piessens, R. (1991): Efficient Quadrature Formulae for the Calculation of the Wavelet Decomposition. Report TW 159, K.U. Leuven, Dept. Computer Science · Zbl 0755.42019
[13] Verschelde, J. (1990): Oplossen van stelsels veeltermvergelijkingen met behulp van continueringsmethodes. Master’s thesis, K.U. Leuven
[14] Watson, L.T. (1989): Globally convergent homotopy methods: a tutorial. Appl. Math. Comput.31, 369-396 · Zbl 0689.65033 · doi:10.1016/0096-3003(89)90129-X
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.