Research

GOFMM (geometry-oblivious Fast Multipole Method) is 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 O(N log N) 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.'' 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.

GOFMM collocates with HMLP at https://github.com/ChenhanYu/hmlp.

[pdf] Geometry-Oblivious FMM for Compressing Dense SPD Matrices, proceedings of SC'17

HMLP is a portable framework that provides high performance, memory efficient matrix-matrix multiplication like operations and their extension based on the BLIS framework. It generalizes C = AB to allow pre- and post-processing on A, B and C with arbitrary types. These extra computation may take no cost during the memory packing process (in transition), or even reduce the memory latency in a matrix-free fashion.

For examples,

• Direct conv2d (in the film) = im2col while packing A and B;
• All neighbor search = selecting column entries of C;
• Strassen algorithm = adding submatrices while packing A and B.

Currently, HMLP has implementations on Intel x86_64, Knights Landing, ARM and NVIDIA GPU. We may further support other architectures in the future.

https://github.com/ChenhanYu/hmlp

[pdf] Performance Optimization for the K-Nearest Neighbors Kernel on x86 Architectures, proceedings of SC'15.

Multifrontal methods are efficient and widely used to solve large-scale sparse linear systems. These methods transform the computations involving the large and sparse linear system into many smaller and dense sub-matrices called frontals. [1,2] show how these methods can be parallelized efficiently on a modern heterogenous architecture.

[1] Adaptive Performance Models and Workload Distribution Algorithms for Optimizing Hybrid CPU-GPU Multifrontal Solver, Computers & Mathematics with Applications (CAMWA), 2014

[2] A CPU-GPU Hybrid Approach for the Unsymmetric Multifrontal Method, Journal of Parallel Computing, 2011