Probability and symmetry in computational linear algebra

This thesis is divided into two parts. In the first part (Chapter 2), we study Gaussian elimination by means of probabilistic analysis and in the second one (Chapters 3 and 4), we study how to preserve symmetry in preconditioned Krylov subspace methods and develop a new Krylov subspace solver for the solution of a nonsymmetric linear system {dollar}Ax=b.{dollar}; The numerical instability of Gaussian elimination is proportional to the size of the L and U factors that it produces. The worst case bounds are well known. For the case without pivoting, breakdowns can occur and it is not possible to provide a priori bounds for L and U. For the partial pivoting case, the worst case bound is {dollar}O(2sp{lcub}n{rcub}),{dollar} where n is the size of the system. Yet, these worst case bounds are seldom achieved, and in particular Gaussian elimination with partial pivoting is extremely stable in practice. Surprisingly, there has been relatively little theoretical study of the "average" case behaviour. The purpose of our study in Chapter 2 is to provide a probabilistic analysis of the case without pivoting. The distribution we use for the entries of A is the normal distribution with mean 0 and unit variance. We first derive the distributions of the entries of L and U. Based on this, we prove that the probability of the occurrence of a pivot less than {dollar}epsilon{dollar} in magnitude is {dollar}O(epsilon).{dollar} We also prove that the probabilities {dollar}Prob(Vert UVertsb{lcub}infty{rcub}/Vert AVertsb{lcub}infty{rcub}>nsp{lcub}2.5{rcub}){dollar} and {dollar}Prob(Vert LVertsb{lcub}infty{rcub}>nsp3){dollar} decay algebraically to zero as n tends to infinity. Numerical experiments are presented to support the theoretical results. By combining our theoretical results and the observations of Trefethen and Schreiber (57) on random matrices, we propose a new method of using GE which may be particularly suited to certain kinds of parallel computers, which greatly reduces data movements while avoiding breakdown and instability effectively.; In Chapter 3, we consider the problem of solving a linear system {dollar}Ax=b{dollar} when A is nearly symmetric and when the system is preconditioned by a symmetric positive definite matrix M. In the symmetric case, one can recover symmetry by using M-inner products in the Conjugate Gradient Algorithm. Inner products can also be used in the nonsymmetric case, and near symmetry can be preserved similarly. We explore the implementation issues associated with this technique and compare a few different options.; We present in Chapter 4 a variant of the popular BiCGSTAB method for solving nonsymmetric linear systems. The method, which we denote by ML(k)BiCGSTAB, is derived from a variant of the BiCG method based on a Lanczos process using multiple {dollar}(k>1){dollar} starting left Lanczos vectors. Compared with the original BiCGSTAB method, our new method produces a residual polynomial which is of lower degree after the same number of steps but which also requires fewer matrix-vector products to generate, on average requiring only {dollar}1+1/k{dollar} matvec's per step. Empirically, it also seems to be more stable and faster convergent. The new method can be implemented as a k-term recurrence and can be viewed as a bridge connecting the Arnoldi-based FOM/GMRES methods and the Lanczos-based BiCGSTAB methods.