Introduction to GOFMM

GOFMM stands for Geometry-Oblivious Fast Multipole Method, which is a novel method that creates a hierarchical low-rank approximation, or “compression,” of an arbitrary dense symmetric positive denite (SPD) matrix. For many applications, GOFMM enables an approximate matrix-vector multiplication (MATVEC) in O(NlogN) or even O(N) time, where N is the matrix size. Compression requires N log N storage and work. In general, our scheme belongs to the family of hierarchical matrix approximation methods. In particular, it generalizes the fast multipole method (FMM) to a purely algebraic setting by only requiring the ability to sample matrix entries. Neither geometric information (i.e., point coordinates) nor knowledge of how the matrix entries have been generated is required, thus the term “geometry-oblivious.”

Compress (Constructing an H-Matrix)

Evaluate (Matrix-Vector Multiplication)

Factorize (H-Matrix Factorization for Fast Solvers)

Solve (Solve a Shifted Linear System)