Multi-level randomized algorithms for high-frequency wave propagation
Abstract
Fast algorithms (such as the fast multipole method) have revolutionized fields from computational acoustics andelectromagnetics to molecular modeling and chip design by their ability to accelerate the solution to integral equationformulations of the associated differential equations. However, as the wavelength of the solution shrinks, thefundamental approximation techniques inherent in these algorithms must transition from those based on low-rankcompression to those based on a detailed understanding of the analytical structure of the underlying, oscillatoryscattering operators. In this project, the PI and Co-I propose to develop a series of randomized algorithms which,together with a suitable basis, will allow for the efficient multi-level compression of high-frequency scattering operators.This will, in turn, permit the factorization and rapid inversion of the corresponding oscillatory integral equations. Suchdevelopments in fast direct solvers are absolutely necessary in the high-frequency scattering regime in order to avoidthe many problems that plague iterative solvers, namely a growth in the iteration count as the frequency increases.The schemes we intend to construct will leverage recent developments in randomized linear algebra and randomizedprojection methods by coupling them with existing fast algorithms and using the resulting rapidly computableprojections to create hierarchical butterfly-based factorizations of the scattering operators. The resulting tools will beapplied to classical scattering problems in computational acoustics and electromagnetics, to wave propagationproblems in layered and/or inhomogeneous media, and to geometric optimization problems which arise in these fields.At the core of all the methods to be developed will be a multi-level hierarchically structured randomized samplingprocedure to extract the data-sparse representation inherent in butterfly-compressible operators.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 10, 2018
- Source ID
- N000141812307
Entities
People
- Leslie Greengard
Organizations
- New York University
- Office of Naval Research
- United States Navy