Accuracy in One-way and Two-way Algorithms for Computing Desired Entries in the Inverse of Sparse Matrices

摘要

When developing a fast algorithm (FIND-SS, a type of one-way algorithm) for computing certain entries of the inverse of a sparse matrix and comparing it with other algorithms that require both LU factorization and backward substitution (two-way algorithms), we observed that two-way algorithms sometimes introduce significant extra round-off errors. Such errors exist even for some well-conditioned matrices, including those that do not require partial pivoting. Our investigation shows that the extra errors in these two-way algorithms are introduced by the update rule in their backward pass, which is a form of Sherman-Morrison-Woodbury formula. In general, any algorithm that relies on this formula is subject to such type of errors, and therefore, other applications that use the formula need to be inspected for such errors as well. Additionally, we present a sufficient condition under which large errors can be expected.