×

Sampling algebraic sets in local intrinsic coordinates. (English) Zbl 1236.14052

Summary: Numerical data structures for positive dimensional solution sets of polynomial systems are sets of generic points cut out by random planes of complementary dimension. We may represent the linear spaces defined by those planes either by explicit linear equations or in parametric form. These descriptions are respectively called extrinsic and intrinsic representations. While intrinsic representations lower the cost of the linear algebra operations, we observe worse condition numbers. In this paper we describe the local adaptation of intrinsic coordinates to improve the numerical conditioning of sampling algebraic sets. Local intrinsic coordinates also lead to a better step size control. We illustrate our results with Maple experiments and computations with PHCpack on some benchmark polynomial systems.

MSC:

14Q15 Computational aspects of higher-dimensional varieties
14P10 Semialgebraic sets and related spaces
65H99 Nonlinear algebraic or transcendental equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Mumford, D., (Algebraic Geometry I. Complex Projective Varieties. Algebraic Geometry I. Complex Projective Varieties, Classics in Mathematics (1995), Springer-Verlag), Corrected second printing of the 1976 edition. Originally published as volume 221 of the Grundlehren der mathematischen Wissenschaften · Zbl 0821.14001
[2] 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
[3] 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
[4] Morgan, A., (Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, Classics in Applied Mathematics Series, vol. 57 (1987), Prentice-Hall), SIAM 2009. Pages with code at: http://www.siam.org/books/cl57 · Zbl 0733.65031
[5] Sommese, A. J.; Wampler, C. W., Numerical algebraic geometry, (Renegar, J.; Shub, M.; Smale, S., The Mathematics of Numerical Analysis. The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32 (1996), AMS), 749-763, Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics. Park City, Utah, July 17-August 11, 1995, Park City, Utah · Zbl 0856.65054
[6] Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific · Zbl 1091.65049
[7] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Introduction to numerical algebraic geometry, (Dickenstein, A.; Emiris, E. Z., Solving Polynomial Equations. Foundations, Algorithms and Applications. Solving Polynomial Equations. Foundations, Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 14 (2005), Springer-Verlag), 301-337 · Zbl 1152.14313
[8] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM J. Numer. Anal., 38, 6, 2022-2046 (2001) · Zbl 1002.65060
[9] 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
[10] Verschelde, J., Polynomial homotopy continuation with PHCpack, ACM Commun. Comput. Algebra, 44, 4, 217-220 (2010) · Zbl 1308.68198
[11] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Numerical irreducible decomposition using PHCpack, (Joswig, M.; Takayama, N., Algebra, Geometry, and Software Systems (2003), Springer-Verlag), 109-130 · Zbl 1027.65066
[12] Guan, Y.; Verschelde, J., PHClab: a MATLAB/Octave interface to PHCpack, (Stillman, M. E.; Takayama, N.; Verschelde, J., Software for Algebraic Geometry. Software for Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 148 (2008), Springer-Verlag), 15-32 · Zbl 1148.68578
[13] Leykin, A.; Verschelde, J., Interfacing with the numerical homotopy algorithms in PHCpack, (Takayama, N.; Iglesias, A., Proceedings of ICMS 2006. Proceedings of ICMS 2006, Lecture Notes in Computer Science, vol. 4151 (2006), Springer-Verlag), 354-360 · Zbl 1230.65061
[14] E. Gross, S. Petrović, J. Verschelde, PHCpack in Macaulay2, Preprint. arXiv:1105.4881v1; E. Gross, S. Petrović, J. Verschelde, PHCpack in Macaulay2, Preprint. arXiv:1105.4881v1
[15] Leykin, A., Numerical algebraic geometry for Macaulay 2, J. Softw. Algebra Geom.: Macaulay 2, 3, 5-10 (2011) · Zbl 1311.14057
[16] D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: software for numerical algebraic geometry. Available at: http://www.nd.edu/ sommese/bertini/; D.J. Bates, J.D. Hauenstein, A.J. Sommese, C.W. Wampler, Bertini: software for numerical algebraic geometry. Available at: http://www.nd.edu/ sommese/bertini/ · Zbl 1143.65344
[17] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Software for numerical algebraic geometry: a paradigm and progress towards its implementation, (Stillman, M. E.; Takayama, N.; Verschelde, J., Software for Algebraic Geometry. Software for Algebraic Geometry, The IMA Volumes in Mathematics and its Applications, vol. 148 (2008), Springer-Verlag), 1-14 · Zbl 1143.65344
[18] Sommese, A. J.; Verschelde, J.; Wampler, C. W., An intrinsic homotopy for intersecting algebraic varieties, J. Complexity, 21, 4, 593-608 (2005), Festschrift for the 70th Birthday of Arnold Schönhage, edited by T. Lickteig and L.M. Pardo · Zbl 1108.13309
[19] 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
[20] Verschelde, J.; Yoffe, G., Polynomial homotopies on multicore workstations, (Maza, M. M.; Roch, J.-L., PASCO 2010. Proceedings of the 2010 International Workshop on Parallel Symbolic Computation (2010), ACM), 131-140
[21] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Stepsize control for path tracking, (Bates, D. J.; Besana, G.; Di Rocco, S.; Wampler, C. W., Interactions of Classical and Numerical Algebraic Geometry. Interactions of Classical and Numerical Algebraic Geometry, Contemporary Mathematics, vol. 496 (2009), AMS), 21-31 · Zbl 1181.65071
[22] Galligo, A.; Poteaux, A., Continuations and monodromy on random Riemann surfaces, (Kai, H.; Sekigawa, H., SNC’09. Proceedings of the 2009 International Workshop on Symbolic-Numeric Computation (2009), ACM), 115-123 · Zbl 1356.14051
[23] Poteaux, A., Computing monodromy groups defined by plane curves, (Verschelde, J.; Watt, S. M., SNC’07. Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation (2007), ACM), 239-246
[24] Kim, S.; Kojima, M., Numerical stability of path tracing in polyhedral homotopy continuation methods, Computing, 73, 4, 329-348 (2004) · Zbl 1061.65042
[25] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Solving polynomial systems equation by equation, (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), 133-152 · Zbl 1136.65052
[26] Guan, Y.; Verschelde, J., Parallel implementation of a subsystem-by-subsystem solver, (The Proceedings of the 22th High Performance Computing Symposium. The Proceedings of the 22th High Performance Computing Symposium, Quebec City, 9-11 June 2008 (2008), IEEE Computer Society), 117-123
[27] 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
[28] 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. Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ISSAC’05, July 24-27 2005, Beijing, China (2005), ACM), 116-123 · Zbl 1360.65151
[29] Sommese, A. J.; Verschelde, J., Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complexity, 16, 3, 572-602 (2000) · Zbl 0982.65070
[30] Diaconis, P.; Eisenbud, D.; Sturmfels, B., Lattice walks and primary decomposition, (Sagan, B. E.; Stanley, R. P., Mathematical Essays in Honor of Gian-Carlo Rota. Mathematical Essays in Honor of Gian-Carlo Rota, Progress in Mathematics, vol. 161 (1998), Birkhäuser), 173-193 · Zbl 0962.05010
[31] Hosten, S.; Shapiro, J., Primary decomposition of lattice basis ideals, J. Symbolic. Comput., 29, 4-5, 625-639 (2000) · Zbl 0968.13003
[32] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Homotopies for intersecting solution components of polynomial systems, SIAM J. Numer. Anal., 42, 4, 552-1571 (2004) · Zbl 1108.13308
[33] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Using monodromy to decompose solution sets of polynomial systems into irreducible components, (Ciliberto, C.; Hirzebruch, F.; Miranda, R.; Teicher, M., Application of Algebraic Geometry to Coding Theory, Physics and Computation (2001), Kluwer Academic Publishers), 297-315, Proceedings of a NATO Conference, February 25-March 1, 2001, Eilat, Israel · Zbl 0990.65051
[34] M.B. Monagan, K.O. Geddes, K.M. Heal, G. Labahn, S.M. Vorkoetter, J. McCarron, P. DeMarco, Maple Advanced Programming Guide, Maplesoft, 2008.; M.B. Monagan, K.O. Geddes, K.M. Heal, G. Labahn, S.M. Vorkoetter, J. McCarron, P. DeMarco, Maple Advanced Programming Guide, Maplesoft, 2008.
[35] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, J.; Demmel, S.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., (LAPACK’s Users Guide. LAPACK’s Users Guide, Software, Environments, and Tools, vol. 9 (1999), SIAM) · Zbl 0934.65030
[36] Demmel, J. W., Applied Numerical Linear Algebra (1997), SIAM · Zbl 0879.65017
[37] Tyrtyshnikov, E. E., A Brief Introduction to Numerical Analysis (1997), Birkhäuser · Zbl 0874.65001
[38] Wilkinson, J. H., The perfidious polynomial, (Golub, G. H., Studies in Numerical Analysis. Studies in Numerical Analysis, MAA Studies in Mathematics, vol. 24 (1984), MAA), 1-28 · Zbl 0601.65028
[39] Gautschi, W., Questions of numerical condition related to polynomials, (Golub, G. H., Studies in Numerical Analysis. Studies in Numerical Analysis, MAA Studies in Mathematics, vol. 24 (1984), MAA), 140-177 · Zbl 0584.65020
[40] Demmel, J., The condition number of equivalence transformations that block diagonalize matrix pencils, SIAM J. Numer. Anal., 20, 3, 599-610 (1983) · Zbl 0509.65020
[41] Shepp, L. A.; Vanderbei, R. J., The complex zeros of random polynomials, Trans. Amer. Math. Soc., 347, 11, 4365-4384 (1995) · Zbl 0841.30006
[42] Rheinboldt, W. C., On measures of ill-conditioning for nonlinear equations, Math. Comp., 30, 133, 104-111 (1976) · Zbl 0328.65032
[43] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press · Zbl 0865.65009
[44] Higham, N. J., Accuracy and Stability of Numerical Algorithms (1996), SIAM · Zbl 0847.65010
[45] C. Beltran, A. Leykin, Certified numerical homotopy tracking, Preprint. arXiv:0912.0920v1; C. Beltran, A. Leykin, Certified numerical homotopy tracking, Preprint. arXiv:0912.0920v1 · Zbl 1238.14048
[46] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer-Verlag
[47] Petković, M., (Point Estimation of Root Finding Methods. Point Estimation of Root Finding Methods, Lecture Notes in Mathematics, vol. 1933 (2007), Springer-Verlag) · Zbl 1160.65017
[48] J. Backelin, Square multiples \(nn\); J. Backelin, Square multiples \(nn\)
[49] M. Griffis, J. Duffy, Method and apparatus for controlling geometrically simple parallel mechanisms with distinctive connections. US Patent 5,179,525, 1993.; M. Griffis, J. Duffy, Method and apparatus for controlling geometrically simple parallel mechanisms with distinctive connections. US Patent 5,179,525, 1993.
[50] M.L. Husty, A. Karger, Self-motions of Griffis-Duffy type parallel manipulators, in: Proc. 2000 IEEE Int. Conf. Robotics and Automation, San Francisco, CA, April 24-28 2000 [CDROM].; M.L. Husty, A. Karger, Self-motions of Griffis-Duffy type parallel manipulators, in: Proc. 2000 IEEE Int. Conf. Robotics and Automation, San Francisco, CA, April 24-28 2000 [CDROM].
[51] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Advances in polynomial continuation for solving problems in kinematics, ASME J. Mech. Des., 126, 2, 262-268 (2004)
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.