Date: Friday, April 05, 2013
Location: 1084 East Hall (3:00 PM to 4:00 PM)
Title: O(N) direct solver for integral equations on 2D domains
Abstract: Most commonly used solvers for boundary integral equations are iterative, using FMM-accelerated matrix-vector multiplication. While these methods are efficient in many contexts, examples of problems that can be challenging to iterative methods include Fredholm equations of the first kind, elasticity problems on geometrically complex domains with thin features, and scattering problems near resonances -- problems with relatively poor conditioning. Direct solvers are a promising alternatives in these contexts, as well as in cases when the same equation needs to be solved with different right-hand sides.
We present an efficient direct solver for integral equations, reaching practical O(N) performance for a broad range of problems. The solver is based on a hierarchical compression method previously developed for boundary integral equations on curves. While a direct extension of the method to planar domains has asymptotic cost is O(N^{3/2}), we demonstrate that the method can be reformulated in a way that an additional level of compression is applied to operators involved in the algorithms. All stages of the resulting direct solver have optimal O(N) complexity, as demonstrated by numerical examples and theoretical analysis . The computational examples further demonstrate good practical performance in terms of both speed and memory usage, as compared to existing state-of-the-art direct solvers: for example, even problems involving 10^{7} unknowns can be solved to precision 10^{-10} using a simple Matlab implementation of the algorithm executed on a single core.
This is joint work with E. Corona and P.-G. Martinsson.
Speaker: Denis Zorin
Institution: Courant Institute of Mathematical Sciences, New York University
Event Organizer: Shravan Veerapaneni shravan@umich.edu
|
