Condition Number Bounds for Problems with Integer Coefficients
Copyright policy )Condition Number Bounds for Problems with Integer Coefficients
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.
Numerical computation of eigenvalues and eigenvectors of matrices, Statistics and Probability, Iterative numerical methods for linear systems, Numerical solutions to overdetermined systems, pseudoinverses, Control and Optimization, eigenvalue problems, Numerical computation of matrix norms, conditioning, scaling, Numerical computation of solutions to systems of equations, linear equation, Complexity and performance of numerical algorithms, Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral), FOS: Mathematics, Computational aspects of field theory and polynomials, QR iteration, systems of multivariate polynomials, Numerical Analysis, least squares problems, convergence, Algebra and Number Theory, Graeffe iteration, Applied Mathematics, condition numbers, Numerical Analysis (math.NA), Real polynomials: location of zeros, Numerical computation of solutions to single equations, complexity, condition number, height
Numerical computation of eigenvalues and eigenvectors of matrices, Statistics and Probability, Iterative numerical methods for linear systems, Numerical solutions to overdetermined systems, pseudoinverses, Control and Optimization, eigenvalue problems, Numerical computation of matrix norms, conditioning, scaling, Numerical computation of solutions to systems of equations, linear equation, Complexity and performance of numerical algorithms, Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral), FOS: Mathematics, Computational aspects of field theory and polynomials, QR iteration, systems of multivariate polynomials, Numerical Analysis, least squares problems, convergence, Algebra and Number Theory, Graeffe iteration, Applied Mathematics, condition numbers, Numerical Analysis (math.NA), Real polynomials: location of zeros, Numerical computation of solutions to single equations, complexity, condition number, height
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!