Fugu-MT 論文翻訳(概要): Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles

論文の概要: Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles

arxiv url: http://arxiv.org/abs/2101.07464v2
Date: Fri, 22 Jan 2021 00:15:14 GMT
ステータス: 処理完了
システム内更新日: 2021-03-26 07:55:13.687615
Title: Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles
Title（参考訳）: Houseer Dice:ガウスおよびランダム直交アンサンブルのダイナミクスをマトリックスフリーでシミュレーションするアルゴリズム
Authors: Yue M. Lu
Abstract要約: Householder Dice (HD) は、高密度ランダム行列アンサンブルのダイナミクスを翻訳不変特性でシミュレートするアルゴリズムである。 HDアルゴリズムのメモリとコストはそれぞれ$mathcalO(nT)$と$mathcalO(nT2)$である。数値結果は、高次元ランダムシステムの研究における新しい計算ツールとしてのHDアルゴリズムの約束を示しています。
参考スコア（独自算出の注目度）: 12.005731086591139
License: http://creativecommons.org/licenses/by/4.0/
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.
Abstract（参考訳）: 本稿では,変換不変な性質を持つ密度乱数行列アンサンブルのダイナミクスをシミュレートする,houseer dice (hd) という新しいアルゴリズムを提案する。例えば、ガウスアンサンブル、ハール分布のランダム直交アンサンブル、それらの複素値アンサンブルなどがある。最初にアンサンブルから密な$n \times n$行列を生成するシミュレーションへの「直接」アプローチは、空間と時間において少なくとも$\mathcal{o}(n^2)$リソースを必要とする。 hdアルゴリズムは、遅延決定の原理を用いて、この$\mathcal{o}(n^2)$のボトルネックを克服する。このマトリクスフリーアルゴリズムの中心は、(ランダムな)ハウスリフレクターの適応的かつ再帰的な構成である。これらの直交変換は行列アンサンブルの群対称性を利用し、同時にダイナミクスによって引き起こされる統計相関を維持している。 HDアルゴリズムのメモリと計算コストはそれぞれ$\mathcal{O}(nT)$と$\mathcal{O}(nT^2)$であり、$T$は反復数である。ほぼ常にそうである$T \ll n$の場合、新しいアルゴリズムは実行時とメモリフットプリントを大幅に削減する。数値実験により,高次元ランダム系の研究における新しい計算ツールとしてのhdアルゴリズムの期待が示された。
全文参考訳へのリンク