A fast semidirect least squares algorithm for hierarchically block separable matrices

DOI10.1137/120902677zbMATH Open1301.65027arXiv1212.3521OpenAlexW2041636959MaRDI QIDQ2923368

Author name not available (Why is that?)

Publication date: 15 October 2014

Published in: (Search for Journal in Brave)

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.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)