Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Computing the Least Fixed Point of Positive Polynomial Systems

Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Computing the least fixed point of positive polynomial systems. Technical report, Technische Universität München, Institut für Informatik, April 2009.

Abstract:

We consider equation systems of the form X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., X_n) where f_1, ..., f_n are polynomials with positive real coefficients. In vector form we denote such an equation system by X = f(X) and call f a system of positive polynomials, short 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 f of an SPP equation X = f(X) is of central interest for these models. Etessami and Yannakakis have suggested a particular version of Newton's method to approximate mu f. We extend a result of Etessami and Yannakakis and show that Newton's method starting at 0 always converges to mu f. We obtain lower bounds on the convergence speed of Newton's method and prove that for so-called strongly connected SPPs there exists a threshold k_f such that for every i >= 0 the (k_f+i)-th iteration of Newton's method has at least i valid bits of mu f. We also provide concrete bounds on k_f. Further we show that Newton's method for arbitrary SPP equations also converges linearly, albeit the convergence rate, i.e., the number of bits obtained per iteration, is poorer. We prove bounds on the convergence rate, which we show to be essentially tight. Finally, we also provide a geometric interpretation of Newton's method for SPPs.

Suggested BibTeX entry:

@techreport{EKL09:newtReal,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {April},
    title = {Computing the Least Fixed Point of Positive Polynomial Systems},
    year = {2009}
}

PDF (902 kB)