Scientific Computing

Cholesky Decomposition and Linear Programming on GPUs

In this work we present efficient algorithms for highly parallel matrix computations on a GPU [O'Leary 07]. Using the decomposition algorithm and other basic building blocks for linear algebra on the GPU, we demonstrate a GPU-powered linear program solver based on a Primal-Dual Interior-Point Method [Jung and O'Leary 07a,b]. This algorithm, based on the rectangular-packed matrix storage scheme of Gunnels and Gustavson, uses the GPU for computationally intensive tasks such as matrix assembly, Cholesky factorization, and forward and back substitution. Comparisons with a CPU implementation demonstrate that we can improve performance by using the GPU for sufficiently large problems. Since GPU architectures and programming languages are rapidly evolving, we expect that GPUs will be an increasingly attractive tool for matrix computation in the future. We have also developed an efficient CPU-GPU algorithm for solving weighted least-squares problems by exploiting the structure of symmetric or triangular matrices on a GPU. In [Jung and O'Leary 06] we provide details on how to form a matrix-matrix product and form the Cholesky factor of the resulting matrix.