A multilevel transform is introduced to represent discretizations of integral operators from potential theory by nearly sparse matrices. The new feature is to construct the basis in a hierarchical decomposition of the three-space and not, in a parameter space of the boundary manifold. This construction leads to sparse representations of the operator even for geometrically complicated domains.
It is demonstrated that the numerical costs are essentially equal to performing the fast multipole method. The diagonal blocks of the transformed matrix can be used as an inexpensive preconditioner which is empirically shown to reduce the condition number independent of the mesh size.