This project concerns two topics in numerical linear algebra: the numerical treatment of Markov chains and regularization of ill-posed linear systems. The topics share common features: singular or nearly singular matrices; use of iterative methods for large-scale problems; problems in matrix perturbation; and connections with infinite dimensional problems. The computation of the steady-state vector of a Markov chain as well as other important quantities are being investigated. In particular, algorithms are being developed and analyzed for calculating mean first passage times and for computing the recurrence matrix of M/G/1 type queues. In addition aggregation methods with overlapping blocks and the behavior of chains with sluggish transients are being considered. When ill-posed problems are discretized they result in ill-conditioned linear systems which must be regularized to yield accurate solutions. There are three main goals in this work. The first is to prove the folk theorem that if the components of the data vector with respect to the singular vectors decay sufficiently fast then the conjugate gradient iteration will produce a regularizing set of solutions. The second is to treat problems with errors in the matrix by a regularized total-least-squares approach. The third is to further preconditioning strategies for iterative solution methods.
