zbMATH — the first resource for mathematics

Clustering complex zeros of triangular systems of polynomials. (English) Zbl 07363378
Summary: This paper gives the first algorithm for finding a set of natural \(\epsilon\)-clusters of complex zeros of a regular triangular system of polynomials within a given polybox in \({\mathbb{C}}^n\), for any given \(\epsilon >0\). Our algorithm is based on a recent near-optimal algorithm of Becker et al. (Proceedings of the ACM on international symposium on symbolic and algebraic computation, 2016) for clustering the complex roots of a univariate polynomial where the coefficients are represented by number oracles. Our algorithm is based on recursive subdivision. It is local, numeric, certified and handles solutions with multiplicity. Our implementation is compared to with well-known homotopy solvers on various triangular systems. Our solver always gives correct answers, is often faster than the homotopy solvers that often give correct answers, and sometimes faster than the ones that give sometimes correct results.
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)
Full Text: DOI
[1] Aubry, P.; Lazard, D.; Maza, MM, On the theories of triangular sets, J. Symb. Comput., 28, 1, 105-124 (1999) · Zbl 0943.12003
[2] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Bertini: Software for numerical algebraic geometry. Available at bertini.nd.edu with permanent doi:10.7274/R0H41PB5 · Zbl 1143.65344
[3] Batra, P., Globally convergent, iterative path-following for algebraic equations, Math. Comput. Sci., 4, 4, 507-537 (2010) · Zbl 1229.65076
[4] Becker, R., Sagraloff, M., Sharma, V., Xu, J., Yap, C.: Complexity analysis of root clustering for a complex polynomial. In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. pp. 71-78. ISSAC ’16, ACM, New York, NY, USA (2016) · Zbl 1364.30011
[5] Becker, R.; Sagraloff, M.; Sharma, V.; Yap, C., A near-optimal subdivision algorithm for complex root isolation based on Pellet test and Newton iteration, J. Symb. Comput., 86, 51-96 (2018) · Zbl 1383.65043
[6] Beltrán, C.; Leykin, A., Certified numerical homotopy tracking, Exp. Math., 21, 1, 69-83 (2012) · Zbl 1238.14048
[7] Boulier, F.; Chen, C.; Lemaire, F.; Moreno Maza, M.; Feng, R.; Lee, WS; Sato, Y., Real root isolation of regular chains, Computer Mathematics, 33-48 (2014), Berlin: Springer, Berlin · Zbl 1336.65079
[8] Cheng, JS; Gao, XS; Yap, CK, Complete numerical isolation of real roots in zero-dimensional triangular systems, J. Symb. Comput., 44, 7, 768-785 (2009) · Zbl 1169.13017
[9] Collins, GE; Johnson, JR; Krandick, W., Interval arithmetic in cylindrical algebraic decomposition, J. Symb. Comput., 34, 2, 145-157 (2002) · Zbl 1007.68210
[10] Dahan, X., Maza, M.M., Schost, E., Wu, W., Xie, Y.: Lifting techniques for triangular decompositions. In: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pp. 108-115. ISSAC ’05, ACM, New York, NY, USA (2005) · Zbl 1360.14146
[11] Darboux, G.: Sur les développements en série des fonctions d’une seule variable. Journal de mathématiques pures et appliquées (Liouville Journal) 3(II), 291-312 (1876) · JFM 08.0124.03
[12] Dayton, B.H., Zeng, Z.: Computing the multiplicity structure in solving polynomial systems. In: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pp. 116-123. ACM (2005) · Zbl 1360.65151
[13] Dickenstein, A.; Emiris, I., Solving Polynomial Equations: Foundations, Algorithms, and Applications (2005), Berlin: Springer, Berlin · Zbl 1061.12001
[14] Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A descartes algorithm for polynomials with bit-stream coefficients. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds.) CASC, LNCS, vol. 3718, pp. 138-149. Springer, Berlin (2005) · Zbl 1169.65315
[15] Giusti, M.; Lecerf, G.; Salvy, B.; Yakoubsohn, JC, On location and approximation of clusters of zeros: case of embedding dimension one, Found. Comput. Math., 7, 1, 1-58 (2007) · Zbl 1124.65047
[16] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 212, 1541-1555 (1995) · Zbl 0849.65030
[17] Imbach, R., Pan, V.Y., Yap, C.: Implementation of a near-optimal complex root clustering algorithm. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) Mathematical Software—ICMS 2018, pp. 235-244. Springer, Cham (2018) · Zbl 1398.65095
[18] Johansson, F., Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput., 66, 1281-1292 (2017) · Zbl 1388.65037
[19] Kobel, A., Rouillier, F., Sagraloff, M.: Computing real roots of real polynomials ... and now for real! In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp. 303-310. ISSAC ’16, ACM, New York, NY, USA (2016) · Zbl 1365.65142
[20] Li, J., Cheng, J., Tsigaridas, E.: Local generic position for root isolation of zero-dimensional triangular polynomial systems. In: Koepf, W., Vorozhtsov, E. (eds.) CASC 2012—14th International Workshop on Computer Algebra in Scientific Computing. Lecture Notes in Computer Science, vol. 7442, pp. 186-197. Springer, Maribor (2012) · Zbl 1416.65132
[21] Mignotte, M., On the distance between the roots of a polynomial, Appl. Algebra Eng. Commun. Comput., 6, 6, 327-332 (1995) · Zbl 0835.12002
[22] Moore, RE; Kearfott, RB; Cloud, MJ, Introduction to Interval Analysis (2009), Philadelphia: SIAM, Philadelphia · Zbl 1168.65002
[23] Niang Diatta, D., Diatta, S., Rouillier, F., Roy, M.F., Sagraloff, M.: Bounds for polynomials on algebraic numbers and application to curve topology. arXiv e-prints arXiv:1807.10622 (Jul 2018)
[24] Strzebonski, A.; Tsigaridas, E., Univariate real root isolation in an extension field and applications, J. Symb. Comput., 92, 31-51 (2019) · Zbl 1408.68148
[25] Wampler, ICW, The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), Singapore: World Scientific, Singapore · Zbl 1091.65049
[26] Xu, J., Burr, M., Yap, C.: An approach for certifying homotopy continuation paths: Univariate case. In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pp. 399-406. ISSAC ’18, ACM, New York, NY, USA (2018) · Zbl 1467.65056
[27] Yap, C., Sagraloff, M., Sharma, V.: Analytic root clustering: a complete algorithm using soft zero tests. In: The Nature of Computation. Logic, Algorithms, Applications. LNCS, vol. 7921, pp. 434-444. Springer, Berlin (2013) · Zbl 1416.65068
[28] Zhang, Z.; Fang, T.; Xia, B., Real solution isolation with multiplicity of zero-dimensional triangular systems, Sci. China Inf. Sci., 54, 1, 60-69 (2011) · Zbl 1218.65046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.