Sweeping algebraic curves for singular solutions. (English) Zbl 1189.65101
Summary: Many problems give rise to polynomial systems. These systems often have several parameters and we are interested to study how the solutions vary when we change the values for the parameters. Using predictor-corrector methods we track the solution paths. A point along a solution path is critical when the Jacobian matrix is rank deficient. The simplest case of quadratic turning points is well understood, but these methods no longer work for general types of singularities. In order not to miss any singular solutions along a path we propose to monitor the determinant of the Jacobian matrix. We examine the operation range of deflation and relate the effectiveness of deflation to the winding number. Computational experiments on systems coming from different application fields are presented.
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 26C10 | Real polynomials: location of zeros |
| 30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |
Keywords:
deflation; Newton’s method; path following; polynomial system; singular solution; sweeping homotopy; numerical examples; predictor-corrector methods; quadratic turning pointsReferences:
| [1] | Li, T. Y., Numerical solution of polynomial systems by homotopy continuation methods, (Cucker, F., Handbook of Numerical Analysis. Volume XI. Special Volume: Foundations of Computational Mathematics (2003), North-Holland), 209-304 · Zbl 1059.65046 |
| [2] | Morgan, A., Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems (1987), Prentice-Hall · Zbl 0733.65031 |
| [3] | Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific · Zbl 1091.65049 |
| [4] | Allgower, E. L.; Georg, K., (Introduction to Numerical Continuation Methods. Introduction to Numerical Continuation Methods, Classics in Applied Mathematics, vol. 45 (2003), SIAM) · Zbl 1036.65047 |
| [5] | Govaerts, W. J.F., Numerical Methods for Bifurcations of Dynamical Equilibria (2000), SIAM · Zbl 0935.37054 |
| [6] | Mei, Z., Numerical Bifurcation Analysis for Reaction-Diffusion Equations (2000), Springer-Verlag · Zbl 0952.65105 |
| [7] | Dumortier, F.; Llibre, J.; Artés, J. C., Qualitative Theory of Planar Differential Systems (2006), Springer-Verlag · Zbl 1110.34002 |
| [8] | Lazard, D.; Rouillier, F., Solving parametric polynomial systems, J. Symbolic Comput., 42, 6, 636-667 (2007) · Zbl 1156.14044 |
| [9] | Safey El Din, M.; Schost, E., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set, Discrete Comput. Geom., 32, 3 (2004) · Zbl 1067.14057 |
| [10] | Lu, Y.; Bates, D. J.; Sommese, A. J.; Wampler, C. W., Finding all real points of a complex curve, Contemp. Math., 448, 183-206 (2007) · Zbl 1136.65050 |
| [11] | Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Adaptive multiprecision path tracking, SIAM J. Numer. Anal., 46, 2, 722-746 (2008) · Zbl 1162.65026 |
| [12] | Jorba, A.; Zou, M., A software package for the numerical integration of ODEs by means of high-order Taylor methods, Experiment. Math., 14, 1, 99-117 (2005) · Zbl 1108.65072 |
| [13] | Li, T. Y.; Wang, X., Solving real polynomial systems with real homotopies, Math. Comput., 60, 669-680 (1993) · Zbl 0779.65033 |
| [14] | Li, T. Y.; Zeng, Z.; Cong, L., Solving eigenvalue problems of real nonsymmetric matrices with real homotopies, SIAM J. Numer. Anal., 29, 1, 229-248 (1992) · Zbl 0749.65028 |
| [15] | Guckenheimer, J.; Myers, M.; Sturmfels, B., Computing hopf bifurcations. ii: Three examples from neurophysiology, SIAM J. Sci. Comput., 17, 6, 1275-1301 (1996) · Zbl 0992.37075 |
| [16] | de Jong, T.; Pfister, G., Local Analytic Geometry. Basic Theory and Applications (2000), Vieweg · Zbl 0959.32011 |
| [17] | Walker, R. J., Algebraic Curves (1950), Princeton University Press · Zbl 0039.37701 |
| [18] | Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer-Verlag · Zbl 0930.65067 |
| [19] | Morgan, A. P.; Sommese, A. J.; Wampler, C. W., A power series method for computing singular solutions to nonlinear analytic systems, Numer. Math., 63, 391-409 (1992) · Zbl 0756.65079 |
| [20] | Sosonkina, M.; Watson, L. T.; Stewart, D. E., Note on the end game in homotopy zero curve tracking, ACM Trans. Math. Softw., 22, 3, 281-287 (1996) · Zbl 0884.65044 |
| [21] | Ojika, T.; Watanabe, S.; Mitsui, T., Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl., 96, 463-479 (1983) · Zbl 0525.65027 |
| [22] | Lecerf, G., Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math., 2, 247-293 (2002) · Zbl 1030.65050 |
| [23] | Li, T. Y.; Zeng, Z., A rank-revealing method with updating, downdating and applications, SIAM J. Matrix Anal. Appl., 26, 4, 918-946 (2005) · Zbl 1114.15004 |
| [24] | Dayton, B. H.; Zeng, Z., Computing the multiplicity structure in solving polynomial systems, (Kauers, M., Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (2005), ACM), 116-123 · Zbl 1360.65151 |
| [25] | Leykin, A.; Verschelde, J.; Zhao, A., Newton’s method with deflation for isolated singularities of polynomial systems, Theoret. Comput. Sci., 359, 1-3, 111-122 (2006) · Zbl 1106.65046 |
| [26] | Brezinski, C.; Redivo Zaglia, M., (Extrapolation Methods. Extrapolation Methods, Studies in Computational Mathematics, vol. 2 (1991), North-Holland) · Zbl 0814.65001 |
| [27] | Christiansen, E.; Petersen, H. G., Estimation of convergence orders in repeated Richardson extrapolation, BIT, 29, 1 (1989) · Zbl 0672.65006 |
| [28] | Huber, B.; Verschelde, J., Polyhedral end games for polynomial continuation, Numer. Algorithms, 18, 1, 91-108 (1998) · Zbl 0933.65057 |
| [29] | Leykin, A.; Verschelde, J.; Zhao, A., Higher-order deflation for polynomial systems with isolated singular solutions, (Dickenstein, A.; Schreyer, F.-O.; Sommese, A. J., Algorithms in Algebraic Geometry. Algorithms in Algebraic Geometry, The IMA Volumes in Mathematics and Its Applications, vol. 146 (2008), Springer-Verlag), 79-97 · Zbl 1138.65038 |
| [30] | Verschelde, J., Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25, 2, 251-276 (1999), Software available at http://www.math.uic.edu/ jan/download.html · Zbl 0961.65047 |
| [31] | Emiris, I. Z.; Mourrain, B.; Gusfield, D.; Kao., M.-Y., Computer algebra methods for studying and computing molecular conformations, Algorithmic Research in Computational Biology. Algorithmic Research in Computational Biology, Algorithmica, 25, 2-3, 372-402 (1999), (special issue) |
| [32] | Noonburg, V. W., A neural network modeled by an adaptive Lotka-Volterra system, SIAM J. Appl. Math., 49, 6, 1779-1792 (1989) · Zbl 0684.92008 |
| [33] | Wang, Y. X.; Wang, Y. M., Configuration bifurcations analysis of six degree-of-freedom symmetrical Stewart parallel mechanism, J. Mech. Design, 127, 2, 70-77 (2005) |
| [34] | Stetter, H. J., Numerical Polynomial Algebra (2004), SIAM · Zbl 1058.65054 |
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.
