  This paper proposes a new algorithm, named Householder Dice (HD), for
simulating dynamics on dense random matrix ensembles with translation-invariant
properties. Examples include the Gaussian ensemble, the Haar-distributed random
orthogonal ensemble, and their complex-valued counterparts. A "direct" approach
to the simulation, where one first generates a dense $n \times n$ matrix from
the ensemble, requires at least $\mathcal{O}(n^2)$ resource in space and time.
The HD algorithm overcomes this $\mathcal{O}(n^2)$ bottleneck by using the
principle of deferred decisions: rather than fixing the entire random matrix in
advance, it lets the randomness unfold with the dynamics. At the heart of this
matrix-free algorithm is an adaptive and recursive construction of (random)
Householder reflectors. These orthogonal transformations exploit the group
symmetry of the matrix ensembles, while simultaneously maintaining the
statistical correlations induced by the dynamics. The memory and computation
costs of the HD algorithm are $\mathcal{O}(nT)$ and $\mathcal{O}(nT^2)$,
respectively, with $T$ being the number of iterations. When $T \ll n$, which is
nearly always the case in practice, the new algorithm leads to significant
reductions in runtime and memory footprint. Numerical results demonstrate the
promise of the HD algorithm as a new computational tool in the study of
high-dimensional random systems.
