  Many matrices appearing in numerical methods for partial differential
equations and integral equations are rank-structured, i.e., they contain
submatrices that can be approximated by matrices of low rank. A relatively
general class of rank-structured matrices are $\mathcal{H}^2$-matrices: they
can reach the optimal order of complexity, but are still general enough for a
large number of practical applications. We consider algorithms for performing
algebraic operations with $\mathcal{H}^2$-matrices, i.e., for approximating the
matrix product, inverse or factorizations in almost linear complexity. The new
approach is based on local low-rank updates that can be performed in linear
complexity. These updates can be combined with a recursive procedure to
approximate the product of two $\mathcal{H}^2$-matrices, and these products can
be used to approximate the matrix inverse and the LR or Cholesky factorization.
Numerical experiments indicate that the new method leads to preconditioners
that require $\mathcal{O}(n)$ units of storage, can be evaluated in
$\mathcal{O}(n)$ operations, and take $\mathcal{O}(n \log n)$ operations to set
up.
