{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:08Z","timestamp":1787340488371,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We consider equation systems of the form $X_1=f_1(X_1,\\dots,X_n)$, $\\dots$, $X_n = f_n(X_1,\\dots,X_n)$, where $f_1,\\dots,f_n$ are polynomials with positive real coefficients. In vector form we denote such an equation system by ${\\bf X}={\\bf f}({\\bf X})$ and call ${\\bf f}$ a system of positive polynomials (SPP). Equation systems of this kind appear naturally in the analysis of stochastic models like stochastic context-free grammars (with numerous applications to natural language processing and computational biology), probabilistic programs with procedures, web-surfing models with back buttons, and branching processes. The least nonnegative solution $\\mu{\\bf f}$ of an SPP equation ${\\bf X}={\\bf f}({\\bf X})$ is of central interest for these models. Etessami and Yannakakis [J. ACM, 56 (2009), pp. 1\u201366] have suggested a particular version of Newton's method to approximate $\\mu{\\bf f}$. We extend a result of Etessami and Yannakakis and show that Newton's method starting at ${\\bf 0}$ always converges to $\\mu{\\bf f}$. We obtain lower bounds on the convergence speed of the method. For so-called strongly connected SPPs we prove the existence of a threshold $k_{{\\bf f}}\\in\\mathbb{N}$ such that for every $i\\geq0$ the $(k_{{\\bf f}}+i)$th iteration of Newton's method has at least i valid bits of $\\mu{\\bf f}$. The proof yields an explicit bound for $k_{{\\bf f}}$ depending only on syntactic parameters of ${\\bf f}$. We further show that for arbitrary SPP equations, Newton's method still converges linearly: there exists a threshold $k_{{\\bf f}}$ and an $\\alpha_{{\\bf f}}&gt;0$ such that for every $i\\geq0$ the $(k_{{\\bf f}}+\\alpha_{{\\bf f}}\\cdot i)$th iteration of Newton's method has at least i valid bits of $\\mu{\\bf f}$. The proof yields an explicit bound for $\\alpha_{{\\bf f}}$; the bound is exponential in the number of equations in ${\\bf X}={\\bf f}({\\bf X})$, but we also show that it is essentially optimal. The proof does not yield any bound for $k_{{\\bf f}}$, but only proves its existence. Constructing a bound for $k_{{\\bf f}}$ is still an open problem. Finally, we also provide a geometric interpretation of Newton's method for SPPs.<\/jats:p>","DOI":"10.1137\/090749591","type":"journal-article","created":{"date-parts":[[2010,3,26]],"date-time":"2010-03-26T18:24:06Z","timestamp":1269627846000},"page":"2282-2335","source":"Crossref","is-referenced-by-count":18,"title":["Computing the Least Fixed Point of Positive Polynomial Systems"],"prefix":"10.1137","volume":"39","author":[{"given":"Javier","family":"Esparza","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kiefer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Luttenberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,3,26]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"K. Athreya and P. Ney,\n                      Branching Processes\n                      , Springer-Verlag, New York, 1972.","DOI":"10.1007\/978-3-642-65371-1"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Berman and R. Plemmons,\n                      Nonnegative Matrices in the Mathematical Sciences\n                      , Academic Press, New York, 1979.","DOI":"10.1016\/B978-0-12-092250-5.50009-6"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"T. Br\u00e1zdil, A. Ku\u010dera, and O. Stra\u017eovsk\u00fd,\n                      On the decidability of temporal properties of probabilistic pushdown automata\n                      , in Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS'2005), Lecture Notes in Comput. Sci. 3404, Springer-Verlag, Berlin, 2005, pp. 145\u2013157.","DOI":"10.1007\/978-3-540-31856-9_12"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0717009"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-5-71"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"R. Durbin, S. Eddy, A. Krogh, and G. Michison,\n                      Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids\n                      , Cambridge University Press, Cambridge, UK, 1998.","DOI":"10.1017\/CBO9780511790492"},{"key":"R8","unstructured":"J. Esparza, A. Gaiser, and S. Kiefer,\n                      Computing least fixed points of probabilistic systems of polynomials\n                      , in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'2010), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2010, pp. 359\u2013370."},{"key":"R9","unstructured":"J. Esparza, S. Kiefer, and M. Luttenberger,\n                      Convergence thresholds of Newton's method for monotone polynomial equations\n                      , in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'2008), 2008, pp. 289\u2013300."},{"key":"R10","unstructured":"J. Esparza, S. Kiefer, and M. Luttenberger,\n                      Computing the Least Fixed Point of Positive Polynomial Systems\n                      , Technical report, Technische Universit\u00e4t M\u00fcnchen, 2010; available online at http:\/\/arxiv.org\/abs\/1001.0340."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Esparza, A. Ku\u010dera, and R. Mayr,\n                      Model-checking probabilistic pushdown automata\n                      , in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE Computer Society Press, Los Alamitos, CA, 2004, pp. 12\u201321.","DOI":"10.1109\/LICS.2004.1319596"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Esparza, A. Ku\u010dera, and R. Mayr,\n                      Quantitative analysis of probabilistic pushdown automata: Expectations and variances\n                      , in Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), IEEE Computer Society Press, Los Alamitos, CA, 2005, pp. 117\u2013126.","DOI":"10.1109\/LICS.2005.39"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"K. Etessami and M. Yannakakis,\n                      Algorithmic verification of recursive probabilistic systems\n                      , in Proceedings of the 11th International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS 2005), Lecture Notes in Comput. Sci. 3440, Springer-Verlag, Berlin, 2005, pp. 253\u2013270.","DOI":"10.1007\/978-3-540-31980-1_17"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"K. Etessami and M. Yannakakis,\n                      Checking LTL properties of recursive Markov chains\n                      , in Proceedings of the 2nd International Conference on Quantitative Evaluation of Systems (QEST'05), IEEE Computer Society Press, Washington, DC, 2005, pp. 155\u2013165.","DOI":"10.1109\/QEST.2005.8"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"K. Etessami and M. Yannakakis,\n                      Recursive Markov decision processes and recursive stochastic games\n                      , in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), Lecture Notes in Comput. Sci. 3580, Springer-Verlag, Berlin, 2005, pp. 891\u2013903.","DOI":"10.1007\/11523468_72"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins,\n                      Random walks with \u201cback buttons\u201d (extended abstract)\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), ACM, New York, 2000, pp. 484\u2013493.","DOI":"10.1145\/335305.335362"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1015345350"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. Geman and M. Johnson,\n                      Probabilistic Grammars and Their Applications\n                      , in International Encyclopedia of the Social & Behavioral Sciences, N. J. Smelser and P. B. Baltes, eds., Pergamon, Oxford, 2002, pp. 12075\u201312082.","DOI":"10.1016\/B0-08-043076-7\/00489-7"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0718011"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"T. Harris,\n                      The Theory of Branching Processes\n                      , Springer-Verlag, Berlin, 1963.","DOI":"10.1007\/978-3-642-51866-9"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. Horn and C. Johnson,\n                      Topics in Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 1991.","DOI":"10.1017\/CBO9780511840371"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"C. T. Kelley,\n                      Iterative Methods for Linear and Nonlinear Equations\n                      , SIAM, Philadelphia, 1995.","DOI":"10.1137\/1.9781611970944"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"S. Kiefer, M. Luttenberger, and J. Esparza,\n                      On the convergence of Newton's method for monotone systems of polynomial equations\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), ACM, New York, 2007, pp. 217\u2013226.","DOI":"10.1145\/1250790.1250822"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg614"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"W. Kuich,\n                      Semirings and formal power series: Their relevance to formal languages and automata\n                      , in Handbook of Formal Languages, Vol. 1, Springer-Verlag, Berlin, 1997, Chap. 9, pp. 609\u2013677.","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"R27","unstructured":"P. Lancaster and M. Tismenetsky,\n                      The Theory of Matrices\n                      , 2nd ed., Academic Press, New York, 1985."},{"key":"R28","unstructured":"C. Manning and H. Sch\u00fctze,\n                      Foundations of Statistical Natural Language Processing\n                      , MIT Press, Cambridge, MA, 1999."},{"key":"R29","unstructured":"J. Ortega,\n                      Numerical Analysis: A Second Course\n                      , Academic Press, New York, 1972."},{"key":"R30","unstructured":"J. Ortega and W. Rheinboldt,\n                      Iterative Solution of Nonlinear Equations in Several Variables\n                      , Academic Press, New York, 1970."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463998"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0715064"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.23.5112"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"E. S\u00fcli and D. Mayers,\n                      An Introduction to Numerical Analysis\n                      , Cambridge University Press, Cambridge, UK, 2003.","DOI":"10.1017\/CBO9780511801181"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.2307\/2841222"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090749591","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:38Z","timestamp":1787337398000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090749591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090749591"],"URL":"https:\/\/doi.org\/10.1137\/090749591","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}