A FAST SEMIDIRECT LEAST SQUARES ALGORITHM FOR HIERARCHICALLY BLOCK SEPARABLE MATRICES∗

Abstract. We present a fast algorithm for linear least squares problems governed by hierarchi-cally 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 ker-nels 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 meth-ods. 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 dimen-sions, 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