Stable computation of generalized matrix functions via polynomial interpolation

Abstract

Generalized matrix functions (GMFs) extend the concept of a matrix function to rectangular matrices via the singular value decomposition. Several applications involving directed graphs, Hamiltonian dynamical systems, and optimization problems with low-rank constraints require the action of a GMF of a large, sparse matrix on a vector. We present a new method for applying GMFs to vectors based on Chebyshev interpolation. The method is matrix free and requires no orthogonalization and minimal additional storage. Comparisons against existing approaches based on Lanczos bidiagonalization demonstrate the competitiveness of our approach. We prove that our method is backward stable by generalizing the proof of the backward stability of Clenshaw's algorithm to the matrix case.