Parallel Sparse Cholesky Factorization

As sequential computers seem to be approaching their limits in CPU speed there is increasing interest in parallel computers. This development calls for parallel algorithms for problems that may already have efficient sequential algorithms. The problem of solving a linear system of equations arises in many areas of science and engineering. Quite often each equation only involves a small number of the variables. In that case the linear systems is sparse. If we can take advantage of the sparsity we can solve much larger systems. Consider the linear system $Ax = b$, where $A$ is a sparse symmetric positive define matrix. A common approach to solving this system is to use Cholesky factorization. Algorithms that solve sparse linear systems using the Cholesky factorization usually consist of the following steps. First the matrix $A$ is permuted in order to get a sparse Cholesky factor $L$. Then there is the symbolic factorization of $A$ to determine the nonzero structure of $L$. Finally the value of $L$ is calculated in the numeric factorization phase and $x$ is computed by solving the triangular systems $Ly = b$ and $L^{T}x = y$. In this thesis we present parallel algorithms for all the above steps except for the permutation step. Before the symbolic factorization we compute the elimination tree of $A$. Elimination trees have many applications in sparse matrix computations. Therefore our parallel algorithm to find elimination trees is important in its own right. The algorithm we present for symbolic factorization then uses the elimination tree to compute the nonzero structure of $L$. We next present a parallel algorithm to compute the numeric factorization of $A$. It runs in time proportional to the height of $A$'s elimination tree times a log factor. We also show how that algorithm can be converted into an NC algorithm (i.d., an algorithm that runs in polygarithmic time) by use of fast algorithms for dense matrices. Finally we demonstrate a parallel algorithm to solve sparse triangular systems of equations. There again we show a version that runs in time related to the height of the elimination tree and a version that is an NC algorithm