  This paper presents a fast iterative solver for Lippmann-Schwinger equation
for high-frequency waves scattered by a smooth medium with a compactly
supported inhomogeneity. The solver is based on the sparsifying preconditioner
and a domain decomposition approach similar to the method of polarized traces.
The iterative solver has two levels, the outer level in which a sparsifying
preconditioner for the Lippmann-Schwinger equation is constructed, and the
inner level, in which the resulting sparsified system is solved fast using an
iterative solver preconditioned with a bi-directional matrix-free variant of
the method of polarized traces. The complexity of the construction and
application of the preconditioner is $\mathcal{O}(N)$ and
$\mathcal{O}(N\log{N})$ respectively, where $N$ is the number of degrees of
freedom. Numerical experiments in 2D indicate that the number of iterations in
both levels depends weakly on the frequency resulting in method with an overall
$\mathcal{O}(N\log{N})$ complexity.
