Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A fast semi-direct least squares algorithm for hierarchically block
  separable matrices   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 \times N$ HBS matrix with $M \geq N$
having bounded off-diagonal block rank, the algorithm has optimal $\mathcal{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
$\mathcal{O} (M + N)$ in 1D, $\mathcal{O} (M + N^{3/2})$ in 2D, and
$\mathcal{O} (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.

32
The categories of this paper are: atom-ph
1
The categories of this paper are: cs
7
The categories of this paper are: hep-th
31
The categories of this paper are: ao-sci
16
The categories of this paper are: stat
21
The categories of this paper are: adap-org
5
The categories of this paper are: gr-qc
17
The categories of this paper are: q-fin
24
The categories of this paper are: dg-ga
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
36
The categories of this paper are: cmp-lg
23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom