Rapid evolution of GPUs in performance, architecture, and programmability provides general and scientific computational potential beyond their primary purpose, graphics processing. In this work we present an efficient algorithm for solving symmetric and positive definite linear systems using the GPU. 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.
Keywords: GPGPU, Cholesky, Matrix Decomposition, Linear Programming, Interior Point Method
Matrix computations are expensive, and GPUs have the potential to deliver results at reduced cost by exploiting parallel computation. We focus on dense matrices of the form $\mathbf{A} \mathbf{D}^2 \mathbf{A}^T$, where $\mathbf{A}$ is an $m \times n$ matrix ($m \le n$) and $\mathbf{D}$ is an $n \times n$ diagonal matrix. Many important numerical problems require solving linear systems of equations involving matrices of this form. These problems include normal equations approaches to solving linear least squares and weighted linear least squares problems, and interior point algorithms for linear and nonlinear programming problems.
Keywords: GPGPU, general purpose graphics processing units, symmetric matrix, triangular matrix, rectangular packed format, matrix computation, factorization, decomposition, weighted least squares.