Parallel MMF: a Multiresolution Approach to Matrix Computation
This work provides a scalable computational primitive for handling large sparse matrices, which is incremental as it builds on existing MMF methods.
The authors tackled the problem of efficiently computing Multiresolution Matrix Factorization (MMF) by developing pMMF, a parallel algorithm that scales linearly in dimension for sparse matrices, enabling applications like matrix compression and preconditioning.
Multiresolution Matrix Factorization (MMF) was recently introduced as a method for finding multiscale structure and defining wavelets on graphs/matrices. In this paper we derive pMMF, a parallel algorithm for computing the MMF factorization. Empirically, the running time of pMMF scales linearly in the dimension for sparse matrices. We argue that this makes pMMF a valuable new computational primitive in its own right, and present experiments on using pMMF for two distinct purposes: compressing matrices and preconditioning large sparse linear systems.