Statistical complexity of numerical linear algebra
Eric Kostlan · 1985
In this paper statistical properties of problems that occur in numerical linear algebra are studied. The distribution function of the condition number of a random matrix is estimated and bounds are calculated for the average loss of precision encountered when one solves a system of linear equations. Bounds are calculated for the average performance of the algorithm. The squaring algorithm can calculate eigenvectors of symmetric and Hermitian matrices, and thus an upper bound is found for the average complexity of (epsilon)-eigenvector calculation. In fact we show that the number of operations required to given an (epsilon)-eigenvector, when averaged over the space of real symmetric or complex Hermitian matrices, grows no more rapidly than some polynomial in the size of the matrix. We also investigate the average performance of the of numerical linear algebra. We show, for example, that the power method and the QR method require, on the average, an infinite number of steps to produce an (epsilon)-eigenvector.