Optimal O(N) Helmholtz and Eigenvalue Solvers for Multi-Domain Problems

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

The design and optimization of many important engineering devices, seismic exploration for oil or gas, or non-intrusive testing of aircraft parts are a few of the many applications that rely on fast computer simulation of certain so-called Helmholtz problems. Helmholtz problems are notoriously difficult to solve computationally, and there has been much research into finding better algorithms for this key and essential task. Despite this past research, there remains room for improvement. The benefit of improved algorithms could be, for example, the creation of advanced optical meta-materials that can outperform traditional optical devices used in civilian and military applications, e.g., being lighter, using less power, or operating in multiple regimes. This proposal will develop new fast algorithms for solving Helmholtz problems. The algorithms are optimal in the sense that the number of operations needed to solve the problem is proportional to the number of degrees of freedom (number of unknowns). The breakthrough is based on viewing the Helmholtz problem as the time-periodic solution of an associated wave propagation problem using the recently developed WaveHoltz algorithm. Time-periodic problems and associated eigenvalue problems arise in a wide range of applications in engineering and applied sciences involving systems exhibiting time-harmonic behavior. This proposal aims to address problems of this type by developing new and efficient high-order accurate algorithms for solving large-scale Helmholtz and eigenvalue problems for multi-domain and multi-physics applications. Numerical schemes for these problems will be based on an extended WaveHoltz algorithm for Helmholtz problems, along with a new EigenWave algorithm for eigenvalue problems. WaveHoltz computes solutions to the Helmholtz problem by filtering solutions of a related time-domain wave equation, thus avoiding the need to invert a large, indefinite matrix. The EigenWave algorithm follows a similar approach and can compute eigenvalues of an elliptic operator anywhere in the spectrum without inverting an indefinite shifted matrix. In addition to the extension of WaveHoltz to complex geometry on overset grids, the basic WaveHoltz approach will be accelerated using large-time-step implicit time-stepping at an O(N) cost per iteration (N being the number of grid points), and by deflation using eigenmodes (or approximate coarse-grid eigenmodes) computed with the new EigenWave algorithm. Dispersive (pollution) errors will be ameliorated using high-order accurate spatial approximations. WaveHoltz will also be extended to dispersive wave propagation problems as well as multi-domain problems that couple different physics or materials in different domains, coupled with high-order accurate interface conditions. For open domain problems (e.g. scattering problems) the new algorithms will be coupled to advanced radiation boundary conditions. The development of the proposed algorithms and simulation capabilities will lead to a new and transformative approach for solving large-scale Helmholtz and eigenvalue problems, and will provide high-performance open source software tools to the community. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.