  Hierarchical matrices approximate a given matrix by a decomposition into
low-rank submatrices that can be handled efficiently in factorized form.
$\mathcal{H}^2$-matrices refine this representation following the ideas of fast
multipole methods in order to achieve linear, i.e., optimal complexity for a
variety of important algorithms. The matrix multiplication, a key component of
many more advanced numerical algorithms, has so far proven tricky: the only
linear-time algorithms known so far either require the very special structure
of HSS-matrices or need to know a suitable basis for all submatrices in
advance. In this article, a new and fairly general algorithm for multiplying
$\mathcal{H}^2$-matrices in linear complexity with adaptively constructed bases
is presented. The algorithm consists of two phases: first an intermediate
representation with a generalized block structure is constructed, then this
representation is re-compressed in order to match the structure prescribed by
the application. The complexity and accuracy are analysed and numerical
experiments indicate that the new algorithm can indeed be significantly faster
than previous attempts.
