Componentwise condition numbers of random sparse matrices
arXiv:0807.09564 citationsh-index: 36
Originality Synthesis-oriented
AI Analysis
Provides theoretical guarantees for numerical stability of sparse linear systems, relevant to numerical linear algebra researchers.
The paper proves an O(log n) bound for the expected logarithm of the componentwise condition number of random sparse n×n matrices, implying small average loss of accuracy for triangular linear systems.
We prove an O(log n) bound for the expected value of the logarithm of the componentwise (and, a fortiori, the mixed) condition number of a random sparse n x n matrix. As a consequence, small bounds on the average loss of accuracy for triangular linear systems follow.