Esparza, Javier ;
Kiefer, Stefan ;
Luttenberger, Michael
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
Abstract
Monotone systems of polynomial equations (MSPEs) are systems of
fixedpoint equations $X_1 = f_1(X_1, ldots, X_n),$ $ldots, X_n =
f_n(X_1, ldots, X_n)$ where each $f_i$ is a polynomial with
positive real coefficients. The question of computing the least
nonnegative solution of a given MSPE $vec X = vec f(vec X)$
arises naturally in the analysis of stochastic models such as
stochastic contextfree grammars, probabilistic pushdown automata,
and backbutton processes. Etessami and Yannakakis have recently
adapted Newton's iterative method to MSPEs. In a previous paper we
have proved the existence of a threshold $k_{vec f}$ for strongly
connected MSPEs, such that after $k_{vec f}$ iterations of
Newton's method each new iteration computes at least 1 new bit of
the solution. However, the proof was purely existential. In this
paper we give an upper bound for $k_{vec f}$ as a function of the
minimal component of the least fixedpoint $muvec f$ of $vec
f(vec X)$. Using this result we show that $k_{vec f}$ is at most
single exponential resp. linear for strongly connected MSPEs
derived from probabilistic pushdown automata resp. from
backbutton processes. Further, we prove the existence of a
threshold for arbitrary MSPEs after which each new iteration
computes at least $1/w2^h$ new bits of the solution, where $w$ and
$h$ are the width and height of the DAG of strongly connected
components.
BibTeX  Entry
@InProceedings{esparza_et_al:LIPIcs:2008:1351,
author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
title = {{Convergence Thresholds of Newton's Method for Monotone Polynomial Equations}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {289300},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1351},
URN = {urn:nbn:de:0030drops13516},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1351},
annote = {Keywords: Newton's Method, FixedPoint Equations, Formal Verification of Software, Probabilistic Pushdown Systems}
}
Keywords: 

Newton's Method, FixedPoint Equations, Formal Verification of Software, Probabilistic Pushdown Systems 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2008 
Date of publication: 

06.02.2008 