  A nearly optimal explicitly-sparse representation for oscillatory kernels is
presented in this work by developing a curvelet based method. Multilevel
curvelet-like functions are constructed as the transform of the original nodal
basis. Then the system matrix in a new non-standard form is derived with
respect to the curvelet basis, which would be nearly optimally sparse due to
the directional low rank property of the oscillatory kernel. Its sparsity is
further enhanced via a-posteriori compression. Finally its nearly optimial
log-linear computational complexity with controllable accuracy is demonstrated
with numerical results. This explicitly-sparse representation is expected to
lay ground to future work related to fast direct solvers and effective
preconditioners for high frequency problems. It may also be viewed as the
generalization of wavelet based methods to high frequency cases, and used as a
new wideband fast algorithm for wave problems.
