Tuesday, July 11
IP2
Direct Methods for Sparse Linear Systems: The MATLAB Sparse Backslash
8:30 AM - 9:15 AM
Room: Imperial Ballroom - ML
Chair: Gilbert Strang, Massachusetts Institute of Technology
Sparse linear systems arise in a wide range of problems in computational science, including such diverse topics as circuit simulation, semiconductor process simulation, DNA electrophoresis, structural mechanics, computational fluid dynamics, and financial portfolio optimization. Direct methods for solving these systems rely on an elegant combination of graph algorithms and linear algebra: elimination trees, depth-first search, paths, cycles, chords, topological orderings, heuristics for NP-hard problems, cliques, cache-friendly dense matrix kernels, graph partitioning, and more. Sparse matrix methods and theory are presented in depth via a simple and concise pair of algorithms for sparse LU and Cholesky factorization, starting from basic principles. Multifrontal and supernodal methods that accelerate these basic algorithms are then illustrated; both are used in x=A\b in MATLAB.
Tim Davis
University of Florida
