[ Home | Classes | Research | Students | About Me ]

General information:

  • Title of thesis: Preconditioning sparse matrices for computing eigenvalues and solving linear systems of equations
  • Author: Tzu-Yi Chen
  • Advisor: Jim Demmel
  • Department: Computer Science Division at UC Berkeley
  • Filing Date: December 2001
  • Abstract:

    Informally, given a problem to solve and a method for solving it, a preconditioner transforms the problem into one with more desirable properties for the solver. The solver may take less time to find the solution to the new problem, it may compute a more accurate solution, or both. The preconditioned system is solved and the solution is transformed back into the solution of the original problem. In this dissertation we look at the role of preconditioners in finding the eigenvalues of sparse matrices and in solving sparse systems of linear equations. A sparse matrix is one with so many zero entries that either only the nonzero elements and their locations in the matrix are stored, or the matrix is not given explicitly and one can only get the results of multiplying the matrix (and sometimes its transpose) by arbitrary vectors.

    The eigenvalues of a matrix A are the \lambda such that Ax = \lambda x, where x is referred to as the (right) eigenvector corresponding to \lambda. Numerical algorithms that compute the eigenvalues of a nonsymmetric matrix A typically have backward errors proportional to the norm of A, so it can be useful to precondition an n-by-n matrix A in such a way that its norm is reduced and its eigenvalues are preserved. We focus on balancing A, in other words finding a diagonal matrix D such that for 1 <= i <= n the norm of row i and column i of DAD^{-1} are the same. Interestingly, there are many relationships between balancing in certain vector norms and minimizing varied matrix norms. For example, in [1] Osborne shows balancing a matrix in the 2-norm also minimizes the Froebenius norm of DAD^{-1} over all D up to scalar multiples. We summarize results known about balancing in other norms before defining balancing in a weighted norm and proving that this minimizes the 2-norm for nonnegative, irreducible A.

    We use our results on balancing in a weighted norm to justify a set of novel Krylov-based balancing algorithms which approximate weighted balancing and which never explicitly access individual entries of A. By using only matrix-vector (Ax) , and sometimes matrix-transpose-vector (A^Tx), multiplications to access A, these new algorithms can be used with eigensolvers that similarly assume only that a subroutine for computing Ax (and possibly A^Tx) is available. We then show that for matrices from our test suite, these Krylov-based balancing algorithms do, in fact, often improve the accuracy to which eigenvalues are computed by dense or sparse eigensolvers. For our test matrices, Krylov-based balancing improved the accuracy of eigenvalues computed by sparse eigensolvers by up to 10 decimal places. In addition, Krylov-based balancing can also improve the condition number of eigenvalues, hence giving better computed error bounds.

    For solving sparse systems of linear systems the problem is to find a vector x such that Ax=b, where A is a square nonsingular matrix and b is some given vector. Algorithms for finding x can be classified as either direct or iterative: direct methods typically compute the LU factorization of A and solve for x through two triangular solves; iterative methods such as conjugate gradient iteratively improve on an initial guess to x. Though direct methods are considered robust, they can require large amounts of memory if the L and U factors have many more nonzero elements than the matrix A. On the other hand, though iterative methods require less space, they are also less robust than direct methods and their behavior is not as well understood.

    Fortunately, preconditioning can help with some of these issues. For example, preconditioners can be used to reduce the number of nonzero elements in the L and U factors of A, or to improve the likelihood of an iterative method converging quickly to the actual solution vector.

    We begin by discussing preconditioners for direct solvers, starting with several algorithms for reordering the rows and columns of A prior to factoring it. We present data comparing the results of decomposing matrices with a nonsymmetric permutation to results from using a symmetric permutation. For one matrix the size of the largest block found with a nonsymmetric permutation is a tenth of the size of the largest block found with a symmetric permutation, which can greatly reduce the subsequent factorization time. We also note that using a stability ordering in concert with a column approximate minimum degree ordering can lead to L and U factors with significantly more or fewer nonzero elements than those computed after using the sparsity ordering alone.

    Focussing on a specific algorithm for reordering A to reduce fill, we then describe our design and implementation of a threaded column approximate minimum degree algorithm. Though we worked hard to avoid the effects of many known parallel pitfalls, our final implementation never achieved a speedup of more than 3 on 8 processors of an SGI Power Challenge machine, and more typically there was virtually no speedup. By analyzing the performance of our code in detail, we provide a better understanding of the difficulties of efficiently implementing algorithms with fine-grained parallelism even in a shared memory environment.

    Finally we turn to incomplete LU (ILU) factorizations, a family of preconditioners often used with iterative solvers. We propose a modification to a standard ILU scheme and show that it makes better use of the memory the user has available, leading to a greater likelihood of convergence for preconditioned GMRES(50), the iterative solver used in our studies. By looking at data gathered from tens of thousands of test runs combining matrices with different ILU algorithms, parameter settings, scaling algorithms, and ordering algorithms, we draw some conclusions about the effects of different ordering algorithm on the convergence of ILU-preconditioned GMRES(50). We find, for example, that both ordering for stability and partial pivoting are necessary for achieving the best convergence results.

    References:

    [1] E.E. Osborne. On pre-conditioning of matrices. JACM , 7:338-345, 1960.