×

Computing singular solutions to polynomial systems. (English) Zbl 0764.65030

A method to improve the accuracy of approximations to singular solutions of polynomial systems is presented. The method is established in a context of polynomial continuation; thus all solutions are generated, with the singular solution being approximated more accurately by standard implementations.
The theorem on which the method is based is proven using results from several complex variables and algebraic geometry. A specific implementation is given and the results in solving four test problems are presented.

MSC:

65H10 Numerical computation of solutions to systems of equations
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Software:

PITCON; HOMPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower, E. L., A survey of homotopy methods for smooth mappings, (Allgower, E. L.; Glashoff, K.; Peitgen, H.-O, Numerical Solution of Nonlinear Equations. Numerical Solution of Nonlinear Equations, Lecture Notes in Mathematics, No. 878 (1981), Springer-Verlag: Springer-Verlag New York), 1-29 · Zbl 0461.65037
[2] Allgower, E. L.; Georg, K., Simplicial and continuation methods for approximating fixed points and solutions to systems of equations, SIAM Rev., 22, 28-85 (1989) · Zbl 0432.65027
[3] Brunovský, P.; Meravý, P., Solving systems of polynomial equations by bounded and real homotopy, Numer. Math., 43, 397-418 (1984) · Zbl 0543.65030
[4] Chow, S. N.; Mallet-Paret, J.; Yorke, J. A., A homotopy method for locating all zeros of a system of polynomials, (Peitgen, H. O.; Walther, H. O., Functional Differential Equations and Approximation of Fixed Points. Functional Differential Equations and Approximation of Fixed Points, Lecture Notes in Math., No. 730 (1979), Springer-Verlag: Springer-Verlag New York/Berlin), 228-237
[5] Decker, D. W.; Keller, H. B.; Kelley, C. T., Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal., 20, 296-314 (1983) · Zbl 0571.65046
[6] Decker, D. W.; Kelley, C. T., Newton’s method at singular points, I, SIAM J. Numer. Anal., 17, 66-70 (1980) · Zbl 0428.65037
[7] Decker, D. W.; Kelley, C. T., Newton’s method at singular points, II, SIAM J. Numer. Anal., 17, 465-471 (1980) · Zbl 0453.65037
[8] Decker, D. W.; Kelley, C. T., Broyden’s method for a class of problems having singular Jacobian at the root, SIAM J. Numer. Anal., 22, 566-574 (1985) · Zbl 0583.65022
[9] Drexler, F. J., Eine Methode zur Berechung sämtlicher Lösunger von Polynomgleichunges-systemen, Numer. Math., 29, 45-58 (1977)
[10] Drexler, F. J., A homotopy method for the calculation of zeros of zero-dimensional polynomial ideals, (Wacker, H. G., Continuation Methods (1978), Academic Press: Academic Press New York), 69-93 · Zbl 0465.55003
[11] Fischer, G., Complex Analytic Geometry, (Lecture Notes in Mathematics, No. 538 (1977), Springer-Verlag: Springer-Verlag New York) · Zbl 0343.32002
[12] Forsythe, G. E.; Malcolm, M. A.; Moler, C. B., Computer Methods for Mathematical Computations (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0361.65002
[13] Garcia, C. B.; Zangwill, W. I., Global Continuation Methods for Finding All Solutions to Polynomial Systems of Equations in \(N\) Variables, (Center for Math. Studies in Business and Economic Report No. 7755 (1977), University of Chicago) · Zbl 0428.90085
[14] Garcia, C. B.; Zangwill, W. I., Finding all solutions to polynomial systems and other systems of equations, Math. Programming, 16, 159-176 (1979) · Zbl 0409.65026
[15] Garcia, C. B.; Zangwill, W. I., An approach to homotopy and degree theory, Math. Oper. Res., 4, 390-405 (1979) · Zbl 0422.55001
[16] Garcia, C. B.; Zangwill, W. I., Determining all solutions to certain systems of nonlinear equations, Math. Oper. Res., 4, 1-14 (1979) · Zbl 0408.90086
[17] Garcia, C. B.; Zangwill, W. I., Pathways to Solutions, Fixed Points, and Equilibria (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0512.90070
[18] Griewank, A., On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev., 27, 537-563 (1985) · Zbl 0598.65026
[19] Griewank, A.; Osborne, M. R., Analysis of Newton’s method at irregular singularities, SIAM J. Numer. Anal., 20, 747-773 (1983) · Zbl 0525.65025
[20] Keller, H. B., Geometrically isolated nonisolated solutions and their approximation, SIAM J. Numer. Anal., 18, 822-838 (1981) · Zbl 0493.65022
[21] Li, T. Y., On Chow, Mallet-Paret, and Yorke homotopy for solving system of polynomials, Bull. Inst. Math. Acad. Sinica, 11, 433-437 (1983) · Zbl 0538.65030
[22] Li, T. Y.; Sauer, T.; Yorke, J. A., Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal., 24, 435-451 (1987) · Zbl 0625.65039
[23] Li, T. Y.; Sauer, T.; Yorke, J. A., Numerically determining solutions of systems of polynomial equations, Bull. Amer. Math. Soc., 18, 173-177 (1988) · Zbl 0651.65042
[24] Li, T. Y.; Sauer, T.; Yorke, J. A., The cheater’s homotopy: An efficient procedure for solving systems of polynomial equations, SIAM J. Num. Anal., 26, 1241-1251 (1989) · Zbl 0689.65032
[25] Meintjes, K.; Morgan, A. P., A methodology for solving chemical equilibrium systems, Appl. Math. Comput., 22, 333-361 (1987) · Zbl 0616.65057
[26] Morgan, A. P., A method for computing all solutions to systems of polynomial equations, ACM Trans. Math. Software, 9, 1-17 (1983) · Zbl 0516.65026
[27] Morgan, A. P., A homotopy for solving polynomial systems, Appl. Math. Comput., 18, 87-92 (1986) · Zbl 0597.65046
[28] Morgan, A. P., A transformation to avoid solutions at infinity for polynomial systems, Appl. Math. Comput., 18, 77-86 (1986) · Zbl 0597.65045
[29] Morgan, A. P., Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0733.65031
[30] Morgan, A. P., Polynomial continuation, (Sharda, R., Impact of Recent Computer Advances on Operations Research. Impact of Recent Computer Advances on Operations Research, Publications in Operations Research Series (1989), North-Holland: North-Holland New York) · Zbl 0699.65036
[31] Morgan, A. P.; Sommese, A. J., A homotopy for solving general polynomial systems that respects \(m\)-homogeneous structures, Appl. Math. Comput., 24, 101-113 (1987) · Zbl 0635.65057
[32] Morgan, A. P.; Sommese, A. J., Computing all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput., 24, 115-138 (1987) · Zbl 0635.65058
[33] Morgan, A. P.; Sommese, A. J., Coefficient-parameter polynomial continuation, Appl. Math. Comput., 29, 123-160 (1989) · Zbl 0664.65049
[34] Morgan, A. P.; Sommese, A. J., Generically nonsingular polynomial continuation, (Allgower, E.; Georg, K., Computational Solution of Nonlinear Systems of Equations. Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Vol. 26 (1990), Amer. Math. Soc: Amer. Math. Soc Providence, RI) · Zbl 0699.65036
[35] Morgan, A. P.; Sommese, A. J.; Wampler, C. W., Polynomial continuation for mechanism design problems, (Allgower, E.; Georg, K., Computational Solution of Nonlinear Systems of Equations. Computational Solution of Nonlinear Systems of Equations, Lectures in Applied Mathematics, Vol. 26 (1990), Amer. Math. Soc: Amer. Math. Soc Providence, RI) · Zbl 0693.73061
[36] Morgan, A. P.; Sommese, A. J.; Wampler, C. W., Computing singular solutions to nonlinear analytic systems, Numer. Math., 58, 669-684 (1991) · Zbl 0721.65027
[37] Morgan, A. P.; Sommese, A. J.; Watson, L. T., Finding all isolated solutions to polynomial systems using HOMPACK, ACM Trans. Math. Software, 15, 93-122 (1989) · Zbl 0900.65151
[38] Pasquini, L.; Trignante, D., A globally convergent method for simultaneously finding polynomial roots, Math. Comp., 44, 135-149 (1985) · Zbl 0565.65026
[39] Rall, L. B., Convergence of the Newton process to multiple solutions, Numer. Math., 9, 23-37 (1966) · Zbl 0163.38702
[40] Reddien, G. W., On Newton’s method for singular problems, SIAM J. Numer. Anal., 15, 993-996 (1978) · Zbl 0397.65042
[41] Rheinboldt, W. C., Numerical Analysis of Parametrized Nonlinear Equations (1986), Wiley: Wiley New York · Zbl 0572.65034
[42] Rheinboldt, W. C.; Burkardt, J. V., Algorithm 596: A program for a locally parameterized continuation process, ACM Trans. Math. Software, 9, 236-241 (1983)
[43] Wampler, C. W.; Morgan, A. P.; Sommese, A. J., Numerical continuation methods for solving polynomial systems arising in kinematics, ASME J. Mech. Des., 112, 59-68 (1990)
[44] Watson, L. T., A globally convergent algorithm for computing fixed points of \(C^2\) maps, Appl. Math. Comput., 5, 297-311 (1979) · Zbl 0445.65032
[45] Watson, L. T.; Billups, S. C.; Morgan, A. P., HOMPACK: A suite of codes for globally convergent homotopy algorithms, ACM Trans. Math. Software, 13, 281-310 (1987) · Zbl 0626.65049
[46] Wright, A. H., Finding all solutions to a system of polynomial equations, Math. Comp., 44, 125-133 (1985) · Zbl 0567.55002
[47] Zulehner, W., A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp., 50, 167-177 (1988) · Zbl 0637.65045
[48] Zulehner, W., On the solutions to polynomial systems obtained by homotopy methods, Numer. Math., 54, 303-317 (1988) · Zbl 0643.65024
[49] Zulehner, W., Numerical solution of polynomial equation systems by curve tracing, Z. Angew. Math. Mech., 68, T504-T505 (1988) · Zbl 0663.65051
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.