Abstract
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.
Introduction
Simulating iterative dynamics on high-dimensional random matrices is a cornerstone of research in statistical physics, signal processing, and machine learning. However, traditional "direct" simulation methods face a significant bottleneck: they require generating and storing a dense $n \times n$ matrix, leading to $O(n^2)$ costs in both time and memory. For dimensions exceeding $10^5$, these requirements quickly surpass the capabilities of standard hardware, forcing researchers to rely on smaller systems and extensive Monte Carlo averaging.
This paper introduces Householder Dice (HD), a matrix-free algorithm that overcomes these limitations. By generating randomness "on-the-fly," HD reduces memory complexity to $O(nT)$ and time complexity to $O(nT^2)$, where $T$ is the number of iterations. This shift allows for the simulation of systems with millions of dimensions on a standard laptop.
The Householder Dice Algorithm
The core of the HD algorithm is the principle of deferred decisions. Rather than fixing the entire random matrix at the start, the algorithm reveals only the necessary components as the dynamics unfold.
Technically, HD leverages an adaptive and recursive construction of Householder reflectors. These orthogonal transformations exploit the group symmetries (rotational and translation invariance) of ensembles like the Gaussian (Ginibre) or Haar-distributed orthogonal matrices. At each iteration $t$, the random matrix is represented as a sum of a low-rank part—derived from previous steps—and a "hidden" random part that has not yet interacted with the dynamics.
Crucially, HD is not an approximation; it is statistically equivalent to the direct approach. The trajectories generated by HD are distributionally identical to those produced by full matrix-vector multiplications.
Performance and Applications
The computational advantages of Householder Dice are most evident at high dimensions. As shown in the scaling analysis above, the runtime of the direct approach scales quadratically with $n$, eventually hitting memory limits. In contrast, HD scales linearly with $n$ for a fixed number of iterations $T$.
In practical tests, HD simulated a system with $n = 10^7$ in approximately 92 seconds. A direct simulation of the same scale would require nearly 90 days of computation and petabytes of memory. This efficiency allows researchers to eliminate finite-size effects by working directly at scales where single-trial results match asymptotic theoretical predictions. For example, in Generalized Linear Models (GLMs), HD can capture sharp phase transitions in a single trial that would otherwise be obscured by noise in smaller systems.
Conclusion
While Householder Dice offers dramatic speedups, its efficiency is contingent on the regime $T \ll n$. If the number of iterations $T$ approaches the dimension $n$, the $O(nT^2)$ time complexity becomes prohibitive. Additionally, the algorithm currently requires the matrix ensemble to possess rotational or translation invariance. Despite these constraints, HD stands as a powerful new tool for exploring the "infinite-dimensional" limit of random systems, providing a scalable path for future research in high-dimensional probability.
Summary updated