Overdetermined Weierstrass iteration and the nearest consistent system
From MaRDI portal
Publication:476879
DOI10.1016/J.TCS.2014.10.008zbMATH Open1310.65044arXiv1401.5086OpenAlexW2055130031WikidataQ57438842 ScholiaQ57438842MaRDI QIDQ476879FDOQ476879
Authors: Olivier Ruatta, Mark Sciabica, Agnes Szanto 
Publication date: 2 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: We propose a generalization of the Weierstrass iteration for over-constrained systems of equations and we prove that the proposed method is the Gauss-Newton iteration to find the nearest system which has at least common roots and which is obtained via a perturbation of prescribed structure. In the univariate case we show the connection of our method to the optimization problem formulated by Karmarkar and Lakshman for the nearest GCD. In the multivariate case we generalize the expressions of Karmarkar and Lakshman, and give explicitly several iteration functions to compute the optimum. The arithmetic complexity of the iterations is detailed.
Full work available at URL: https://arxiv.org/abs/1401.5086
Recommendations
- Nearest multivariate system with given root multiplicities
- On the solutions of polynomial systems obtained with Weierstrass method
- A multivariate Weierstrass iterative rootfinder
- scientific article; zbMATH DE number 1254271
- Nearest common root of a set of polynomials: a structured singular value approach
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Solving polynomial systems; resultants (13P15)
Cites Work
- Design, analysis, and implementation of a multiprecision polynomial rootfinder
- Title not available (Why is that?)
- Global minimization of rational functions and the nearest GCDs
- Nearest multivariate system with given root multiplicities
- Quasi-gcd computations
- On approximate GCDs of univariate polynomials
- Certified approximate univariate GCDs
- Computation of approximate polynomial GCDs and an extension
- Multivariate polynomials, duality, and structured matrices
- Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An improved non-linear method for the computation of a structured low rank approximation of the Sylvester resultant matrix
- The approximate GCD of inexact polynomials
- Numerical Polynomial Algebra
- Generalized normal forms and polynomial system solving
- Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials
- Structured low rank approximations of the sylvester resultant matrix for approximate GCDS of Bernstein basis polynomials
- A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix
- Newton's method for overdetermined systems of equations
- Solving a Polynomial Equation: Some History and Recent Progress
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- Fast algorithms for zero-dimensional polynomial systems using duality
- Stable normal forms for polynomial system solving
- Detection and validation of clusters of polynomial zeros
- Title not available (Why is that?)
- Nearest singular polynomials
- A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials
- Symbolic and numeric methods for exploiting structure in constructing resultant matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- DISPLACEMENT STRUCTURE IN COMPUTING APPROXIMATE GCD OF UNIVARIATE POLYNOMIALS
- Computing multiple roots of inexact polynomials
- Title not available (Why is that?)
- Title not available (Why is that?)
- The nearest polynomial with a given zero, revisited
- A subdivision method for computing nearest gcd with certification
- Hybrid method for computing the nearest singular polynomials
- A numerical elimination method for polynomial computations
- An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
- Approximate GCD of several univariate polynomials with small degree perturbations
- Approximate polynomial GCD: small degree and small height perturbations
- Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems
- Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
- Title not available (Why is that?)
- Title not available (Why is that?)
- The calculation of the degree of an approximate greatest common divisor of two polynomials
- When are two numerical polynomials relatively prime?
- Computing the isolated roots by matrix methods
- Approximate gcds of polynomials and sparse SOS relaxations
- Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
- A unified approach to method for the simultaneous computation of all zeros of generalized polynomials
- Solutions of systems of algebraic equations and linear maps on residue class rings
- Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems
- The nearest polynomial with a zero in a given domain
- Solving over-determined systems by the subresultant method (with an appendix by Marc Chardin)
- A note on global Newton iteration over Archimedean and non-Archimedean fields
- Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method
- A multivariate Weierstrass iterative rootfinder
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving algebraic systems using matrix computations
- Computation of a specified root of a polynomial system of equations using eigenvectors
- Hybrid rational function approximation and its accuracy analysis
- Relations between roots and coefficients, interpolation and application to system solving
Cited In (1)
Uses Software
This page was built for publication: Overdetermined Weierstrass iteration and the nearest consistent system
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476879)
