George Biros (University of Texas at Austin), Applied Mathematics Colloquium

Tea at 3:30 in Phillips Hall 330

Title:  Fast algorithms for hierarchical matrices.  George Biros (with  William B. March, Dhairya Malhotra, and Chenhan Yu)

Abstract:  Hierarchical matrices are matrices that have a large number of blocks that admit a low-rank approximation. There are many ways to construct these approximations, but the most natural ones are based on recursion. Once an approximation has been constructed, it can be used to accelerate matrix-vector multiplications and construct preconditioners. Operations that typically require quadratic or cubic complexity on the size of the matrix can be reduced to linear complexity — up to a logarithmic prefactor. Hierarchical matrices appear in computational physics (Green’s functions) and machine learning (kernel methods). Many famous algorithms for constructing hierarchical matrices exist: treecodes, kernel matrices, Gram matrices, N-body methods.

In this talk, I will present some examples of applications of hierarchical matrices in Stokesian fluid mechanics, and supervised learning. Then I will present a review of ASKIT (approximate skeletonization kernel independent treecode), a method that we recently developed in my group. The main feature of ASKIT is its dependence on the local intrinsic dimension of the dataset as opposed to the dimension of the ambient space of the dataset.  We will compare ASKIT with the Nystrom method and discuss its application to learning problems in high-dimensions. As a highlight, we will report results for Gaussian kernel matrices with 100 million points in 64 dimensions, and for eight million points in 1000 dimensions.