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.
The most efficient direct methods for solving the discrete Helmholtz systems are the multifrontal methods or their pivoted versions @cite_17 @cite_7 @cite_21 . The multifrontal methods exploit the locality of the discrete operator and construct an @math factorization based on a hierarchical partitioning of the domain. The cost of a multifrontal method depends strongly on the number of dimensions. For a 2D problem with @math unknowns, a multifrontal method takes @math flops and @math storage space. The prefactor is usually rather small, making the multifrontal methods effectively the default choice for most 2D Helmholtz problems. However, for a 3D problem with @math unknowns, a multifrontal method requires @math flops and @math storage space, which can be very costly for large scale 3D problems.
@cite_21 @cite_7 @cite_17
2031990962 2063675347
This paper presents an overview of the multifrontal method for the solution of large sparse symmetric positive definite linear systems. The method is formulated in terms of frontal matrices, update matrices, and an assembly tree. Formal definitions of these notions are given based on the sparse matrix structure. Various advances to the basic method are surveyed. They include the role of matrix reorderings, the use of supernodes, and other implementatjon techniques. The use of the method in different computational environments is also described. On etend la methode frontale pour resoudre des systemes lineaires d'equations en permettant a plus d'un front d'apparaitre en meme temps