  Wavelet decompositions of integral operators have proven their efficiency in
reducing computing times for many problems, ranging from the simulation of
waves or fluids to the resolution of inverse problems in imaging.
Unfortunately, computing the decomposition is itself a hard problem which is
oftentimes out of reach for large scale problems. The objective of this work is
to design fast decomposition algorithms based on another representation called
product-convolution expansion. This decomposition can be evaluated efficiently
assuming that a few impulse responses of the operator are available, but it is
usually less efficient than the wavelet decomposition when incorporated in
iterative methods. The proposed decomposition algorithms, run in quasi-linear
time and we provide some numerical experiments to assess its performance for an
imaging problem involving space varying blurs.
