License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1351
URN: urn:nbn:de:0030-drops-13516
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1351/
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
fixed-point 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
non-negative solution of a given MSPE $vec X = vec f(vec X)$
arises naturally in the analysis of stochastic models such as
stochastic context-free grammars, probabilistic pushdown automata,
and back-button 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 fixed-point $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
back-button 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 = {289--300},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-06-4},
ISSN = {1868-8969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1351},
URN = {urn:nbn:de:0030-drops-13516},
doi = {10.4230/LIPIcs.STACS.2008.1351},
annote = {Keywords: Newton's Method, Fixed-Point Equations, Formal Verification of Software, Probabilistic Pushdown Systems}
}
Keywords: |
|
Newton's Method, Fixed-Point Equations, Formal Verification of Software, Probabilistic Pushdown Systems |
Collection: |
|
25th International Symposium on Theoretical Aspects of Computer Science |
Issue Date: |
|
2008 |
Date of publication: |
|
06.02.2008 |