text: 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.
  @cite_24: A new finite element method is presented that features the ability to include in the finite element space knowledge about the partial differential equation being solved. This new method can therefore be more efficient than the usual finite element methods. An additional feature of the partition-of-unity method is that finite element spaces of any desired regularity can be constructed very easily. This paper includes a convergence proof of this method and illustrates its efficiency by an application to the Helmholtz equation for high wave numbers. The basic estimates for a posteriori error estimation for this new method are also proved. © 1997 by John Wiley & Sons, Ltd.
  @cite_70: 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.
summary: Simultaneously to the ultra weak formulation, the partition of unity method (PUM) by Babuska and Melenk @cite_24 , and the least-squares method by Monk and Wang @cite_70 , were developed.