Special Seminar

Fast direct solvers for elliptic partial differential equations

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³) 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 (or nearly linearly) with the problem size. Such direct solvers are much faster for problems with multiple right-hand sides that arise frequently in applications.  This talk will highlight recently developed methods that increase the range of applicability of fast direct solvers.