Geometry-Oblivious FMM for Compressing Dense SPD Matrices
Event Type
Paper
TimeThursday, November 16th1:30pm -
2pm
Location405-406-407
DescriptionWe present GOFMM (geometry-oblivious FMM), a novel
method that creates a hierarchical low-rank
approximation, or "compression,'' of an arbitrary dense
symmetric positive definite (SPD) matrix. For many
applications, GOFMM enables an approximate matrix-vector
multiplication in NlogN or even N time, where N is the
matrix size. Compression requires NlogN 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.'' Also, we introduce
a shared-memory parallel scheme for hierarchical matrix
computations that reduces synchronization barriers. We
present results on the Intel Knights Landing and Haswell
architectures, and on the NVIDIA Pascal architecture for
a variety of matrices.
Download PDF:
here
