Computing the least fixed point of positive polynomial systems

DOI10.1137/090749591MaRDI QIDQ3068634zbMATH OpenOpenAlexFDO

Authors Javier Esparza, Stefan Kiefer, Michael Luttenberger

Publication date 17 January 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/090749591

zbMATH Keywords

convergence speedfixed-point equationsNewton's methodnumerical analysispolynomial equations

Mathematics Subject Classification ID

Rate of convergence, degree of approximation (41A25) Numerical computation of solutions to systems of equations (65H10) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• COMPUTING LEAST FIXED POINTS OF PROBABILISTIC SYSTEMS OF POLYNOMIALS
• Convergence thresholds of Newton's method for monotone polynomial equations
• Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• ON NEWTON'S METHOD FOR SOLVING A SYSTEM OF NONLINEAR MATRIX EQUATIONS

Cited in

(15)

• Multiplicative updates for polynomial root finding
• Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs
• Computing real witness points of positive dimensional polynomial systems
• Recursive Markov decision processes and recursive stochastic games
• On probabilistic parallel programs with process creation and synchronisation
• Runtime analysis of probabilistic programs with unbounded recursion
• COMPUTING LEAST FIXED POINTS OF PROBABILISTIC SYSTEMS OF POLYNOMIALS
• Upper bounds for Newton's method on monotone polynomial systems, and P-time model checking of probabilistic one-counter automata
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• Convergence thresholds of Newton's method for monotone polynomial equations
• A convex programming approach to solve posynomial systems
• Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations
• A polynomial time algorithm for computing extinction probabilities of multitype branching processes
• Certificates for probabilistic pushdown automata via optimistic value iteration
• Runtime analysis of probabilistic programs with unbounded recursion

Describes a project that uses

Uses Software

• KELLEY

This page was built for publication: Computing the least fixed point of positive polynomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068634)