Condition number bounds for problems with integer coefficients

DOI10.1006/JCOM.2000.0552MaRDI QIDQ1594828zbMATH OpenOpenAlexFDO

Authors Gregorio Malajovich

Publication date 5 July 2001

Published in Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

convergenceeigenvalue problemslinear equationcondition numbersleast squares problemsQR iterationGraeffe iterationsystems of multivariate polynomials

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Real polynomials: location of zeros (26C10) Numerical computation of solutions to single equations (65H05)

Abstract: An apriori bound for the condition number associated to each of the following problems is given: general linear equation solving, minimum squares, non-symmetric eigenvalue problems, solving univariate polynomials, solving systems of multivariate polynomials. It is assumed that the input has integer coefficients and is not on the degenerate locus of the respective problem (i.e. the condition number is finite). Then condition numbers are bounded in terms of the dimension and of the bit-size of the input. In the same setting, bounds are given for the speed of convergence of the following iterative algorithms: QR without shift for the symmetric eigenvalue problem, and Graeffe iteration for univariate polynomials.

Recommendations

• Bounds for the condition number of polynomials systems with integer coefficients. (invited talk)
• The geometry of ill-conditioning
• Bounds and Estimates for Condition Numbers of Integral Equations
• On condition numbers of polynomial eigenvalue problems
• On the minimum value of the condition number of polynomials

Cites work

• scientific article; zbMATH DE number 3937328 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1015317 (Why is no real title available?)
• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 1069617 (Why is no real title available?)
• scientific article; zbMATH DE number 939812 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• Condition Number Analysis for Sparse Polynomial Systems
• The number of roots of a system of equations

Cited in

(4)

• Bounds for the condition number of polynomials systems with integer coefficients. (invited talk)
• Algorithms for Chow-Heegner points via iterated integrals
• Bounds and Estimates for Condition Numbers of Integral Equations
• Robust certified numerical homotopy tracking

Describes a project that uses

Uses Software

• mctoolbox

This page was built for publication: Condition number bounds for problems with integer coefficients

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