A fast semidirect least squares algorithm for hierarchically block separable matrices

Kenneth L. Ho, Leslie Greengard

Research output: Contribution to journalArticlepeer-review


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 M×N HBS matrix with M > N having bounded off-diagonal block rank, the algorithm has optimal O(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 O(M + N) in one dimension, O(M + N3/2) in two dimensions, and O(M + N2) in three dimensions. We illustrate the performance of the method on both overdetermined and underdetermined systems in a variety of settings, with an emphasis on radial basis function approximation and efficient updating and downdating.

Original languageEnglish (US)
Pages (from-to)725-748
Number of pages24
JournalSIAM Journal on Matrix Analysis and Applications
Issue number2
StatePublished - 2014


  • Deferred correction
  • Fast algorithms
  • Matrix compression
  • Radial basis functions
  • Recursive skeletonization
  • Sparse QR decomposition
  • Updating/downdating
  • Weighted least squares

ASJC Scopus subject areas

  • Analysis


Dive into the research topics of 'A fast semidirect least squares algorithm for hierarchically block separable matrices'. Together they form a unique fingerprint.

Cite this