  The efficient and accurate QR decomposition for matrices with hierarchical
low-rank structures, such as HODLR and hierarchical matrices, has been
challenging. Existing structure-exploiting algorithms are prone to numerical
instability as they proceed indirectly, via Cholesky decompositions or a block
Gram-Schmidt procedure. For a highly ill-conditioned matrix, such approaches
either break down in finite-precision arithmetic or result in significant loss
of orthogonality. Although these issues can sometimes be addressed by
regularization and iterative refinement, it would be more desirable to have an
algorithm that avoids these detours and is numerically robust to
ill-conditioning. In this work, we propose such an algorithm for HODLR
matrices. It achieves accuracy by utilizing Householder reflectors. It achieves
efficiency by utilizing fast operations in the HODLR format in combination with
compact WY representations and the recursive QR decomposition by Elmroth and
Gustavson. Numerical experiments demonstrate that our newly proposed algorithm
is robust to ill-conditioning and capable of achieving numerical orthogonality
down to the level of roundoff error.
