Special Applied Mathematics Colloquium

Abstract: In many areas of science and engineering, the cost of solving a linear boundary value problem determines what can and cannot be modeled computationally. In some cases, it is possible to recast the problem as an integral equation which sometimes leads to a reduction in the dimensionality of the problem.  Alternatively, the differential equation can be discretized directly with a finite element or finite difference method. Either way, one is left with having to solve a large linear system. The computational cost of directly inverting the linear system via Gaussian elimination grows as O(N^3) where N is the size of the system. Due to recent developments (multigrid, FMM, FFT, etc.), there are “fast” methods for most of these linear systems of equations. By “fast,” we mean that the computational cost of solving the problem grows as O(N log^k N) where k is a small integer normally k = 0, 1, or 2. Many “fast” schemes are based on iterative techniques that build a sequence of approximate solutions that converges to the exact solution and often require the use of a problem specific preconditioner. In this talk, we will present methods that “directly” invert the system by exploiting structure in the matrix with a cost that grows linearly with the problem size. Such “fast direct methods” are more robust, versatile and stable than iterative schemes.  They are also much faster for problems with multiple right-hand sides.  The recent integration of these methods to applications will also be presented.