  We present new algorithms for the randomized construction of hierarchically
semi-separable matrices, addressing several practical issues. The HSS
construction algorithms use a partially matrix-free, adaptive randomized
projection scheme to determine the maximum off-diagonal block rank. We develop
both relative and absolute stopping criteria to determine the minimum dimension
of the random projection matrix that is sufficient for the desired accuracy.
Two strategies are discussed to adaptively enlarge the random sample matrix:
repeated doubling of the number of random vectors, and iteratively incrementing
the number of random vectors by a fixed number. The relative and absolute
stopping criteria are based on probabilistic bounds for the Frobenius norm of
the random projection of the Hankel blocks of the input matrix. We discuss
parallel implementation and computation and communication cost of both
variants. Parallel numerical results for a range of applications, including
boundary element method matrices and quantum chemistry Toeplitz matrices, show
the effectiveness, scalability and numerical robustness of the proposed
algorithms.
