University of Texas at Austin

Past Event: Oden Institute Seminar

Low-rank approximation and rank-revealing for oscillatory-kernel matrix blocks

Yaniv Brick, Senior Lecturer (Assistant Prof.), Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev

3:30 – 5PM
Tuesday Oct 2, 2018

POB 6.304

Abstract

Various fast direct integral equation solvers rely on the low-rank (LR) representation of sub-matrices (blocks) of the boundary elements method (BEM) matrix or moment matrix Z. In particular, direct solvers based on the hierarchical-matrix approach use LR approximate factorization Z_os≈AB^T of “admissible” blocks Z_os corresponding to interactions between separate groups (clusters) of basis (source) and testing (observer) functions that are sufficiently separated. The straightforward algebraic LR factorization, e.g., by using the singular value decomposition (SVD), involves O(N^2) time and memory for generating and storing the blocks, and an O(N^3) time for applying the algebraic procedure itself, and becomes a computational bottleneck for any such solver. While for non-oscillatory kernels many alternative algorithms, including some kernel independent alternatives, enable the fast LR factorization of MoM matrix blocks at an O(N) cost, accurate revealing of the rank and computing the LR factorization beyond the quasi-static regime is performed more efficiently by using physics-based methods. In my talk, I will discuss a class of hierarchical algorithms, developed together with the Computational Electromagnetics Group at UT, for fast LR approximation of oscillatory kernel moment matrix blocks. These rely on the multilevel partitioning of the source cluster associated with Z_os into a tree of sub-clusters. This enables the application of the SVD not directly to Z_os but to smaller matrices, which represent interactions between the source sub-clusters and observers on auxiliary grids; phase- and amplitude-compensation of the interactions allows for coarse (non-uniform) sampling from which the block Z_os can be reconstructed approximately, at the hierarchy’s top level. We will present two variants of the algorithm: (i) a fast algorithm for the computation of Z_os≈AB^T that makes use of volumetric non-uniform grids, and has been shown to effectively achieve computation times that are ∝N^3/2 and ∝N^2 for very large quasi-planar and densely packed problems (with an expected asymptotic costs of O(N^2) and O(N^7/3), respectively) and storage of O(N^3/2). (ii) an even faster algorithm for the computation of an orthonormal column matrix B and the rank only, at costs of N^3/2 and N^2 (for quasi-planar and densely packed cases, respectively), followed by the computation of Z_osB≈A that can be accelerated by employing fast matrix-vector multiplication methods. The performance of the two variants, in terms of memory, computation time, and rank-revealing accuracy, will be demonstrated and compared via representative examples, and their relevance for various applications/problems will be discussed. Bio Yaniv Brick received the B.Sc. (magna cum laude), M.Sc. (summa cum laude), and Ph.D. degrees in electrical engineering from the School of Electrical Engineering, Tel Aviv University, Tel Aviv, Israel, in 2005, 2007, and 2015, respectively. From 2014 to 2017, he was a Post-Doctoral Fellow at the Institute for Computational Engineering and Sciences, The University of Texas at Austin. Since 2017, he is with the Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beersheba, Israel. His current research interests include wave theory and numerical modeling for electromagnetic and acoustic analysis, with an emphasis on fast algorithms for direct and iterative solution of integral equations. Dr. Brick was a recipient of the IEEE Antennas and Propagation SocietyDoctoral Research Award in 2012, the Peter O’Donnell, Jr. Postdoctoral Fellowships in Computational Engineering and Sciences in 2014–2016, the Fulbright Postdoctoral Fellowship Program grant in 2014–2015, and the 2015 Fulbright Alumni Prize.

Event information

Date
3:30 – 5PM
Tuesday Oct 2, 2018
Location POB 6.304
Hosted by Ali Yilmaz