The butterfly algorithm is a robust alternative to the FFT for
computing certain oscillatory integrals in a fast and accurate manner. In
this approach low-rank interactions are updated in a hierarchical fashion
up and down quadtrees. We review the method, its expected accuracy, and
present an application to synthetic aperture radar imaging. Joint work
with Lexing Ying.