Numerical homotopies to compute generic points on positive dimensional algebraic sets. (English) Zbl 0982.65070
The authors consider the space of solutions to a system of polynomial equations in \(n\) variables over the complex numbers. The problem is to determine the dimension of, and a “generic” point on, each component of this space by numerical methods.
In a previous article [Numerical algebraic geometry. In: Renegar, James (ed.) et al., The mathematics of numerical analysis. 1995 AMS-SIAM summer seminar in applied mathematics, July 17–August 11, 1995, Park City, UT, USA. Providence, RI: American Mathematical Society. Lect. Appl. Math. 32, 749-763 (1996; Zbl 0856.65054)], the first author and C. Wampler developed an algorithm for solving this problem based on slicing by “generic” (i.e., “random”) linear spaces of different dimensions. Here, the authors embed the given system into a family of systems of polynomials in \(2n\) variables that depends on a large space of parameters. By choosing particular values of these parameters, they obtain \(n+1\) systems, \({\mathcal E}_0,\dots,{\mathcal E}_n\) and homotopies from \({\mathcal E}_i\) to \({\mathcal E}_{i-1}\), such that \({\mathcal E}_n\) has isolated nonsingular solutions and \({\mathcal E}_0\) is equivalent to the given system.
Their algorithm uses polynomial continuation, as developed by A. P. Morgan [Solving polynomial systems using continuation for engineering and scientific problems. Englewood Cliffs, NJ: Prentice-Hall (1987; Zbl 0733.65031)]. Examples are given to show that this new algorithm can be much more efficient than the earlier one employing slicing.
In a previous article [Numerical algebraic geometry. In: Renegar, James (ed.) et al., The mathematics of numerical analysis. 1995 AMS-SIAM summer seminar in applied mathematics, July 17–August 11, 1995, Park City, UT, USA. Providence, RI: American Mathematical Society. Lect. Appl. Math. 32, 749-763 (1996; Zbl 0856.65054)], the first author and C. Wampler developed an algorithm for solving this problem based on slicing by “generic” (i.e., “random”) linear spaces of different dimensions. Here, the authors embed the given system into a family of systems of polynomials in \(2n\) variables that depends on a large space of parameters. By choosing particular values of these parameters, they obtain \(n+1\) systems, \({\mathcal E}_0,\dots,{\mathcal E}_n\) and homotopies from \({\mathcal E}_i\) to \({\mathcal E}_{i-1}\), such that \({\mathcal E}_n\) has isolated nonsingular solutions and \({\mathcal E}_0\) is equivalent to the given system.
Their algorithm uses polynomial continuation, as developed by A. P. Morgan [Solving polynomial systems using continuation for engineering and scientific problems. Englewood Cliffs, NJ: Prentice-Hall (1987; Zbl 0733.65031)]. Examples are given to show that this new algorithm can be much more efficient than the earlier one employing slicing.
Reviewer: Robert F.Lax (Baton Rouge)
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 14Q99 | Computational aspects in algebraic geometry |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |
Keywords:
numerical algebraic geometry; homotopy continuation; generic points; numerical examples; system of polynomial equations; algorithm; polynomial continuationReferences:
| [1] | Allgower, E. L.; Georg, K., Numerical Continuation Methods, an Introduction. Numerical Continuation Methods, an Introduction, Springer Series in Comput. Math., 13 (1990), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York · Zbl 0717.65030 |
| [2] | Allgower, E. L.; Georg, K., Numerical path following, (Ciarlet, P. G.; Lions, J. L., Techniques of Scientific Computing (Part 2). Techniques of Scientific Computing (Part 2), Handbook of Numerical Analysis, 5 (1997), North-Holland: North-Holland Amsterdam), 3-203 · Zbl 0884.65001 |
| [3] | Aubry, P.; Lazard, D.; Maza, M. M., On the theories of triangular sets, J. Symbolic Comput., 28, 105-124 (1999) · Zbl 0943.12003 |
| [4] | Aubry, P.; Maza, M. M., Triangular sets for solving polynomial systems: a comparative implementation of four methods, J. Symbolic Comput., 28, 125-154 (1999) · Zbl 0943.12004 |
| [5] | Backelin, J.; Fröberg, R., How we proved that there are exactly 924 cyclic 7-roots, Proceedings of ISSAC-91 (1991), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 101-111 · Zbl 0925.13012 |
| [6] | Bank, B.; Giusti, M.; Heinz, J.; Mbakop, G. M., Polar varieties, real equation solving, and data structures: the hypersurface case, J. Complexity, 13, 5-27 (1997) · Zbl 0872.68066 |
| [7] | Bayer, D.; Mumford, D., What can be computed in algebraic geometry?, Computational Algebraic Geometry and Commutative Algebra, Cortona, 1991. Computational Algebraic Geometry and Commutative Algebra, Cortona, 1991, Sympos. Math., XXXIV (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, p. 1-48 · Zbl 0846.13017 |
| [8] | Beltrametti, M.; Sommese, A. J., The Adjunction Theory of Complex Projective Varieties. The Adjunction Theory of Complex Projective Varieties, Expositions in Mathematics, 16 (1995), de Gruyter: de Gruyter Berlin · Zbl 0845.14003 |
| [9] | Björck, G., Functions of modulus one on \(Z_p\) whose Fourier transforms have constant modulus, Proceedings of the Alfred Haar Memorial Conference, Budapest. Proceedings of the Alfred Haar Memorial Conference, Budapest, Colloquia Mathematica Societatis János Bolyai, 49 (1985), p. 193-197 · Zbl 0619.43004 |
| [10] | Björck, G., Functions of modulus one on \(Z_n\) whose Fourier transforms have constant modulus, and “cyclic \(n\)-roots”, (Byrnes, J. S.; Byrnes, J. F., Recent Advances in Fourier Analysis and its Applications. Recent Advances in Fourier Analysis and its Applications, NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 315 (1989), Kluwer: Kluwer Dordrecht/Norwell), 131-140 · Zbl 0726.43004 |
| [11] | Björck, G.; Fröberg, R., A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots, J. Symbolic Comput., 12, 329-336 (1991) · Zbl 0751.12001 |
| [12] | Björck, G.; Fröberg, R., Methods to “divide out” certain solutions from systems of algebraic equations, applied to find all cyclic 8-roots, (Gyllenberg, M.; Persson, L. E., Analysis, Algebra and Computers in Math. Research. Analysis, Algebra and Computers in Math. Research, Lecture Notes in Applied Mathematics, 564 (1994), Dekker), 57-70 · Zbl 0811.12002 |
| [13] | Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1997), Springer-Verlag: Springer-Verlag New York · Zbl 0948.68068 |
| [14] | Boege, W.; Gebauer, R.; Kredel, H., Some examples for solving systems of algebraic equations by calculating Groebner bases, J. Symbolic Comput., 2, 83-98 (1986) · Zbl 0602.65032 |
| [15] | Briskin, M.; Yomdin, Y., Critical and near-critical values in polynomial control problems. I. One-dimensional case, Israel J. Math., 78, 257-280 (1992) · Zbl 0769.93039 |
| [16] | Buchberger, B.; Winkler, F., Gröbner Bases and Applications. Gröbner Bases and Applications, London Mathematical Lecture Note Series, 251 (1998), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0883.00014 |
| [17] | Butcher, C., An application of the Runge-Kutta space, BIT, 24, 425-440 (1984) · Zbl 0555.65045 |
| [18] | Davenport, J., Technical report (1987) |
| [19] | Decker, W.; Greuel, G. M.; Pfister, G., Primary decomposition: Algorithms and comparisons, (Matzat, B. H.; Greuel, G. M.; Hib, G., Algorithmic Algebra and Number Theory. Selected Papers of a Conference held at the University of Heidelberg in October 1997 (1998), Springer-Verlag: Springer-Verlag Berlin/New York), 187-220 · Zbl 0932.13019 |
| [20] | Eisenbud, D., Commutative Algebra. With a View Toward Algebraic Geometry. Commutative Algebra. With a View Toward Algebraic Geometry, Graduate Texts in Math., 150 (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0819.13001 |
| [21] | Emiris, I. Z., Sparse Elimination and Applications in Kinematics (1994), University of CaliforniaComputer Science Division, Dept. of Electrical Engineering and Computer Science: University of CaliforniaComputer Science Division, Dept. of Electrical Engineering and Computer Science Berkeley |
| [22] | Emiris, I. Z.; Canny, J. F., Efficient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Comput., 20, 117-149 (1995) · Zbl 0843.68036 |
| [23] | Emiris, I. Z.; Mourrain, B., Matrices in elimination theory, J. Symbolic Comput., 28, 3-44 (1999) · Zbl 0943.13005 |
| [24] | Emiris, I. Z.; Verschelde, J., How to count efficiently all affine roots of a polynomial system, Discr. Appl. Math., 93, 21-32 (1999) · Zbl 1034.68715 |
| [25] | Faugère, J. C., A new efficient algorithm for computing Gröbner bases \((F_4)\), J. Pure Appl. Algebra, 139, 61-88 (1999) · Zbl 0930.68174 |
| [26] | Fischer, G., Complex Analytic Geometry. Complex Analytic Geometry, Lecture Notes in Mathematics, 538 (1976), Springer-Verlag: Springer-Verlag New York · Zbl 0343.32002 |
| [27] | Fulton, W., Intersection Theory. Intersection Theory, Ergeb. Math. Grenzgeb., (3) 2 (1984), Springer-Verlag: Springer-Verlag Berlin · Zbl 0541.14005 |
| [28] | Gao, T.; Li, T. Y.; Wang, X., Finding isolated zeros of polynomial systems in \(C^n\) with stable mixed volumes, J. Symbolic Comput., 28, 187-211 (1999) · Zbl 0944.65055 |
| [29] | M. Giusti, K. Hägele, G. Lecerf, J. Marchand, and, B. Salvy, The projective Noether Maple package: computing the dimension of a projective variety. Manuscript available at,; M. Giusti, K. Hägele, G. Lecerf, J. Marchand, and, B. Salvy, The projective Noether Maple package: computing the dimension of a projective variety. Manuscript available at, · Zbl 0963.68235 |
| [30] | Greuel, G.-M.; Pfister, G.; Schönemann, H., Singular version 1.2 user manual, Reports On Computer Algebra (June 1998), University of KaiserslauternCentre for Computer Algebra |
| [31] | Griffiths, P.; Harris, J., Principles of Algebraic Geometry (1978), Wiley: Wiley New York · Zbl 0408.14001 |
| [32] | Gunning, R. C., Lectures on Complex Analytic Varieties: The Local Parameterization Theorem (1970), Princeton Univ. Pres: Princeton Univ. Pres Princeton · Zbl 0213.35904 |
| [33] | U. Haagerup, Orthogonal MASA’s in the \(nnn\); U. Haagerup, Orthogonal MASA’s in the \(nnn\) |
| [34] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (1996), SIAM: SIAM Philadelphia · Zbl 0847.65010 |
| [35] | Huber, B.; Sturmfels, B., Bernstein’s theorem in affine space, Discr. Comput. Geom., 17, 137-141 (1997) · Zbl 0891.65055 |
| [36] | Kalkbrener, M., On the complexity of Gröbner basis conversion, J. Symbolic Comput., 28, 187-211 (1999) |
| [37] | Li, T. Y., Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numer., 6, 399-436 (1997) · Zbl 0886.65054 |
| [38] | Li, T. Y.; Sauer, T.; Yorke, J. A., The cheater’s homotopy: An efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal., 26, 1241-1251 (1989) · Zbl 0689.65032 |
| [39] | Li, T. Y.; Wang, X., The BKK root count in \(C^n\), Math. Comp., 65, 1477-1484 (1996) · Zbl 0855.65053 |
| [40] | Marinari, M. G.; Möller, H. M.; Mora, T., On multiplicities in polynomial system solving, Trans. Amer. Soc., 348, 3283-3321 (1996) · Zbl 0910.13009 |
| [41] | Mayr, E. W., Some complexity results for polynomial ideals, J. Complexity, 13, 303-325 (1997) · Zbl 1033.12008 |
| [42] | Möller, H. M., Gröbner bases and numerical analysis, (Buchberger, B.; Winkler, F., Gröbner Bases and Applications. Gröbner Bases and Applications, London Mathematical Lecture Note Series, 251 (1998), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 159-178 · Zbl 0928.65058 |
| [43] | Morgan, A. P., Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0733.65031 |
| [44] | Morgan, A. P.; Sommese, A. J., A homotopy for solving general polynomials systems that respects \(m\)-homogeneous structures, Appl. Math. Comput., 24, 101-113 (1987) · Zbl 0635.65057 |
| [45] | Morgan, A. P.; Sommese, A. J., Computation of all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput., 24, 115-138 (1987) · Zbl 0635.65058 |
| [46] | Morgan, A. P.; Sommese, A. J., Coefficient-parameter polynomial continuation, Appl. Math. Comput., 29, 123-160 (1989) · Zbl 0664.65049 |
| [47] | Morgan, A. P.; Wampler, C. W., Solving a planer four-bar design problem using continuation, ASME J. Mechanical Design, 112, 544-550 (1990) |
| [48] | Rheinboldt, W. C., On the computation of multi-dimensional solution manifolds of parameterized equations, Numer. Math., 53, 165-181 (1988) · Zbl 0676.65047 |
| [49] | Rojas, J. M., A convex geometric approach to counting the roots of a polynomial system, Theoret. Comput. Sci., 133, 105-140 (1994) · Zbl 0812.65040 |
| [50] | Rojas, J. M., Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert’s tenth problem, (Cucker, F.; Shub, M., Foundations of Computational Mathematics. Selected Papers of a Conference, Held at IMPA in Rio de Janeiro, January 1997 (1997), Springer-Verlag: Springer-Verlag Berlin/New York), 369-381 · Zbl 0911.13012 |
| [51] | Rojas, J. M., Toric intersection theory for affine root counting, J. Pure Appl. Algebra, 136, 67-100 (1999) · Zbl 0943.14027 |
| [52] | Rojas, J. M., Solving degenerate sparse polynomial systems faster, J. Symbolic Comput., 28, 155-186 (1999) · Zbl 0943.65060 |
| [53] | Rojas, J. M.; Wang, X., Counting affine roots of polynomial systems via pointed Newton polytopes, J. Complexity, 12, 116-133 (1996) · Zbl 0885.12007 |
| [54] | Sommese, A. J.; Wampler, C. W., Numerical algebraic geometry, (Renegar, J.; Shub, M.; Smale, S., The Mathematics and Numerical Analysis. The Mathematics and Numerical Analysis, Lectures in Applied Mathematics, 32 (1996), Proceedings of the 1995 AMS-SIAM Summer Seminar in Applied Mathematics: Proceedings of the 1995 AMS-SIAM Summer Seminar in Applied Mathematics Park City), 749-763 · Zbl 0856.65054 |
| [55] | H. J. Stetter, Numerical polynomial algebra. Supplementary notes for the tutorial on “Interaction between Numerical Analysis and Computer Algebra,” held at ISSAC’98 in Rostock, 1998.; H. J. Stetter, Numerical polynomial algebra. Supplementary notes for the tutorial on “Interaction between Numerical Analysis and Computer Algebra,” held at ISSAC’98 in Rostock, 1998. |
| [56] | Trefethen, L. N., The definition of numerical analysis, SIAM News, 25, 6-22 (Nov. 1992) |
| [57] | Verschelde, J., PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Software, 25, 251-276 (1999) · Zbl 0961.65047 |
| [58] | C. W. Wampler, Isotropic coordinates, circularity and Bezout numbers: planar kinematics from a new perspective, in Proceedings of the 1996 ASME Design Engineering Technical Conference, Irvine, CA, August 18-22, 1996, CD-ROM edited by McCarthy, J. M., American society of mechanical engineers. Also available as GM Technical Report, Publication R&D-8188, 1996.; C. W. Wampler, Isotropic coordinates, circularity and Bezout numbers: planar kinematics from a new perspective, in Proceedings of the 1996 ASME Design Engineering Technical Conference, Irvine, CA, August 18-22, 1996, CD-ROM edited by McCarthy, J. M., American society of mechanical engineers. Also available as GM Technical Report, Publication R&D-8188, 1996. |
| [59] | Yomdin, Y., Sard’s theorem and its improved versions in numerical analysis, (Allgower, E. L.; Georg, K., Computational Solution of Nonlinear Systems of Equations. Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, 26 (1990), Proceedings of 1988 AMS-SIAM Summer Seminar in Applied Mathematics: Proceedings of 1988 AMS-SIAM Summer Seminar in Applied Mathematics Fort Collins), 701-706 · Zbl 0694.65019 |
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.
