3:30 pm Thursday, March 29, 2007
Math Dept/ICES Numerical Analysis Seminar: Randomized Algorithms and Fast Direct Solvers by Per Gunnar Martinsson (Univ. of Colorado at Boulder) in ACE 6.304
Abstract: Linear boundary value problems occur ubiquitously in many areas of science and engineering, and the cost of computing approximate solutions to such equations is very often what determines which problems can, and which cannot, be simulated. Over the last few decades, significant progress has been made in developing fast algorithms for such problems; FFT-based methods, finite element methods accelerated by multigrid solvers, integral equation methods accelerated by fast multipole methods, and others. However, many technologically important problems remain challenging, including: * Problems requiring the solution of a very large number of similar boundary value problems (e.g. optimal design, molecular dynamics). * Problems whose spectral properties render them hard to solve using iterative methods (e.g. high-frequency scattering). * Problems involving complex multiscale geometries (e.g. modeling of composite materials). In this talk, I will argue that many of these challenging problems can be successfully solved by recently developed fast methods that directly (as opposed to iteratively) solve the linear systems arising from the discretization of linear boundary value problems. I will also describe a number of technical developments that were required for the construction of fast direct solvers, but are of interest in their own right; these include randomized methods for approximating rank-deficient matrices, and interpolative representations of low-rank function spaces. Submitted by
|
|