A symmetric homotopy and hybrid polynomial system solving method for mixed trigonometric polynomial systems
Authors:
Bo Dong, Bo Yu and Yan Yu
Journal:
Math. Comp. 83 (2014), 18471868
MSC (2010):
Primary 13P15, 65H20; Secondary 65H10, 14Q99, 68W30
Published electronically:
November 7, 2013
MathSciNet review:
3194132
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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 symbolicnumerical 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 stateofart numerical methods for solving highly deficient polynomial systems of high dimension.
 [1]
Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Bertini: Software for numerical algebraic geometry, http://www.nd.edu/sommese/bertini/.
 [2]
David
Cox, John
Little, and Donal
O’Shea, Using algebraic geometry, Graduate Texts in
Mathematics, vol. 185, SpringerVerlag, New York, 1998. MR 1639811
(99h:13033)
 [3]
Robin
Hartshorne, Algebraic geometry, SpringerVerlag, New
YorkHeidelberg, 1977. Graduate Texts in Mathematics, No. 52. MR 0463157
(57 #3116)
 [4]
H.
Hong and V.
Stahl, Safe starting regions by fixed points and tightening,
Computing 53 (1994), no. 34, 323–335 (English,
with English and German summaries). International Symposium on Scientific
Computing, Computer Arithmetic and Validated Numerics (Vienna, 1993). MR 1308770
(95i:65081), 10.1007/BF02307383
 [5]
Birkett
Huber and Bernd
Sturmfels, A polyhedral method for solving sparse
polynomial systems, Math. Comp.
64 (1995), no. 212, 1541–1555. MR 1297471
(95m:65100), 10.1090/S00255718199512974714
 [6]
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
(2012d:65105), 10.1090/S002557182010023993
 [7]
T.
L. Lee, T.
Y. Li, and C.
H. Tsai, HOM4PS2.0: a software package for solving polynomial
systems by the polyhedral homotopy continuation method, Computing
83 (2008), no. 23, 109–133. MR 2457354
(2009h:65223), 10.1007/s0060700800156
 [8]
T.
Y. Li, Numerical solution of polynomial systems by homotopy
continuation methods, Handbook of numerical analysis, Vol.\ XI,
Handb. Numer. Anal., XI, NorthHolland, Amsterdam, 2003,
pp. 209–304. MR 2009773
(2004k:65089)
 [9]
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
(90m:65105), 10.1137/0726069
 [10]
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 (88j:65108), 10.1007/BF01400351
 [11]
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
(91j:65089), 10.1090/S00255718199110668352
 [12]
TienYien
Li, On Chow, MalletParet and Yorke homotopy for solving system of
polynomials, Bull. Inst. Math. Acad. Sinica 11
(1983), no. 3, 433–437. MR 726989
(85k:58015)
 [13]
TienYien
Li, Solving polynomial systems, Math. Intelligencer
9 (1987), no. 3, 33–39. MR 895771
(89d:12001), 10.1007/BF03023953
 [14]
TienYien
Li, Solving polynomial systems by polyhedral homotopies,
Taiwanese J. Math. 3 (1999), no. 3, 251–279. MR 1705990
(2000e:65057)
 [15]
TienYien
Li and Tim
Sauer, A simple homotopy for solving deficient polynomial
systems, Japan J. Appl. Math. 6 (1989), no. 3,
409–419. MR 1019683
(90j:65077), 10.1007/BF03167887
 [16]
TienYien
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 (89e:90181), 10.1137/0724032
 [17]
Pavol
Meravý, Symmetric homotopies for solving systems of
polynomial equations, Math. Slovaca 39 (1989),
no. 3, 277–288 (English, with Russian summary). MR 1016345
(91d:65074)
 [18]
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
(89b:65126), 10.1016/00963003(87)900646
 [19]
Alexander
Morgan and Andrew
Sommese, A homotopy for solving general polynomial systems that
respects 𝑚homogeneous structures, Appl. Math. Comput.
24 (1987), no. 2, 101–113. MR 914806
(88j:65110), 10.1016/00963003(87)900634
 [20]
Alexander
P. Morgan, A homotopy for solving polynomial systems, Appl.
Math. Comput. 18 (1986), no. 1, 87–92. MR 815774
(87c:90194), 10.1016/00963003(86)900305
 [21]
Alexander
P. Morgan and Andrew
J. Sommese, Coefficientparameter polynomial continuation,
Appl. Math. Comput. 29 (1989), no. 2, 123–160.
MR 977815
(90f:58018), 10.1016/00963003(89)900994
 [22]
Alexander
P. Morgan and Andrew
J. Sommese, Coefficientparameter polynomial continuation,
Appl. Math. Comput. 29 (1989), no. 2, 123–160.
MR 977815
(90f:58018), 10.1016/00963003(89)900994
 [23]
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
(98g:65050), 10.1137/S0036142995281504
 [24]
Jan Verschelde, Algorithm 795: Phcpack: A generalpurpose solver for polynomial systems by homotopy continuation, 25 (1999), no. 2, 251276.
 [25]
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
(92c:65068), 10.1016/00963003(91)90059V
 [26]
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
(95j:65056), 10.1016/03770427(94)903298
 [27]
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 (95m:65101), 10.1006/aama.1995.1005
 [28]
Jan
Verschelde and Ann
Haegemans, The 𝐺𝐵𝑄algorithm for
constructing start systems of homotopies for polynomial systems, SIAM
J. Numer. Anal. 30 (1993), no. 2, 583–594. MR 1211406
(94b:65075), 10.1137/0730028
 [29]
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
(94m:65084), 10.1137/0731049
 [30]
Alden
H. Wright, Finding all solutions to a system of
polynomial equations, Math. Comp.
44 (1985), no. 169, 125–133. MR 771035
(86i:12001), 10.1090/S00255718198507710354
 [31]
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
(2009b:65133), 10.1137/070681740
 [32]
Bo
Yu and Guo
Chen Feng, The random product homotopy for solving polynomial
systems in
𝐶^{𝑘₁}×𝐶^{𝑘₂}×\cdots×𝐶^{𝑘_{𝑚}},
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
(95c:65080)
 [33]
Walter
Zulehner, A simple homotopy method for
determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), no. 181, 167–177. MR 917824
(89b:65130), 10.1090/S00255718198809178247
 [1]
 Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Bertini: Software for numerical algebraic geometry, http://www.nd.edu/sommese/bertini/.
 [2]
 David Cox, John Little, and Donal O'Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, SpringerVerlag, New York, 1998. MR 1639811 (99h:13033)
 [3]
 Robin Hartshorne, Algebraic geometry, SpringerVerlag, New York, 1977. Graduate Texts in Mathematics, No. 52. MR 0463157 (57 #3116)
 [4]
 H. Hong and V. Stahl, Safe starting regions by fixed points and tightening, Computing 53 (1994), no. 34, 323335 (English, with English and German summaries). International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (Vienna, 1993). MR 1308770 (95i:65081), http://dx.doi.org/10.1007/BF02307383
 [5]
 Birkett Huber and Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Math. Comp. 64 (1995), no. 212, 15411555. MR 1297471 (95m:65100), http://dx.doi.org/10.2307/2153370
 [6]
 Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Regeneration homotopies for solving systems of polynomials, Math. Comp. 80 (2011), no. 273, 345377. MR 2728983 (2012d:65105), http://dx.doi.org/10.1090/S002557182010023993
 [7]
 T. L. Lee, T. Y. Li, and C. H. Tsai, HOM4PS2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method, Computing 83 (2008), no. 23, 109133. MR 2457354 (2009h:65223), http://dx.doi.org/10.1007/s0060700800156
 [8]
 T. Y. Li, Numerical solution of polynomial systems by homotopy continuation methods, Handbook of numerical analysis, Vol. XI, Handb. Numer. Anal., XI, NorthHolland, Amsterdam, 2003, pp. 209304. MR 2009773 (2004k:65089)
 [9]
 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, 12411251. MR 1014884 (90m:65105), http://dx.doi.org/10.1137/0726069
 [10]
 T.Y. Li, Tim Sauer, and James A. Yorke, The random product homotopy and deficient polynomial systems, Numer. Math. 51 (1987), no. 5, 481500. MR 910860 (88j:65108), http://dx.doi.org/10.1007/BF01400351
 [11]
 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, 693710. MR 1066835 (91j:65089), http://dx.doi.org/10.2307/2008402
 [12]
 TienYien Li, On Chow, MalletParet and Yorke homotopy for solving system of polynomials, Bull. Inst. Math. Acad. Sinica 11 (1983), no. 3, 433437. MR 726989 (85k:58015)
 [13]
 TienYien Li, Solving polynomial systems, Math. Intelligencer 9 (1987), no. 3, 3339. MR 895771 (89d:12001), http://dx.doi.org/10.1007/BF03023953
 [14]
 TienYien Li, Solving polynomial systems by polyhedral homotopies, Taiwanese J. Math. 3 (1999), no. 3, 251279. MR 1705990 (2000e:65057)
 [15]
 TienYien Li and Tim Sauer, A simple homotopy for solving deficient polynomial systems, Japan J. Appl. Math. 6 (1989), no. 3, 409419. MR 1019683 (90j:65077), http://dx.doi.org/10.1007/BF03167887
 [16]
 TienYien Li, Tim Sauer, and James A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Numer. Anal. 24 (1987), no. 2, 435451. MR 881375 (89e:90181), http://dx.doi.org/10.1137/0724032
 [17]
 Pavol Meravý, Symmetric homotopies for solving systems of polynomial equations, Math. Slovaca 39 (1989), no. 3, 277288 (English, with Russian summary). MR 1016345 (91d:65074)
 [18]
 Alexander Morgan and Andrew Sommese, Computing all solutions to polynomial systems using homotopy continuation, Appl. Math. Comput. 24 (1987), no. 2, 115138. MR 914807 (89b:65126), http://dx.doi.org/10.1016/00963003(87)900646
 [19]
 Alexander Morgan and Andrew Sommese, A homotopy for solving general polynomial systems that respects homogeneous structures, Appl. Math. Comput. 24 (1987), no. 2, 101113. MR 914806 (88j:65110), http://dx.doi.org/10.1016/00963003(87)900634
 [20]
 Alexander P. Morgan, A homotopy for solving polynomial systems, Appl. Math. Comput. 18 (1986), no. 1, 8792. MR 815774 (87c:90194), http://dx.doi.org/10.1016/00963003(86)900305
 [21]
 Alexander P. Morgan and Andrew J. Sommese, Coefficientparameter polynomial continuation, Appl. Math. Comput. 29 (1989), no. 2, 123160. MR 977815 (90f:58018), http://dx.doi.org/10.1016/00963003(89)900994
 [22]
 Alexander P. Morgan and Andrew J. Sommese, Coefficientparameter polynomial continuation, Appl. Math. Comput. 29 (1989), no. 2, 123160. MR 977815 (90f:58018), http://dx.doi.org/10.1016/00963003(89)900994
 [23]
 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, 797827. MR 1442939 (98g:65050), http://dx.doi.org/10.1137/S0036142995281504
 [24]
 Jan Verschelde, Algorithm 795: Phcpack: A generalpurpose solver for polynomial systems by homotopy continuation, 25 (1999), no. 2, 251276.
 [25]
 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, 225239. MR 1115067 (92c:65068), http://dx.doi.org/10.1016/00963003(91)90059V
 [26]
 Jan Verschelde and Ronald Cools, Symmetric homotopy construction, Proceedings of the Fifth International Congress on Computational and Applied Mathematics (Leuven, 1992), 1994, pp. 575592. MR 1284290 (95j:65056), http://dx.doi.org/10.1016/03770427(94)903298
 [27]
 Jan Verschelde and Karin Gatermann, Symmetric Newton polytopes for solving sparse polynomial systems, Adv. in Appl. Math. 16 (1995), no. 1, 95127. MR 1317613 (95m:65101), http://dx.doi.org/10.1006/aama.1995.1005
 [28]
 Jan Verschelde and Ann Haegemans, The algorithm for constructing start systems of homotopies for polynomial systems, SIAM J. Numer. Anal. 30 (1993), no. 2, 583594. MR 1211406 (94b:65075), http://dx.doi.org/10.1137/0730028
 [29]
 Jan Verschelde, Pierre Verlinden, and Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31 (1994), no. 3, 915930. MR 1275120 (94m:65084), http://dx.doi.org/10.1137/0731049
 [30]
 Alden H. Wright, Finding all solutions to a system of polynomial equations, Math. Comp. 44 (1985), no. 169, 125133. MR 771035 (86i:12001), http://dx.doi.org/10.2307/2007797
 [31]
 Bo Yu and Bo Dong, A hybrid polynomial system solving method for mixed trigonometric polynomial systems, SIAM J. Numer. Anal. 46 (2008), no. 3, 15031518. MR 2391004 (2009b:65133), http://dx.doi.org/10.1137/070681740
 [32]
 Bo Yu and Guo Chen Feng, The random product homotopy for solving polynomial systems in , Computer mathematics (Tianjin, 1991) Nankai Ser. Pure Appl. Math. Theoret. Phys., vol. 5, World Sci. Publ., River Edge, NJ, 1993, pp. 3645. MR 1257442 (95c:65080)
 [33]
 Walter Zulehner, A simple homotopy method for determining all isolated solutions to polynomial systems, Math. Comp. 50 (1988), no. 181, 167177. MR 917824 (89b:65130), http://dx.doi.org/10.2307/2007920
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
13P15,
65H20,
65H10,
14Q99,
68W30
Retrieve articles in all journals
with MSC (2010):
13P15,
65H20,
65H10,
14Q99,
68W30
Additional Information
Bo Dong
Affiliation:
School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning 116024, People’s Republic of China
Email:
dongbo@dlut.edu.cn
Bo Yu
Affiliation:
School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning 116024, People’s Republic of China
Email:
yubo@dlut.edu.cn
Yan Yu
Affiliation:
Faculty of Sciences, Shenyang Agricultural University, Shenyang, Liaoning, 110866, People’s Republic of China
Email:
yuyan1015@syau.edu.cn
DOI:
http://dx.doi.org/10.1090/S002557182013027639
Keywords:
Mixed trigonometric polynomial system,
polynomial system,
symmetry,
homotopy method,
hybrid algorithm,
symbolicnumeric computation
Received by editor(s):
October 21, 2011
Received by editor(s) in revised form:
July 3, 2012
Published electronically:
November 7, 2013
Additional Notes:
The first author was supported in part by the National Natural Science Foundation of China (Grant No. 11101067), TianYuan Special Funds of the National Natural Science Foundation of China (Grant No. 11026164) and the Fundamental Research Funds for the Central Universities
The second author’s research was supported by Major Research Plan of the National Natural Science Foundation of China (Grant No. 91230103) and the National Natural Science Foundation of China (Grant No. 11171051)
Article copyright:
© Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
