This paper introduces a new sweeping preconditioner for the iterative solution of the variable coefficient Helmholtz equation in two and three dimensions. The algorithms follow the general structure of constructing an approximate @math factorization by eliminating the unknowns layer by layer starting from an absorbing layer or boundary condition. The central idea of this paper is to approximate the Schur complement matrices of the factorization using moving perfectly matched layers (PMLs) introduced in the interior of the domain. Applying each Schur complement matrix is equivalent to solving a quasi-1D problem with a banded LU factorization in the 2D case and to solving a quasi-2D problem with a multifrontal method in the 3D case. The resulting preconditioner has linear application cost and the preconditioned iterative solver converges in a number of iterations that is essentially indefinite of the number of unknowns or the frequency. Numerical results are presented in both two and three dimensions to demonstrate the efficiency of this new preconditioner.
There has been a vast literature on developing efficient algorithms for the Helmholtz equation. A partial list of significant progresses includes @cite_19 @cite_22 @cite_20 @cite_3 @cite_18 @cite_23 @cite_4 @cite_0 @cite_12 @cite_9 . We refer to the review article @cite_16 and our previous paper @cite_24 for detailed discussion. The brief discussion below is restricted to the ones that are closely related to the approach proposed in this paper.
@cite_18 @cite_4 @cite_22 @cite_9 @cite_3 @cite_0 @cite_19 @cite_24 @cite_23 @cite_16 @cite_12 @cite_20
2098102734 2069595221 2001099567 2165091991
The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable-coefficient Helmholtz equation including very-high-frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three-dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. An iterative algorithm for the solution of the Helmholtz equation is developed. The algorithm is based on a preconditioned conjugate gradient iteration for the normal equations. The preconditioning is based on an SSOR sweep for the discrete Laplacian. Numerical results are presented for a wide variety of problems of physical interest and demonstrate the effectiveness of the algorithm. In this paper, we consider the numerical solution of the Helmholtz equation, arising from the study of the wave equation in the frequency domain. The approach proposed here differs from those recently considered in the literature, in that it is based on a decomposition that is exact when considered analytically, so the only degradation in computational performance is due to discretization and roundoff errors. In particular, we make use of a multiplicative decomposition of the solution of the Helmholtz equation into an analytical plane wave and a multiplier, which is the solution of a complex-valued advection-diffusion-reaction equation. The use of fast multigrid methods for the solution of this equation is investigated. Numerical results show that this is an efficient solution algorithm for a reasonable range of frequencies. Abstract We investigate the use of least-squares methods to approximate the Helmholtz equation. The basis used in the discrete method consists of solutions of the Helmholtz equation (either consisting of plane waves or Bessel functions) on each element of a finite element grid. Unlike previous methods of this type, we do not use polynomial based finite elements. The use of small elements (and relatively few basis functions per element) allows us to prove convergence theorems for the method and, to some extent, control the conditioning of the resulting linear sy stem. Numerical results show the efficiency of the new method and suggest that it may be possible to obtain accurate results with a coarser grid than is usual for standard finite element methods.