A fast semidirect least squares algorithm for hierarchically block separable matrices

DOI10.1137/120902677MaRDI QIDQ2923368zbMATH OpenOpenAlexFDO

Authors Kenneth L. Ho, Leslie Greengard

Publication date 15 October 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.3521

zbMATH Keywords

deferred correctionfast algorithmshierarchically block separable matricesmatrix compressionnumerical examplesQR factorizationradial basis functionsrecursive skeletonizationsparse QR decompositionupdating/downdatingweighted least squares

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Computational methods for sparse matrices (65F50)

Abstract: We present a fast algorithm for linear least squares problems governed by hierarchically block separable (HBS) matrices. Such matrices are generally dense but data-sparse and can describe many important operators including those derived from asymptotically smooth radial kernels that are not too oscillatory. The algorithm is based on a recursive skeletonization procedure that exposes this sparsity and solves the dense least squares problem as a larger, equality-constrained, sparse one. It relies on a sparse QR factorization coupled with iterative weighted least squares methods. In essence, our scheme consists of a direct component, comprised of matrix compression and factorization, followed by an iterative component to enforce certain equality constraints. At most two iterations are typically required for problems that are not too ill-conditioned. For an $MimesN$ HBS matrix with $MgeqN$ having bounded off-diagonal block rank, the algorithm has optimal $mathcalO(M+N)$ complexity. If the rank increases with the spatial dimension as is common for operators that are singular at the origin, then this becomes $mathcalO(M+N)$ in 1D, $mathcalO(M+N^{3/2})$ in 2D, and $mathcalO(M+N^2)$ in 3D. We illustrate the performance of the method on both over- and underdetermined systems in a variety of settings, with an emphasis on radial basis function approximation and efficient updating and downdating.

Recommendations

• A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
• Fast algorithms for hierarchically semiseparable matrices
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• A fast adaptive solver for hierarchically semiseparable representations
• Compressing Rank-Structured Matrices via Randomized Sampling

Cited in

(11)

• Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
• An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
• Hierarchical interpolative factorization for elliptic operators: integral equations
• Rapid error reduction for block Gauss-Seidel based onp-hierarchical basis
• Hierarchical matrix approximation for kernel-based scattered data interpolation
• scientific article; zbMATH DE number 6796233 (Why is no real title available?)
• Factorization, Symmetrization, and Truncated Transformation of Radial Basis Function-GA Stabilized Gaussian Radial Basis Functions
• Broadband recursive skeletonization
• A fast direct solver for boundary integral equations using quadrature by expansion
• Superfast direct inversion of the nonuniform discrete Fourier transform via hierarchically semiseparable least squares
• A fast adaptive solver for hierarchically semiseparable representations

Describes a project that uses

Uses Software

• ATLAS

This page was built for publication: A fast semidirect least squares algorithm for hierarchically block separable matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2923368)