New algorithms for approximating Φ-functions and their condition numbers for large sparse matrices

摘要

Given an n-by-n large sparse matrix A with low rank or with fast decaying singular values, we propose new algorithms for consecutively approximating the functions ?_?(A) as well as their 2-norm condition numbers for ? = 0, 1, . . . , p. The key is to reduce the computation of ?'-functions of the large matrix to that of ?_?(+1)-functions of some smaller matrices of size r-by-r, where r is the numerical rank of A. For storage reasons, the new algorithms need to store only two n-by-r sparse matrices and some r-by-r matrices, rather than some n-by-n possibly dense matrices. Some error analysis is given. Numerical experiments illustrate the numerical behavior of our new algorithms and show the practical utility of new strategies.