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 of this approach 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 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.
The most efficient direct methods for solving the discretized Helmholtz systems are the multifrontal methods or their pivoted versions @cite_31 @cite_19 @cite_39 . The multifrontal methods exploit the locality of the discrete operator and construct an @math factorization based on a hierarchical partitioning of the domain. Their computational costs depend quite strongly on the dimensionality. In 2D, for a problem with @math unknowns, a multifrontal method takes @math steps and @math storage space. The prefactor is usually rather small, making the multifrontal methods effectively the default choice for the 2D Helmholtz problem. In 3D, for a problem with @math unknowns, a multifrontal method takes @math steps and @math storage space. For large scale 3D problems, they can be very costly.
@cite_19 @cite_31 @cite_39
2063675347 2031990962
On etend la methode frontale pour resoudre des systemes lineaires d'equations en permettant a plus d'un front d'apparaitre en meme temps 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.