On the convergence of Newton's method for monotone systems of polynomial equations

ABSTRACT

Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations X₁ = f₁(X₁, ..., X_n), ..., X_n = f_n(X₁, ..., X_n) where each f_i is a polynomial with positive real coefficients. The question of computing the least non-negative solution of a given MSPE X = f(X) arises naturally in the analysis of stochastic context-free grammars, recursive Markov chains, and probabilistic pushdown automata. While the Kleene sequence f(0), f(f(0)), ... always converges to the least solution mu.f, if it exists, the number of iterations needed to compute the first i bits of mu.f may grow exponentially in i.Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs and proved that the Newton sequence converges at least as fast as the Kleene sequence and exponentially faster in many cases.They conjecture that, given an MSPE of size m, the number of Newton iterations needed to obtain i accurate bits of mu.f grows polynomially in i and m. In this paper we show that the number of iterations grows linearly in i for strongly connected MSPEs and may grow exponentially in m for general MSPEs.

REFERENCES

• 1: [1] T. Brázdil, A. Ku¿era, and O. Stra¿ovský. On the decidability of temporal properties of probabilistic pushdown automata. In Proceedings of STACS'2005, volume 3404 of LNCS, pages 145-157. Springer, 2005.
• 2: [2] D. W. Decker and C. T. Kelley. Newton's method at singular points I. SIAM Journal on Numerical Analysis, 17(1):66-70, 1980.
• 3: [3] R. D. Dowell and S. R. Eddy. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics, 5(71), 2004.
• 4: [4] R. Durbin, S. R. Eddy, A. Krogh, and G. J. Michison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.
• 5: [5] J. Esparza, S. Kiefer, and M. Luttenberger. On fixed point equations over commutative semirings. In Proceedings of STACS, LNCS 4397, pages 296-307, 2007.
• 6: Javier Esparza , Antonin Kucera , Richard Mayr, Model Checking Probabilistic Pushdown Automata, Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), p.12-21, July 13-17, 2004 [doi>10.1109/LICS.2004.23]
• 7: Javier Esparza , Antonin Kucera, Quantitative Analysis of Probabilistic Pushdown Automata: Expectations and Variances, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), p.117-126, June 26-29, 2005 [doi>10.1109/LICS.2005.39]
• 8: [8] K. Etessami and M. Yannakakis. Algorithmic verification of recursive probabilistic systems. In Proceedings of TACAS 2005, LNCS 3440, pages 253-270. Springer, 2005.
• 9: Mihalis Yannakakis , Kousha Etessami, Checking LTL Properties of Recursive Markov Chains, Proceedings of the Second International Conference on the Quantitative Evaluation of Systems (QEST'05) on The Quantitative Evaluation of Systems, p.155, September 19-22, 2005 [doi>10.1109/QEST.2005.8]
• 10: [10] K. Etessami and M. Yannakakis. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. In STACS, pages 340-352, 2005.
• 11: [11] K. Etessami and M. Yannakakis. Recursive Markov decision processes and recursive stochastic games. In Proceedings of ICALP 2005, volume 3580 of LNCS. Springer, 2005.
• 12: [12] K. Etessami and M. Yannakakis. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations, 2006. Draft journal submission, http://homepages. inf.ed.ac.uk/kousha/bib_index.html.
• 13: Ronald Fagin , Anna R. Karlin , Jon Kleinberg , Prabhakar Raghavan , Sridhar Rajagopalan , Ronitt Rubinfeld , Madhu Sudan , Andrew Tomkins, Random walks with “back buttons” (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.484-493, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335362]
• 14: [14] R. Fagin, A. R. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins. Random walks with "back buttons". Annals of Applied Probability, 11(3):810-862, 2001.
• 15: [15] S. Geman and M. Johnson. Probabilistic grammars and their applications, 2002.
• 16: [16] A. Griewank and M. R. Osborne. Newton's method for singular problems when the dimension of the null space is > 1. SIAM Journal on Numerical Analysis, 18(1):145-149, 1981.
• 17: [17] C. T. Kelley. Iterative Methods for Linear and Nonlinear Equations. SIAM, 1995.
• 18: [18] B. Knudsen and J. Hein. Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Research, 31(13):3423-3428, 2003.
• 19: Werner Kuich, Semirings and formal power series: their relevance to formal languages and automata, Handbook of formal languages, vol. 1: word, language, grammar, Springer-Verlag New York, Inc., New York, NY, 1997
• 20: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 21: [21] J. M. Ortega. Numerical Analysis: A Second Course. Academic Press, New York, 1972.
• 22: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 23: [23] F. A. Potra and V. Pták. Sharp error bounds for Newton's process. Numerische Mathematik, 34(1):63-72, 1980.
• 24: [24] G. W. Reddien. On Newton's method for singular problems. SIAM Journal on Numerical Analysis, 15:993-996, 1978.
• 25: [25] Y. Sakabikara, M. Brown, R. Hughey, I. S. Mian, K. Sjolander, R. C. Underwood, and D. Haussler. Stochastic context-free grammars for tRNA. Nucleic Acids Research, 22:5112-5120, 1994.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Convergence

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations; Iterative methods; Polynomials, methods for

General Terms:
Algorithms, Theory, Verification

Keywords:
Newton's method, fixed-point equations, formal verification of software, probabilistic pushdown systems