Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Math Colloquium
Ken Ho Stanford 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, 2014Time: 4:30 pmLocation: Wean Hall 7500Submitted by: BohmanNote: Refreshments at 4:00 pm, Math Lounge. |