We present a solver for the 2D high-frequency Helmholtz equation in heterogeneous acoustic media, with online parallel complexity that scales optimally as @math , where @math is the number of volume unknowns, and @math is the number of processors, as long as @math grows at most like a small fractional power of @math . The solver decomposes the domain into layers, and uses transmission conditions in boundary integral form to explicitly define "polarized traces", i.e., up- and down-going waves sampled at interfaces. Local direct solvers are used in each layer to precompute traces of local Green's functions in an embarrassingly parallel way (the offline part), and incomplete Green's formulas are used to propagate interface data in a sweeping fashion, as a preconditioner inside a GMRES loop (the online part). Adaptive low-rank partitioning of the integral kernels is used to speed up their application to interface data. The method uses second-order finite differences. The complexity scalings are empirical but motivated by an analysis of ranks of off-diagonal blocks of oscillatory integrals. They continue to hold in the context of standard geophysical community models such as BP and Marmousi 2, where convergence occurs in 5 to 10 GMRES iterations.
implemented a 3D solver using the complex-shifted Laplacian with optimal grids to minimize pollution effects in @cite_36 . Multigrid methods applied to large 3D examples have been implemented by Plessix @cite_90 , @cite_69 and, more recently, @cite_21 . A good review of iterative methods for the Helmholtz equation, including complex-shifted Laplace preconditioners, is in @cite_85 . Another review paper that discussed the difficulties generated by the high-frequency limit is @cite_71 . Finally, beautiful mathematical expositions of the Helmholtz equation and a good reviews are @cite_51 and @cite_17 .
@cite_69 @cite_36 @cite_90 @cite_21 @cite_85 @cite_71 @cite_51 @cite_17
2113502771 2095572167 2106787546 2025033760 950823788 2065538232 2042199958 2142094322 2171798031 2098102734 2069595221 2164119610 2001099567 2073656615 2318979302 2063547741 2018457194 1883796613 2117926105 2035238652
SUMMARY In this paper, we address the solution of three-dimensional heterogeneous Helmholtz problems discretized with second-order finite difference methods with application to acoustic waveform inversion in geophysics. In this setting, the numerical simulation of wave propagation phenomena requires the approximate solution of possibly very large indefinite linear systems of equations. For that purpose, we propose and analyse an iterative two-grid method acting on the Helmholtz operator where the coarse grid problem is solved inaccurately. A cycle of a multigrid method applied to a complex shifted Laplacian operator is used as a preconditioner for the approximate solution of this coarse problem. A single cycle of the new method is then used as a variable preconditioner of a flexible Krylov subspace method. We analyse the properties of the resulting preconditioned operator by Fourier analysis. Numerical results demonstrate the effectiveness of the algorithm on three-dimensional applications. The proposed numerical method allows us to solve three-dimensional wave propagation problems even at high frequencies on a reasonable number of cores of a distributed memory computer. Copyright © 2012 John Wiley & Sons, Ltd. In this paper we survey the development of fast iterative solvers aimed at solving 2D 3D Helmholtz problems. In the first half of the paper, a survey on some recently developed methods is given. The second half of the paper focuses on the development of the shifted Laplacian preconditioner used to accelerate the convergence of Krylov subspace methods applied to the Helmholtz equation. Numerical examples are given for some difficult problems, which had not been solved iteratively before. We investigate the parallel performance of an iterative solver for 3D heterogeneous Helmholtz problems related to applications in seismic wave propagation. For large 3D problems, the computation is no longer feasible on a single processor, and the memory requirements increase rapidly. Therefore, parallelization of the solver is needed. We employ a complex shifted-Laplace preconditioner combined with the Bi-CGSTAB iterative method and use a multigrid method to approximate the inverse of the resulting preconditioning operator. A 3D multigrid method with 2D semi-coarsening is employed. We show numerical results for large problems arising in geophysical applications. An algebraic multilevel (ML) preconditioner is presented for the Helmholtz equation in heterogeneous media. It is based on a multilevel incomplete @math factorization and preserves the inherent (complex) symmetry of the Helmholtz equation. The ML preconditioner incorporates two key components for efficiency and numerical stability: symmetric maximum weight matchings and an inverse-based pivoting strategy. The former increases the block-diagonal dominance of the system, whereas the latter controls @math for numerical stability. When applied recursively, their combined effect yields an algebraic coarsening strategy, similar to algebraic multigrid methods, even for highly indefinite matrices. The ML preconditioner is combined with a Krylov subspace method and applied as a “black-box” solver to a series of challenging two- and three-dimensional test problems, mainly from geophysical seismic imaging. The numerical results demonstrate the robustness and efficiency of the ML preconditioner, even at higher frequency regimes. Using a finite element method to solve the Helmholtz equation leads to a sparse system of equations which in three dimensions is too large to solve directly. It is also non-Hermitian and highly indefinite and consequently difficult to solve iteratively. The approach taken in this paper is to precondition this linear system with a new preconditioner and then solve it iteratively using a Krylov subspace method. Numerical analysis shows the preconditioner to be effective on a simple 1D test problem, and results are presented showing considerable convergence acceleration for a number of different Krylov methods for more complex problems in 2D, as well as for the more general problem of harmonic disturbances to a non-stagnant steady flow. A preconditioned iterative solver for the 3D frequency-domain wave equation applied to seismic problems is evaluated. The preconditioner corresponds to an approximate inverse of a heavily damped wave equation deduced from the (undamped) wave equation. The approximate inverse is computed with one multigrid cycle. Numerical results show that the method is robust and that the number of iterations increases roughly linearly with frequency when the grid spacing is adapted to keep a constant number of discretization points per wavelength. To evaluate the relevance of this iterative solver, the number of floating-point operations required for two imaging problems are roughly evaluated. This rough estimate indicates that the time-domain migration approach is more than one order of magnitude faster. The full-wave-form tomography, based on a least-squares formulation and a scale separation approach, has the same complexity in both domains. An iterative solution method, in the form of a preconditioner for a Krylov subspace method, is presented for the Helmholtz equation. The preconditioner is based on a Helmholtz-type differential operator with a complex term. A multigrid iteration is used for approximately inverting the preconditioner. The choice of multigrid components for the corresponding preconditioning matrix with a complex diagonal is validated with Fourier analysis. Multigrid analysis results are verified by numerical experiments. High wavenumber Helmholtz problems in heterogeneous media are solved indicating the performance of the preconditioner. In 1983, a preconditioner was proposed [J. Comput. Phys. 49 (1983) 443] based on the Laplace operator for solving the discrete Helmholtz equation efficiently with CGNR. The preconditioner is especially effective for low wavenumber cases where the linear system is slightly indefinite. Laird [Preconditioned iterative solution of the 2D Helmholtz equation, First Year's Report, St. Hugh's College, Oxford, 2001] proposed a preconditioner where an extra term is added to the Laplace operator. This term is similar to the zeroth order term in the Helmholtz equation but with reversed sign. In this paper, both approaches are further generalized to a new class of preconditioners, the so-called "shifted Laplace" preconditioners of the form Δφ-αk2φ with α ∈ C. Numerical experiments for various wavenumbers indicate the effectiveness of the preconditioner. The preconditioner is evaluated in combination with GMRES, Bi-CGSTAB, and CGNR. In some applications, it is reasonable to assume that geodesics (rays) have a consistent orientation so that the Helmholtz equation may be viewed as an evolution equation in one of the spatial directions. With such applications in mind, we propose a new Eulerian computational geometrical-optics method, dubbed the fast Huygens sweeping method, for computing Green functions of Helmholtz equations in inhomogeneous media in the high-frequency regime and in the presence of caustics. The first novelty of the new method is that the Huygens–Kirchhoff secondary source principle is used to integrate many locally valid asymptotic solutions to yield a globally valid asymptotic solution so that caustics associated with the usual geometrical-optics ansatz can be treated automatically. The second novelty is that a butterfly algorithm is adapted to carry out the matrix–vector products induced by the Huygens–Kirchhoff integration in O(NlogN) operations, where N is the total number of mesh points, and the proportionality constant depends on the desired accuracy and is independent of the frequency parameter. To reduce the storage of the resulting traveltime and amplitude tables, we compress each table into a linear combination of tensor-product based multivariate Chebyshev polynomials so that the information of each table is encoded into a small number of Chebyshev coefficients. The new method enjoys the following desired features: (1) it precomputes a set of local traveltime and amplitude tables; (2) it automatically takes care of caustics; (3) it constructs Green functions of the Helmholtz equation for arbitrary frequencies and for many point sources; (4) for a specified number of points per wavelength it constructs each Green function in nearly optimal complexity in terms of the total number of mesh points, where the prefactor of the complexity only depends on the specified accuracy and is independent of the frequency parameter. Both two-dimensional (2-D) and three-dimensional (3-D) numerical experiments are presented to demonstrate the performance and accuracy of the new method. 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. The Helmholtz equation governing wave propagation and scattering phenomena is difficult to solve numerically. Its discretization with piecewise linear finite elements results in typically large linear systems of equations. The inherently parallel domain decomposition methods constitute hence a promising class of preconditioners. An essential element of these methods is a good coarse space. Here, the Helmholtz equation presents a particular challenge, as even slight deviations from the optimal choice can be devastating. In this paper, we present a coarse space that is based on local eigenproblems involving the Dirichlet-to-Neumann operator. Our construction is completely automatic, ensuring good convergence rates without the need for parameter tuning. Moreover, it naturally respects local variations in the wave number and is hence suited also for heterogeneous Helmholtz problems. The resulting method is parallel by design and its efficiency is demonstrated on 2D homogeneous and heterogeneous numerical examples. 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. In the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ℝ d , d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ℬ R ≈(ℒ−λ I)−1, where ℒ is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ℝ d , which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e −i κ‖x‖ ‖x‖, x∈ℝ d , κ∈ℝ+, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ |log e|2 n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n 2), even in the case κ=O(n). SUMMARY We present a domain decomposition solver for the 2D Helmholtz equation, with a special choice of integral transmission condition that involves polarizing the waves into oneway components. This refinement of the transmission condition is the key to combining local direct solves into an efficient iterative scheme, which can then be deployed in a highperformance computing environment. The method involves an expensive, but embarrassingly parallel precomputation of local Green’s functions, and a fast online computation of layer potentials in partitioned low-rank form. The online part has sequential complexity that scales sublinearly with respect to the number of volume unknowns, even in the high-frequency regime. The favorable complexity scaling continues to hold in the context of low-order finite difference schemes for standard community models such as BP and Marmousi2, where convergence occurs in 5 to 10 GMRES iterations. We present an incomplete LU preconditioner for solving discretized Helmholtz problems. The preconditioner is based on an analytic factorization of the Helmholtz operator. This allows us to take the physical properties of the acoustics problem modeled by the Helmholtz equation into account in the preconditioner. We show how the parameters in the preconditioner can be chosen in order to make it effective. Numerical experiments show that the new preconditioner leads to convergent iterative methods even for large wave numbers, and it outperforms classical ILU preconditioners by a large margin. Underdetermined source separation methods often rely on the assumption that the time-frequency source coefficients are independent and Laplacian distributed. In this article, we extend these methods by assuming that these coefficients follow a generalized Gaussian prior with shape parameter p. We study mathematical and experimental properties of the resulting complex nonconvex lp norm optimization problem in a particular case and derive an efficient global optimization algorithm. We show that the best separation performance for three-source stereo convolutive speech mixtures is achieved for small p. In this paper we compare the following two methods of transmit preceding for the multiple antenna broadcast channel: vector perturbation applied to channel inversion (also termed zero forcing or ZF) precoding and scalar Tomlinson-Harashima (TH) precoding applied to sum-rate achieving transmit precoding. Our results indicate that vector perturbation applied to channel inversion preceding can significantly reduce power enhancement and yields the full diversity afforded by the channel to each user. Scalar TH-modulo reduction significantly reduces the power enhancement for precoding based on sum-rate criterion. The solution to vector perturbation applied to ZF precoding requires the solution to an integer optimization problem which is exponentially complex, or an approximation to the integer optimization problem which requires the Lenstra-Lenstra-Lovasz algorithm of polynomial complexity. Instead we propose a simpler solution (an approximation) to the vector perturbation problem based on the Rayleigh-Ritz theorem (R.A. Horn and C.R. Johnson, 1985). This approximate solution achieves the same diversity order as the optimal vector perturbation technique, but suffers a small coding loss. This solution is of polynomial complexity order. Further, a small increase in complexity with a "sphere"-based search around this solution yields significantly better performance. Since this vector perturbation is required to be done at the symbol rate, the lower complexity of the proposed algorithm is valuable in practice We present a new fast multipole method for particle simulations. The main feature of our algorithm is that it does not require the implementation of multipole expansions of the underlying kernel, and it is based only on kernel evaluations. Instead of using analytic expansions to represent the potential generated by sources inside a box of the hierarchical FMM tree, we use a continuous distribution of an equivalent density on a surface enclosing the box. To find this equivalent density, we match its potential to the potential of the original sources at a surface, in the far field, by solving local Dirichlet-type boundary value problems. The far-field evaluations are sparsified with singular value decomposition in 2D or fast Fourier transforms in 3D. We have tested the new method on the single and double layer operators for the Laplacian, the modified Laplacian, the Stokes, the modified Stokes, the Navier, and the modified Navier operators in two and three dimensions. Our numerical results indicate that our method compares very well with the best known implementations of the analytic FMM method for both the Laplacian and modified Laplacian kernels. Its advantage is the (relative) simplicity of the implementation and its immediate extension to more general kernels. We propose and study a domain decomposition method for solving the truncated perfectly matched layer (PML) approximation in bounded domain of Helmholtz scattering problems. The method is based on the decomposition of the domain into nonoverlapping layers and the idea of source transfer which transfers the sources equivalently layer by layer so that the solution in the final layer can be solved using a PML method defined locally outside the last two layers. The convergence of the method is proved for the case of constant wave number based on the analysis of the fundamental solution of the PML equation. The method can be used as an efficient preconditioner in the preconditioned GMRES method for solving discrete Helmholtz equations with constant and heterogeneous wave numbers. Numerical examples are included.