Solving Linear Systems on a GPU with Hierarchically Off-Diagonal Low-Rank Approximations
DescriptionWe are interested in solving linear systems arising from three applications: (1) kernel methods in machine learning, (2) discretization of boundary integral equations from mathematical physics, and (3) Schur complements formed in the factorization of many large sparse matrices. The coefficient matrices are often data-sparse in the sense that their off-diagonal blocks have low numerical ranks; specifically, we focus on ''hierarchically off-diagonal low-rank (HODLR)'' matrices. We introduce algorithms for factorizing HODLR matrices and for applying the factorizations on a GPU. The algorithms leverage the efficiency of batched dense linear algebra, and they scale nearly linearly with the matrix size when the numerical ranks are fixed. The accuracy of the HODLR-matrix approximation is a tunable parameter, so we can construct high-accuracy fast direct solvers or low-accuracy robust preconditioners. Numerical results show that we can solve problems with several millions of unknowns in a couple of seconds on a single GPU.
Event Type
Paper
TimeThursday, 17 November 20224:30pm - 5pm CST
LocationC140-142
TP
Numerical Algorithms
Scientific Computing
Recorded
Archive
view
