Exploiting Structure of Symmetric or Triangular Matrices on a GPU

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 A D2 A^T, where A is an m x n matrix (m less than or equal to n) and D is an n x 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. We develop in this work efficient GPU algorithms for forming and factoring A D2 A^T by exploiting the triangular rastorization capabilities of the GPU.This report summarizes work from 2005 to 2007 and was supported in part by the US Department of Energy under Grant DEFG0204ER25655 and by the National Science Foundation under Grant CCF 05 14213