Sponsored by
[ Events ]

Activity Search
Sort out
NCTS Seminar on Scientific Computing
09:30 - 10:30, May 17, 2017 (Wednesday)
Room 526, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 526室)
Geometry-Oblivious FMM for Compressing Dense SPD Matrices
Chen-Han Yu (University of Texas at Austin)


We 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.” In this presentation, we also present results of a variety of SPD matrices.


back to list  
 (C) 2017 National Center for Theoretical Sciences