A Posteriori Error Estimate for Computing tr(f(A)) by Using the Lanczos Method

An outstanding problem when computing a function of a matrix, f(A), by using a Krylov method is to accurately estimate errors when convergence is slow. Apart from the case of the exponential function which has been extensively studied in the past, there are no well-established solutions to the problem. Often the quantity of interest in applications is not the matrix f(A) itself, but rather, matrix-vector products or bilinear forms. When the computation related to f(A) is a building block of a larger problem (e.g., approximately computing its trace), a consequence of the lack of reliable error estimates is that the accuracy of the computed result is unknown. In this paper, we consider the problem of computing tr(f(A)) for a symmetric positive-definite matrix A by using the Lanczos method and make two contributions: (i) we propose an error estimate for the bilinear form associated with f(A), and (ii) an error estimate for the trace of f(A). We demonstrate the practical usefulness of these estimates for large, sparse or structured, matrices and in particular, show that the trace error estimate is indicative of the number of accurate digits. As an application, we compute the log-determinant of a covariance matrix in Gaussian process analysis and underline the importance of error tolerance as a stopping criterion, as a means of bounding the number of Lanczos steps to achieve a desired accuracy.

By: Jie Chen, Yousef Saad

Published in: RC25650 in 2017

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

rc25650.pdf

Questions about this service can be mailed to reports@us.ibm.com .