The Science of High Performance Algorithms for Hierarchical Matrices PDF Download

Author: Chen-Han Yu (Ph. D.)
Publisher:
ISBN:
Category :
Languages : en
Pages : 230

Get Book Here

Book Description
Many matrices in scientific computing, statistical inference, and machine learning exhibit sparse and low-rank structure. Typically, such structure is exposed by appropriate matrix permutation of rows and columns, and exploited by constructing an hierarchical approximation. That is, the matrix can be written as a summation of sparse and low-rank matrices and this structure repeats recursively. Matrices that admit such hierarchical approximation are known as hierarchical matrices (H-matrices in brief). H-matrix approximation methods are more general and scalable than solely using a sparse or low-rank matrix approximation. Classical numerical linear algebra operations on H-matrices-multiplication, factorization, and eigenvalue decomposition-can be accelerated by many orders of magnitude. Although the literature on H-matrices for problems in computational physics (low-dimensions) is vast, there is less work for generalization and problems appearing in machine learning. Also, there is limited work on high-performance computing algorithms for pure algebraic H-matrix methods. This dissertation tries to address these open problems on building hierarchical approximation for kernel matrices and generic symmetric positive definite (SPD) matrices. We propose a general tree-based framework (GOFMM) for appropriately permuting a matrix to expose its hierarchical structure. GOFMM supports both static and dynamic scheduling, shared memory and distributed memory architectures, and hardware accelerators. The supported algorithms include kernel methods, approximate matrix multiplication and factorization for large sparse and dense matrices.