Convergence Thresholds of Newton's Method for Monotone Polynomial Equations

Details Convergence Thresholds of Newton's Method for Monotone Polynomial Equations Convergence Thresholds of Newton's Method for Monotone Polynomial Equations

2008-02-20

arxiv.org/abs/0802.2856v2

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Data Structures and Algorithms

version 2 deposited February 29, after the end of the STACS conference. Two minor mistakes corrected

Scientific paper

Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations $X_1 = f_1(X_1, ..., X_n),$ $..., X_n = f_n(X_1, ..., 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 $\mu\vec 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.

Affiliated with

Also associated with

No associations

Rating

Convergence Thresholds of Newton's Method for Monotone Polynomial Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convergence Thresholds of Newton's Method for Monotone Polynomial Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence Thresholds of Newton's Method for Monotone Polynomial Equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647842