Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Sparse matrix factorizations for fast linear solvers with application to
  Laplacian systems   In solving a linear system with iterative methods, one is usually confronted
with the dilemma of having to choose between cheap, inefficient iterates over
sparse search directions (e.g., coordinate descent), or expensive iterates in
well-chosen search directions (e.g., conjugate gradients). In this paper, we
propose to interpolate between these two extremes, and show how to perform
cheap iterations along non-sparse search directions, provided that these
directions can be extracted from a new kind of sparse factorization. For
example, if the search directions are the columns of a hierarchical matrix,
then the cost of each iteration is typically logarithmic in the number of
variables. Using some graph-theoretical results on low-stretch spanning trees,
we deduce as a special case a nearly-linear time algorithm to approximate the
minimal norm solution of a linear system $Bx= b$ where $B$ is the incidence
matrix of a graph. We thereby can connect our results to recently proposed
nearly-linear time solvers for Laplacian systems, which emerge here as a
particular application of our sparse matrix factorization.

18
The categories of this paper are: econ
7
The categories of this paper are: hep-th
6
The categories of this paper are: astro-ph
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
22
The categories of this paper are: chao-dyn
36
The categories of this paper are: cmp-lg
5
The categories of this paper are: gr-qc
21
The categories of this paper are: adap-org
12
The categories of this paper are: nucl-th
32
The categories of this paper are: atom-ph
24
The categories of this paper are: dg-ga
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
19
The categories of this paper are: eess
29
The categories of this paper are: funct-an