Content area
Abstract
Many physical phenomena are characterized by strong localization , that is, rapid decay outside a small spatial or temporal region. Frequently, such localization can be expressed as decay in the entries of a function f (A) of an appropriate sparse or banded matrix A that encodes a description of the system. Important examples include the decay in the entries of the density matrix for non-metallic systems in quantum chemistry (a function of the Hamiltonian), the localization of the eigenvectors in the Anderson model, and the decay behavior of the inverse of a banded symmetric positive definite matrix. Localization phenomena are of fundamental importance in physical theory and in computation, because they open up the possibility of approximating relevant matrix functions in O(n) time, where n is a measure of the size of the system.
In this thesis we first give some background on matrix functions and their importance in scientific applications, and we review the existing results on decay bounds on the entries of matrix functions. Next, we present our main results that generalize and unify several previous bounds known in the literature for special classes of functions and matrices, such as the inverse, the resolvent, and the exponential. Our theory can be used to determine the bandwidth or sparsity pattern outside which the entries of f (A) are guaranteed to be so small that they can be neglected without exceeding a prescribed error tolerance. We discuss sufficient conditions for the possibility of O(n) approximations to given accuracy in terms of the possible singularities of f and the spectral properties of the matrices involved. To approximate f(A) we consider algorithms that are based upon polynomial approximations. Depending on the location of the spectrum, different approaches are used. If the eigenvalues of A lie on a line segment in the complex plane, we use the well known Chebyshev polynomials to compute approximations of the matrix function. For more general matrices, we consider an approximation technique based on Newton-type interpolation, in which the interpolation points are given by the Féjer points. We combine these techniques with a procedure that a priori determines the significant bandwidth (or sparsity pattern) of the matrix f(A). Finally, we present numerical experiments illustrating the behavior of the proposed approximation schemes.
