Overdetermined Weierstrass iteration and the nearest consistent system

DOI10.1016/J.TCS.2014.10.008MaRDI QIDQ476879zbMATH OpenOpenAlexWikidataFDO

Authors Olivier Ruatta, Mark Sciabica, Agnes Szanto

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.5086

zbMATH Keywords

approximate GCDoverdetermined systemsnearest consistent systemWeierstrass-Durand-Kerner method

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Solving polynomial systems; resultants (13P15)

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 $k$ 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.

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

Cites work

• scientific article; zbMATH DE number 2125604 (Why is no real title available?)
• scientific article; zbMATH DE number 3161517 (Why is no real title available?)
• scientific article; zbMATH DE number 5168246 (Why is no real title available?)
• scientific article; zbMATH DE number 4076472 (Why is no real title available?)
• scientific article; zbMATH DE number 62668 (Why is no real title available?)
• scientific article; zbMATH DE number 1253975 (Why is no real title available?)
• scientific article; zbMATH DE number 1254251 (Why is no real title available?)
• scientific article; zbMATH DE number 1254271 (Why is no real title available?)
• scientific article; zbMATH DE number 1254284 (Why is no real title available?)
• scientific article; zbMATH DE number 1262453 (Why is no real title available?)
• scientific article; zbMATH DE number 1262454 (Why is no real title available?)
• scientific article; zbMATH DE number 1262456 (Why is no real title available?)
• scientific article; zbMATH DE number 1303542 (Why is no real title available?)
• scientific article; zbMATH DE number 1504686 (Why is no real title available?)
• scientific article; zbMATH DE number 2151210 (Why is no real title available?)
• scientific article; zbMATH DE number 953021 (Why is no real title available?)
• scientific article; zbMATH DE number 1827103 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials
• A multivariate Weierstrass iterative rootfinder
• A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix
• A note on global Newton iteration over Archimedean and non-Archimedean fields
• A numerical elimination method for polynomial computations
• A subdivision method for computing nearest gcd with certification
• A unified approach to method for the simultaneous computation of all zeros of generalized polynomials
• Algorithm 921: alphaCertified: certifying solutions to polynomial systems
• An algorithm for computing certified approximate GCD of \(n\) univariate polynomials
• An improved non-linear method for the computation of a structured low rank approximation of the Sylvester resultant matrix
• Approximate GCD of several univariate polynomials with small degree perturbations
• Approximate gcds of polynomials and sparse SOS relaxations
• Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
• Approximate polynomial GCD: small degree and small height perturbations
• Certified approximate univariate GCDs
• Computation of a specified root of a polynomial system of equations using eigenvectors
• Computation of approximate polynomial GCDs and an extension
• Computing multiple roots of inexact polynomials
• Computing the isolated roots by matrix methods
• Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method
• Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems
• DISPLACEMENT STRUCTURE IN COMPUTING APPROXIMATE GCD OF UNIVARIATE POLYNOMIALS
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Detection and validation of clusters of polynomial zeros
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• Fast algorithms for zero-dimensional polynomial systems using duality
• Generalized normal forms and polynomial system solving
• Global minimization of rational functions and the nearest GCDs
• Hybrid method for computing the nearest singular polynomials
• Hybrid rational function approximation and its accuracy analysis
• Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems
• Multivariate polynomials, duality, and structured matrices
• Nearest multivariate system with given root multiplicities
• Nearest singular polynomials
• Newton's method for overdetermined systems of equations
• Numerical Polynomial Algebra
• On approximate GCDs of univariate polynomials
• Quasi-gcd computations
• Relations between roots and coefficients, interpolation and application to system solving
• Solutions of systems of algebraic equations and linear maps on residue class rings
• Solving a Polynomial Equation: Some History and Recent Progress
• Solving algebraic systems using matrix computations
• Solving over-determined systems by the subresultant method (with an appendix by Marc Chardin)
• Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
• Stable normal forms for polynomial system solving
• Structured low rank approximations of the sylvester resultant matrix for approximate GCDS of Bernstein basis polynomials
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• The approximate GCD of inexact polynomials
• The calculation of the degree of an approximate greatest common divisor of two polynomials
• The nearest polynomial with a given zero, revisited
• The nearest polynomial with a zero in a given domain
• Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials
• When are two numerical polynomials relatively prime?

Cited in

(1)

• Nearest multivariate system with given root multiplicities

Describes a project that uses

Uses Software

• MultRoot
• alphaCertified
• na20

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)