CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Ken Ho
Title: Fast direct methods for structured matrices

Abstract: Many linear systems arising in practice are governed by rank-structured matrices. Examples include PDEs, integral equations, Gaussian process regression, etc. Such systems are typically solved using fast iterative methods, which have been very successful but remain somewhat ineffective when faced with slow convergence or multiple right-hand sides. An alternative in such cases is to consider direct methods such as matrix factorization, which typically are much more robust and allow efficient information reuse. However, standard direct solvers have cubic complexity and thus are prohibitively expensive. In this talk, we discuss our recent efforts at accelerating direct methods to optimal linear or quasilinear complexity by exploiting rank structure. Our main technical achievement is an efficient matrix sparsification/factorization framework that produces a generalized LU decomposition. This factorization permits fast multiplication/inversion and further supports rapid updating. We anticipate that such techniques will be game-changing for applications requiring the solution of an exceedingly large number of closely related linear systems, as is common in many important problems such as protein structure prediction and inverse scattering.

Date: Wednesday, October 8, 2014
Time: 4:30 pm
Location: Wean Hall 7500
Submitted by:  Bohman
Note: Refreshments at 4:00 pm, Math Lounge.