Sparse matrix algorithms (Stanford, June 2013, Tim Davis)

A seminar given at Stanford in June 2013. Sparse Matrix Algorithms: Combinatorics + Numerical Methods + Applications Tim Davis, University of Florida Sparse matrix algorithms lie in the intersection of graph theory and numerical linear algebra, and are a key component of high-performance combinatorial scientific computing. This talk highlights four of my contributions in this domain, ranging from theory and algorithms to reliable software and its impact on applications: (1) Sparse Cholesky update/downdate (2) Approximate minimum degree (3) Unsymmetric multifrontal method for sparse LU factorization (4) Multifrontal sparse QR factorization The design of these algorithms takes into account the many applications that rely on them, including MATLAB (x=A when A is sparse), Mathematica, Google (Street View, Photo Tours, and 3D Earth), Octave, ANSYS, Cadence, MSC NASTRAN, Mentor Graphics, and many other commercial, academic, and government lab applications in finite element methods, mathematical optimization, circuit simulation, VLSI design, robotics, graphics, computer vision, structural engineering, and geophysical modeling. This talk presents my current work in GPU-based heterogeneous high-performance parallel computing for sparse multifrontal methods. The method assembles and factorizes all frontal matrices on the GPU, without the need to transfer large amounts of data between the GPU and CPU. The sparse matrix is shipped to the GPU and the final factors are retreived when it completes. A novel scheduling algorithm for communication-avoiding dense QR exposes a higher degree of parallelism than previous methods. Our research prototype exceeds 80 GFlops for a large sparse QR factorization on the NVIDIA Fermi GPU, with a 5x to 8x speedup for large problems, as compared to the highly-optimized multicore sparse QR on the CPU. [UPDATE: As of Feb 2014, we reach 150 Gflops on the NVIDIA K20c] My goal for future research is to continue to create algorithms and software with deep impact in applications of computational science.