University of Texas at Austin

Past Event: Oden Institute Seminar

Butterfly+ Fast Direct Solvers for Highly Oscillatory Problems

Eric Michielssen, Professor, Department of Electrical Engineering and Computer Science,University of Michigan, Ann Arbor

3:30 – 5PM
Thursday Mar 22, 2018

POB 6.304

Abstract

Fast direct integral equation (IE) solvers for oscillatory problems governed by the Helmholtz and Maxwell’s equations constitute an active area of research in applied mathematics and engineering. Direct solvers represent an attractive alternative to iterative schemes for problems that are inherently ill-conditioned and/or involve many excitations (right-hand sides). Present direct solvers leveraging hierarchical (semi-separable) matrix and related constructs rely on low-rank (LR) representations of blocks of discretized forward and inverse IE operators to rein in the CPU and memory requirements of traditional direct methods. Unfortunately, when applied to highly oscillatory problems, the computational complexity and memory requirements of these solvers suffer from a lack of LR compressibility of blocks of the discretized operators. Recently, we developed a family of butterfly-enhanced direct IE solvers that circumvent this bottleneck. Contrary to LR schemes, butterfly representations are well-suited for compressing highly oscillatory operators and can be used to construct LU and Hierarchical Semi-Separable matrix-based fast direct solvers. The resulting solvers leverage randomized schemes to construct butterfly-compressed approximations of blocks obtained by adding, multiplying, and inverting previously butterfly-compressed matrices. Moreover, to render them applicable to both 2D and 3D scenarios, recursive extensions of classical butterfly structures, termed butterfly+, are called for. The CPU and memory complexities of these solvers are estimated and numerically validated to be O(N log^(2) N) and at most (O(N^(1.5) log N), respectively. Applications of the proposed solvers to radar cross section analysis, wireless propagation in complex environments, and focusing through opaque media involving millions of spatial unknowns will be discussed. Bio Eric Michielssen received his M.S. in Electrical Engineering (Summa Cum Laude) from the Katholieke Universiteit Leuven (KUL, Belgium) in 1987, and his Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign (UIUC) in 1992. From 1992 to 2005, he served on the faculty at UIUC. In 2005, he joined the University of Michigan, Ann Arbor, where he currently is the Louise Ganiard Johnson Professor of Engineering and Professor of Electrical Engineering and Computer Science. He also serves as the institution’s Associate Vice President for Advanced Research Computing and Co-Director for its Precision Health Initiative. His research interests include all aspects of theoretical and applied computational electromagnetics, with a focus on fast frequency and time domain integral-equation-based techniques for analyzing electromagnetic phenomena, and the development of robust optimizers for the synthesis of electromagnetic/optical devices.

Event information

Date
3:30 – 5PM
Thursday Mar 22, 2018
Location POB 6.304
Hosted by Leszek F. Demkowicz