This dissertation concerns the development of iterative methods for the approximation of functions of a large matrix, motivated by the development of efficient algorithms for the analysis of large-scale linear discrete ill-posed problems and complex networks. The connection between the Lanczos process and Gauss-type quadrature rules has been exploited for several decades in the development of iterative methods for bounding matrix functions; this work further elaborates on the application of Gauss-type quadrature to matrix computations. In addition, methods based on the singular value decomposition (SVD) and eigenvalue decomposition are presented.
First we consider the minimization of a functional over a set of approximate solutions of a linear discrete ill-posed problem, in order to compute confidence intervals for components of the solution of such a problem. Our iterative method, using the link between Lanczos bidiagonalization and quadrature rules to bound certain matrix functions, greatly reduces large-scale work relative to available methods.
Next we consider methods based on quadrature rules computed via block Lanczos algorithms. We derive anti-Gauss quadrature rules for the symmetric and nonsymmetric block Lanczos algorithms. These methods are applied to the computation of functions of an adjacency matrix. Moreover, novel quantities are introduced which characterize the nodes of a complex network, and which can be computed cheaply via our block methods.
The remaining numerical methods presented rely on bounds based on the use of a partial SVD or partial eigenvalue decomposition of a large matrix. Such methods are competitive when solving many problems with a fixed matrix A but different data vectors. An alternative is provided to the aforementioned quadrature-based algorithm for computing confidence intervals for ill-posed problems, which is favorable when confidence intervals for many components are desired. Regarding complex networks, we use a partial eigenvalue decomposition to bound elements of the exponential of a symmetric adjacency matrix, and develop an algorithm which identifies important nodes in a complex network.