English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Monotone systems of polynomial equations (MSPEs) are systems of fixed-pointequations $X_1 = f_1(X_1, ..., X_n),$ $..., X_n = f_n(X_1, ..., X_n)$ whereeach $f_i$ is a polynomial with positive real coefficients. The question ofcomputing the least non-negative solution of a given MSPE $\vec X = \vec f(\vecX)$ arises naturally in the analysis of stochastic models such as stochasticcontext-free grammars, probabilistic pushdown automata, and back-buttonprocesses. Etessami and Yannakakis have recently adapted Newton's iterativemethod to MSPEs. In a previous paper we have proved the existence of athreshold $k_{\vec f}$ for strongly connected MSPEs, such that after $k_{\vecf}$ iterations of Newton's method each new iteration computes at least 1 newbit of the solution. However, the proof was purely existential. In this paperwe give an upper bound for $k_{\vec f}$ as a function of the minimal componentof the least fixed-point $\mu\vec f$ of $\vec f(\vec X)$. Using this result weshow that $k_{\vec f}$ is at most single exponential resp. linear for stronglyconnected MSPEs derived from probabilistic pushdown automata resp. fromback-button processes. Further, we prove the existence of a threshold forarbitrary MSPEs after which each new iteration computes at least $1/w2^h$ newbits of the solution, where $w$ and $h$ are the width and height of the DAG ofstrongly connected components.

Convergence Thresholds of Newton's Method for Monotone Polynomial Equations