  A fast method is proposed for solving the high frequency Helmholtz equation.
The building block of the new fast method is an overlapping source transfer
domain decomposition method for layered medium, which is an extension of the
source transfer domain decomposition method proposed by Chen and Xiang
\cite{Chen2013a,Chen2013b}. The new fast method contains a setup phase and a
solving phase. In the setup phase, the computation domain is decomposed
hierarchically into many subdomains of different levels, and the mapping from
incident traces to field traces on all the subdomains are set up bottom-up. In
the solving phase, first on the bottom level, the local problem on the
subdomains with restricted source is solved, then the wave propagates on the
boundaries of all the subdomains bottom-up, at last the local solutions on all
the subdomains are summed up top-down. The total computation cost of the new
fast method is $O(n^{\frac{3}{2}} \log n)$ for 2D problem. Numerical
experiments shows that with the new fast method, Helmholtz equations with half
billion unknowns could be solved efficiently on massively parallel machines.
