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

condition numbersconvergenceeigenvalue problemsGraeffe iterationleast squares problemslinear equationQR iterationsystems of multivariate polynomials

Mathematics Subject Classification ID

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

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.

Review text

Explicit bounds are derived for the condition numbers associated to linear equation solving, least squares problems, nonsymmetric eigenvalue problems, solving univariate polynomials, and solving systems of multivariate polynomials. These results are applied to find bounds for the speed of convergence of QR iteration without shift for the symmetric eigenvalue problems and Graeffe iteration for solving univariate polynomials as well.

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

• Condition Number Analysis for Sparse Polynomial Systems
• 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?)
• The number of roots of a system of equations

Cited in

(4)

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

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)