WS, Per-Gunnar Martinsson: Intro lecture: Fast direct solvers for elliptic PDEs

Speaker
Per-Gunnar Martinsson, UT Austin

Abstract
The talk will describe a class of methods known as “fast direct solvers” that have attracted much attention in the linear algebra and numerical PDE communities in the past couple of decades. These algorithms address the problem of solving a linear equation Ax=b arising from the discretization of either an elliptic PDE or of an associated integral equation. The matrix A will be sparse when the PDE is discretized directly, and dense when an integral equation formulation is used. In either case, industry practice for large scale problems has been to use an iterative solver such as, e.g., multigrid or GMRES. A direct solver, in contrast, builds an approximation to the inverse of A (or alternatively, an easily invertible factorization such as LU or Cholesky). A major development in the last couple of decades has been the emergence of algorithms for performing this inversion in linear or close to linear time. Such methods must necessarily exploit that the inverse of the matrix A is “data sparse”, typically in the sense that it can be tessellated into blocks that have low numerical rank.