A symmetric homotopy and hybrid polynomial system solving method for mixed trigonometric polynomial systems

Dong, Bo; Yu, Bo; Yu, Yan

doi:10.1090/S0025-5718-2013-02763-9

A symmetric homotopy and hybrid polynomial system solving method for mixed trigonometric polynomial systems
HTML articles powered by AMS MathViewer

by Bo Dong, Bo Yu and Yan Yu PDF

Math. Comp. 83 (2014), 1847-1868 Request permission

Abstract:

A mixed trigonometric polynomial system, which rather frequently occurs in applications, is a polynomial system where every monomial is a mixture of some variables and sine and cosine functions applied to the other variables. Polynomial systems transformed from the mixed trigonometric polynomial systems have a special structure. Based on this structure, a hybrid polynomial system solving method, which is more efficient than random product homotopy method and polyhedral homotopy method in solving this class of systems, has been presented. Furthermore, the transformed polynomial system has an inherent partially symmetric structure, which cannot be adequately exploited to reduce the computation by the existing methods for solving polynomial systems. In this paper, a symmetric homotopy is constructed and, combining homotopy methods, decomposition, and elimination techniques, an efficient symbolic-numerical method for solving this class of polynomial systems is presented. Preservation of the symmetric structure assures us that only part of the homotopy paths have to be traced, and more important, the computation work can be reduced due to the existence of the inconsistent subsystems, which need not to be solved at all. Exploiting the new hybrid method, some problems from the literature and a challenging practical problem, which cannot be solved by the existing methods, are resolved. Numerical results show that our method has an advantage over the polyhedral homotopy method, hybrid method and regeneration method, which are considered as the state-of-art numerical methods for solving highly deficient polynomial systems of high dimension.

References

Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Bertini: Software for numerical algebraic geometry, http://www.nd.edu/$\sim$sommese/bertini/.
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157, DOI 10.1007/978-1-4757-3849-0
H. Hong and V. Stahl, Safe starting regions by fixed points and tightening, Computing 53 (1994), no. 3-4, 323–335 (English, with English and German summaries). International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (Vienna, 1993). MR 1308770, DOI 10.1007/BF02307383
Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 1541–1555. MR 1297471, DOI 10.1090/S0025-5718-1995-1297471-4
Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Regeneration homotopies for solving systems of polynomials, Math. Comp. 80 (2011), no. 273, 345–377. MR 2728983, DOI 10.1090/S0025-5718-2010-02399-3
T. L. Lee, T. Y. Li, and C. H. Tsai, HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing 83 (2008), no. 2-3, 109–133. MR 2457354, DOI 10.1007/s00607-008-0015-6
T. Y. Li, Numerical solution of polynomial systems by homotopy continuation methods, Handbook of numerical analysis, Vol. XI, Handb. Numer. Anal., XI, North-Holland, Amsterdam, 2003, pp. 209–304. MR 2009773
T. Y. Li, Tim Sauer, and J. A. Yorke, The cheater’s homotopy: an efficient procedure for solving systems of polynomial equations, SIAM J. Numer. Anal. 26 (1989), no. 5, 1241–1251. MR 1014884, DOI 10.1137/0726069
T.-Y. Li, Tim Sauer, and James A. Yorke, The random product homotopy and deficient polynomial systems, Numer. Math. 51 (1987), no. 5, 481–500. MR 910860, DOI 10.1007/BF01400351
T. Y. Li and Xiao Shen Wang, Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant, Math. Comp. 56 (1991), no. 194, 693–710. MR 1066835, DOI 10.1090/S0025-5718-1991-1066835-2
Tien-Yien Li, On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials, Bull. Inst. Math. Acad. Sinica 11 (1983), no. 3, 433–437. MR 726989
Tien-Yien Li, Solving polynomial systems, Math. Intelligencer 9 (1987), no. 3, 33–39. MR 895771, DOI 10.1007/BF03023953
Tien-Yien Li, Solving polynomial systems by polyhedral homotopies, Taiwanese J. Math. 3 (1999), no. 3, 251–279. MR 1705990, DOI 10.11650/twjm/1500407124
Tien-Yien Li and Tim Sauer, A simple homotopy for solving deficient polynomial systems, Japan J. Appl. Math. 6 (1989), no. 3, 409–419. MR 1019683, DOI 10.1007/BF03167887
Tien-Yien Li, Tim Sauer, and James A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24 (1987), no. 2, 435–451. MR 881375, DOI 10.1137/0724032
Pavol Meravý, Symmetric homotopies for solving systems of polynomial equations, Math. Slovaca 39 (1989), no. 3, 277–288 (English, with Russian summary). MR 1016345
Alexander Morgan and Andrew Sommese, Computing all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput. 24 (1987), no. 2, 115–138. MR 914807, DOI 10.1016/0096-3003(87)90064-6
Alexander Morgan and Andrew Sommese, A homotopy for solving general polynomial systems that respects $m$-homogeneous structures, Appl. Math. Comput. 24 (1987), no. 2, 101–113. MR 914806, DOI 10.1016/0096-3003(87)90063-4
Alexander P. Morgan, A homotopy for solving polynomial systems, Appl. Math. Comput. 18 (1986), no. 1, 87–92. MR 815774, DOI 10.1016/0096-3003(86)90030-5
Alexander P. Morgan and Andrew J. Sommese, Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), no. 2, 123–160. MR 977815, DOI 10.1016/0096-3003(89)90099-4
Alexander P. Morgan and Andrew J. Sommese, Coefficient-parameter polynomial continuation, Appl. Math. Comput. 29 (1989), no. 2, 123–160. MR 977815, DOI 10.1016/0096-3003(89)90099-4
Pascal Van Hentenryck, David McAllester, and Deepak Kapur, Solving polynomial systems using a branch and prune approach, SIAM J. Numer. Anal. 34 (1997), no. 2, 797–827. MR 1442939, DOI 10.1137/S0036142995281504
Jan Verschelde, Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation, 25 (1999), no. 2, 251–276.
Jan Verschelde, Marc Beckers, and Ann Haegemans, A new start system for solving deficient polynomial systems using continuation, Appl. Math. Comput. 44 (1991), no. 3, 225–239. MR 1115067, DOI 10.1016/0096-3003(91)90059-V
Jan Verschelde and Ronald Cools, Symmetric homotopy construction, Proceedings of the Fifth International Congress on Computational and Applied Mathematics (Leuven, 1992), 1994, pp. 575–592. MR 1284290, DOI 10.1016/0377-0427(94)90329-8
Jan Verschelde and Karin Gatermann, Symmetric Newton polytopes for solving sparse polynomial systems, Adv. in Appl. Math. 16 (1995), no. 1, 95–127. MR 1317613, DOI 10.1006/aama.1995.1005
Jan Verschelde and Ann Haegemans, The $GBQ$-algorithm for constructing start systems of homotopies for polynomial systems, SIAM J. Numer. Anal. 30 (1993), no. 2, 583–594. MR 1211406, DOI 10.1137/0730028
Jan Verschelde, Pierre Verlinden, and Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), no. 3, 915–930. MR 1275120, DOI 10.1137/0731049
Alden H. Wright, Finding all solutions to a system of polynomial equations, Math. Comp. 44 (1985), no. 169, 125–133. MR 771035, DOI 10.1090/S0025-5718-1985-0771035-4
Bo Yu and Bo Dong, A hybrid polynomial system solving method for mixed trigonometric polynomial systems, SIAM J. Numer. Anal. 46 (2008), no. 3, 1503–1518. MR 2391004, DOI 10.1137/070681740
Bo Yu and Guo Chen Feng, The random product homotopy for solving polynomial systems in $\textbf {C}^{k_1}\times \textbf {C}^{k_2}\times \cdots \times \textbf {C}^{k_m}$, Computer mathematics (Tianjin, 1991) Nankai Ser. Pure Appl. Math. Theoret. Phys., vol. 5, World Sci. Publ., River Edge, NJ, 1993, pp. 36–45. MR 1257442
Walter Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), no. 181, 167–177. MR 917824, DOI 10.1090/S0025-5718-1988-0917824-7