  Although some preconditioners are available for solving dense linear systems,
there are still many matrices for which preconditioners are lacking, in
particular in cases where the size of the matrix $N$ becomes very large. There
remains hence a great need to develop general purpose preconditioners whose
cost scales well with the matrix size $N$. In this paper, we propose a
preconditioner with broad applicability and with cost $\mathcal{O}(N)$ for
dense matrices, when the matrix is given by a smooth kernel. Extending the
method using the same framework to general $\mathcal{H}^2$-matrices is
relatively straightforward. These preconditioners have a controlled accuracy
(machine accuracy can be achieved if needed) and scale linearly with $N$. They
are based on an approximate direct solve of the system. The linear scaling of
the algorithm is achieved by means of two key ideas. First, the
$\mathcal{H}^2$-structure of the dense matrix is exploited to obtain an
extended sparse system of equations. Second, fill-ins arising when performing
the elimination are compressed as low-rank matrices if they correspond to
well-separated interactions. This ensures that the sparsity pattern of the
extended sparse matrix is preserved throughout the elimination, hence resulting
in a very efficient algorithm with $\mathcal{O}(N \log(1/\varepsilon)^2 )$
computational cost and $\mathcal{O}(N \log 1/\varepsilon )$ memory requirement,
for an error tolerance $0 < \varepsilon < 1$. The solver is inexact, although
the error can be controlled and made as small as needed. These solvers are
related to ILU in the sense that the fill-in is controlled. However, in ILU,
most of the fill-in is simply discarded whereas here it is approximated using
low-rank blocks, with a prescribed tolerance. Numerical examples are discussed
to demonstrate the linear scaling of the method and to illustrate its
effectiveness as a preconditioner.
