Condition Number Bounds for Problems with Integer Coefficients
Author: Malajovich, G.
Source: Journal of Complexity, Volume 16, Number 3, September 2000 , pp. 529-551(23)
Publisher: Academic Press
Abstract:An explicit a priori bound for the condition number associated to each of the following problems is given: general linear equation solving, least squares, nonsymmetric eigenvalue problems, solving univariate polynomials, and solving systems of multivariate polynomials. It is assumed that the input has integer coefficients and is not on the degeneracy locus of the respective problem (i.e., the condition number is finite). Our bounds are stated 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 iteration without shift for the symmetric eigenvalue problem and Graeffe iteration for univariate polynomials. Copyright 2000 Academic Press.
Document Type: Research Article
Affiliations: Departamento de Matemática Aplicada, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, CEP 21945-970, Brazil
Publication date: September 2000