Solving the three-dimensional high-frequency Helmholtz equation using contour integration and polynomial preconditioning

Xiao Liu, Yuanzhe Xi, Yousef Saad, Maarten V. de Hoop

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We propose an iterative solution method for the three-dimensional high-frequency Helmholtz equation that exploits a contour integral formulation of spectral projectors. In this framework, the solution in certain invariant subspaces is approximated by solving complex-shifted linear systems, resulting in faster GMRES iterations due to the restricted spectrum. The shifted systems are solved by exploiting a polynomial fixed-point iteration, which is a robust scheme even if the magnitude of the shift is small. Numerical tests in three dimensions indicate that O(n1/3) matrix-vector products are needed to solve a high-frequency problem with a matrix size n with high accuracy. The method has a small storage requirement, can be applied to both dense and sparse linear systems, and is highly parallelizable.

Original languageEnglish (US)
Pages (from-to)58-82
Number of pages25
JournalSIAM Journal on Matrix Analysis and Applications
Issue number1
StatePublished - 2020

Bibliographical note

Funding Information:
∗Received by the editors November 21, 2018; accepted for publication (in revised form) by L. Giraud November 4, 2019; published electronically January 9, 2020. Funding: The work of the second and third authors was supported by National Science Foundation grant DMS-1521573 and the Minnesota Supercomputing Institute. The work of the fourth author was supported by the Simons Foundation under the MATH + X program, National Science Foundation grant DMS-1559587, the corporate members of the Geo-Mathematical Group at Rice University, and Total. †Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005 (, ‡Department of Mathematics, Emory University, Atlanta, GA 30322 ( §Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455 (

Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics


  • Cauchy integral
  • Helmholtz preconditioner
  • Polynomial iteration
  • Shifted Laplacian


Dive into the research topics of 'Solving the three-dimensional high-frequency Helmholtz equation using contour integration and polynomial preconditioning'. Together they form a unique fingerprint.

Cite this