×

Positive root isolation for poly-powers by exclusion and differentiation. (English) Zbl 1378.68200

Summary: We consider a class of univariate real functions – \(\mathsf{poly-powers}\) – that extend integer exponents to real algebraic exponents for polynomials. Our purpose is to isolate positive roots of such a function into disjoint intervals, each contains exactly one positive root and together contain all, which can be easily refined to any desired precision. To this end, we first classify \(\mathsf{poly-powers}\) into simple and non-simple ones, depending on the number of linearly independent exponents. For the former, based on Gelfond-Schneider theorem, we present two complete isolation algorithms – exclusion and differentiation. For the latter, their completeness depends on Schanuel’s conjecture. We implement the two methods and compare them in efficiency via a few examples. Finally the proposed methods are applied to the field of systems biology to show the practical usefulness.

MSC:

68W30 Symbolic computation and algebraic computation
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
92C42 Systems biology, networks

Software:

REACH; ISOLATE; QEPCAD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achatz, M.; McCallum, S.; Weispfenning, V., Deciding polynomial-exponential problems, (Sendra, J. R.; González-Vega, L., Proc. ISSAC 2008 (2008), ACM), 215-222 · Zbl 1236.68301
[2] Anai, H.; Weispfenning, V., Reach set computations using real quantifier elimination, (Benedetto, M. D.D.; Sangiovanni-Vincentelli, A., Proc. HSCC 2001. Proc. HSCC 2001, Lect. Notes Comput. Sci., vol. 2034 (2001), Springer), 63-76 · Zbl 0991.93008
[3] Ax, J., On Schanuel’s conjectures, Ann. Math., 93, 2, 252-268 (1971) · Zbl 0232.10026
[4] Bak, J.; Leviatan, D.; Newman, D. J.; Tzimbalario, J., Generalized polynomial approximation, Isr. J. Math., 15, 4, 337-349 (1973) · Zbl 0273.41004
[5] Becker, R.; Sagraloff, M.; Sharma, V.; Xu, J.; Yap, C., Complexity analysis of root clustering for a complex polynomial, (Abramov, S. A.; Zima, E. V.; Gao, X.-S., Proc. ISSAC 2016 (2016), ACM), 71-78 · Zbl 1364.30011
[6] Cheng, J.-S.; Gao, X.-S.; Yap, C.-K., Complete numerical isolation of real zeros in zero-dimensional triangular systems, (Brown, C. W., Proc. ISSAC 2007 (2007), ACM), 92-99 · Zbl 1190.65082
[7] Chonev, V.; Ouaknine, J.; Worrell, J., On the Skolem problem for continuous linear dynamical systems, (Chatzigiannakis, I.; Mitzenmacher, M.; Rabani, Y.; Sangiorgi, D., Proc. ICALP 2016. Proc. ICALP 2016, LIPIcs, vol. 55 (2016), Schloss Dagstuhl), 100:1-100:13 · Zbl 1388.68043
[8] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, (Brakhage, H., Proc. 2nd GI Conference on Automata Theory and Formal Languages. Proc. 2nd GI Conference on Automata Theory and Formal Languages, Lect. Notes Comput. Sci., vol. 33 (1975), Springer), 134-183
[9] Collins, G. E.; Akritas, A. G., Polynomial real root isolation using Descarte’s rule of signs, (Proc. SYMSAC 1976 (1976), ACM), 272-275
[10] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. Symb. Comput., 12, 3, 299-328 (1991) · Zbl 0754.68063
[11] Collins, G. E.; Loos, R., Polynomial real root isolation by differentiation, (Proc. SYMSAC 1976 (1976), ACM), 15-25 · Zbl 0454.65036
[12] Coste, M.; Lajous-Loaeza, T.; Lombardic, H.; Roy, M.-F., Generalized Budan-Fourier theorem and virtual roots, J. Complex., 21, 4, 479-486 (2005) · Zbl 1106.12001
[13] Coste, M.; Roy, M. F., Thom’s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symb. Comput., 5, 1-2, 121-129 (1988) · Zbl 0689.14006
[14] Cucker, F.; Smale, S., Complexity estimates depending on condition and round-off error, J. ACM, 46, 1, 113-184 (1999) · Zbl 1065.68533
[15] Dedieu, J.-P.; Yakoubsohn, J.-C., Computing the real roots of a polynomial by the exclusion algorithm, Numer. Algorithms, 4, 1, 1-24 (1993) · Zbl 0774.65028
[16] Gupta, A.; Kamath, P.; Kayal, N.; Saptharishi, R., Approaching the chasm at depth four, (Proc. CCC 2013 (2013), IEEE Computer Society), 65-73
[17] Gustafson, G. B., Systems of Differential Equations (1998), Available at · Zbl 0261.34023
[18] Kailath, T., Linear Systems (1980), Prentice Hall · Zbl 0458.93025
[19] Lafferriere, G.; Pappas, G. J.; Yovine, S., Symbolic reachability computation for families of linear vector fields, J. Symb. Comput., 32, 3, 231-253 (2001) · Zbl 0983.93004
[20] Li, J.-C.; Huang, C.-C.; Xu, M.; Li, Z.-B., Positive root isolation for poly-powers, (Abramov, S. A.; Zima, E. V.; Gao, X.-S., Proc. ISSAC 2016 (2016), ACM), 325-332 · Zbl 1365.65143
[21] Loos, R., Computing in algebraic extensions, (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra: Symbolic and Algebraic Computation (1983), Springer), 173-187
[22] McCallum, S.; Weispfenning, V., Deciding polynomial-transcendental problems, J. Symb. Comput., 47, 1, 16-31 (2012) · Zbl 1243.03015
[23] Mignotte, M., Some useful bounds, (Buchberger, B.; Collins, G. E.; Loos, R., Computer Algebra: Symbolic and Algebraic Computation (1983), Springer), 259-263
[24] Newton, I., De analysi per aequationes numero terminorum infinitas (1711), William Jones
[25] Pan, V. Y., Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, J. Symb. Comput., 33, 5, 701-733 (2002) · Zbl 1004.65061
[26] Pan, V. Y.; Tsigaridas, E. P., Nearly optimal refinement of real roots of a univariate polynomial, J. Symb. Comput., 74, 181-204 (2016) · Zbl 1329.65096
[27] Richardson, D., Towards computing non algebraic cylindrical decompositions, (Watt, S. M., Proc. ISSAC 1991 (1991), ACM), 247-255 · Zbl 0925.65091
[28] Richardson, D., How to recognize zero, J. Symb. Comput., 24, 6, 627-645 (1997) · Zbl 0917.11062
[29] Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008
[30] Sagraloff, M.; Mehlhorn, K., Computing real roots of real polynomials, J. Symb. Comput., 73, 46-86 (2016) · Zbl 1330.65072
[31] Siegel, C. L., Transcendental Numbers (1949), Princeton University Press · Zbl 0039.04402
[32] Smale, S., Newton’s method estimates from data at one point, (Ewing, R. E.; Gross, K. I.; Martin, C. F., The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (1986), Springer), 185-196
[33] Strzeboński, A., Real root isolation for exp-log functions, (Sendra, J. R.; González-Vega, L., Proc. ISSAC 2008 (2008), ACM), 303-313 · Zbl 1236.65057
[34] Strzeboński, A., Real root isolation for tame elementary functions, (Johnson, J. R.; Park, H.; Kaltofen, E., Proc. ISSAC 2009 (2009), ACM), 341-350 · Zbl 1237.33015
[35] Strzeboński, A., Cylindrical decomposition for systems transcendental in the first variable, J. Symb. Comput., 46, 11, 1284-1290 (2011) · Zbl 1236.14053
[36] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), University of California Press · Zbl 0044.25102
[37] Thomas, J. M., Sturm’s theorem for multiple roots, Natl. Math. Mag., 15, 8, 391-394 (1941) · JFM 67.0064.03
[38] van der Waerden, B. L., Algebra I (1991), Springer · Zbl 0724.12001
[39] Xia, B.; Yang, L., An algorithm for isolating the real solutions of semi-algebraic systems, J. Symb. Comput., 34, 5, 461-477 (2002) · Zbl 1027.68150
[40] Xu, M.; Chen, L.; Zeng, Z.; Li, Z.-B., Reachability analysis of rational eigenvalue linear systems, Int. J. Syst. Sci., 41, 12, 1411-1419 (2010) · Zbl 1206.93013
[41] Xu, M.; Li, Z.-B.; Yang, L., Quantifier elimination for a class of exponential polynomial formulas, J. Symb. Comput., 68, 1, 146-168 (2015) · Zbl 1382.03056
[42] Xu, M.; Mu, C.; Zeng, Z.; Li, Z.-B., A heuristic approach to positive root isolation for multiple power sums, J. Univers. Comput. Sci., 16, 14, 1912-1926 (2010) · Zbl 1216.68349
[43] Xu, M.; Zhu, J.; Li, Z.-B., Some decidable results on reachability of solvable systems, Int. J. Gen. Syst., 42, 4, 405-425 (2013) · Zbl 1278.93046
[44] Yang, L., Solving harder problems with lesser mathematics, (Proc. 10th Asian Technology Conference in Mathematics (2005), ATCM Inc.), 37-46
[45] Yap, C.; Sagraloff, M.; Sharma, V., Analytic root clustering: a complete algorithm using soft zero tests, (Bonizzoni, P.; Brattka, V.; Löwe, B., Proc. CiE 2013. Proc. CiE 2013, Lect. Notes Comput. Sci., vol. 7921 (2013), Springer), 433-444 · Zbl 1416.65068
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.