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/
Go to the corresponding LIPIcs Volume Portal

Esparza, Javier ; Kiefer, Stefan ; Luttenberger, Michael

Convergence Thresholds of Newton's Method for Monotone Polynomial Equations

pdf-format:
22011.EsparzaJavier.Paper.1351.pdf (0.2 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI