論文の概要: Computing rank-revealing factorizations of matrices stored out-of-core
- arxiv url: http://arxiv.org/abs/2002.06960v2
- Date: Wed, 4 Mar 2020 12:18:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 13:11:59.774751
- Title: Computing rank-revealing factorizations of matrices stored out-of-core
- Title（参考訳）: コア外に格納された行列の階数-階数分解
- Authors: Nathan Heavner, Per-Gunnar Martinsson, Gregorio Quintana-Ort\'i
- Abstract要約: 本稿では,RAM に収まるには大きすぎる行列の階乗分解を効率よく計算するアルゴリズムについて述べる。
新しいアルゴリズムは、ハードディスクに格納されたデータを処理する場合と、従来のアルゴリズムがメインメモリに格納されたデータに対する場合とほぼ同速である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper describes efficient algorithms for computing rank-revealing
factorizations of matrices that are too large to fit in RAM, and must instead
be stored on slow external memory devices such as solid-state or spinning disk
hard drives (out-of-core or out-of-memory). Traditional algorithms for
computing rank revealing factorizations, such as the column pivoted QR
factorization, or techniques for computing a full singular value decomposition
of a matrix, are very communication intensive. They are naturally expressed as
a sequence of matrix-vector operations, which become prohibitively expensive
when data is not available in main memory. Randomization allows these methods
to be reformulated so that large contiguous blocks of the matrix can be
processed in bulk. The paper describes two distinct methods. The first is a
blocked version of column pivoted Householder QR, organized as a "left-looking"
method to minimize the number of write operations (which are more expensive
than read operations on a spinning disk drive). The second method results in a
so called UTV factorization which expresses a matrix $A$ as $A = U T V^*$ where
$U$ and $V$ are unitary, and $T$ is triangular. This method is organized as an
algorithm-by-blocks, in which floating point operations overlap read and write
operations. The second method incorporates power iterations, and is
exceptionally good at revealing the numerical rank; it can often be used as a
substitute for a full singular value decomposition. Numerical experiments
demonstrate that the new algorithms are almost as fast when processing data
stored on a hard drive as traditional algorithms are for data stored in main
memory. To be precise, the computational time for fully factorizing an $n\times
n$ matrix scales as $cn^{3}$, with a scaling constant $c$ that is only
marginally larger when the matrix is stored out of core.
- Abstract（参考訳）: 本稿では,RAMに収まるには大きすぎる行列の階乗分解を効率よく計算するアルゴリズムについて述べる。
列のピボットQR因子分解や行列の完全特異値分解の計算技術のような階数分解を計算するための伝統的なアルゴリズムは非常に通信集約的である。
これらは行列ベクトル演算のシーケンスとして自然に表現され、メインメモリでデータが利用できない場合、非常に高価になる。
ランダム化により、これらの手法は行列の大きな連続ブロックをバルクで処理できるように再構成される。
この論文は2つの異なる方法を説明する。
ひとつはブロックされたcolumn pivoted householder qrで、書き込み操作数(回転ディスクドライブの読み取り操作よりも高価)を最小限に抑えるための"左に見える"メソッドとして構成されている。
2つ目の方法は、いわゆる utv 因子分解で、行列 $a$ as $a = u t v^*$ ここで $u$ と $v$ はユニタリであり、$t$ は三角である。
この方法は、浮動小数点演算が読み書き操作と重なるアルゴリズム・バイ・ブロックとして構成される。
第2の方法は、パワーイテレーションを組み込んでおり、数値ランクを明らかにするのに非常に適しており、完全な特異値分解の代用としてしばしば用いられる。
数値実験により、従来のアルゴリズムはメインメモリに格納されたデータと同じ速度でハードドライブに格納されたデータを処理することができる。
正確に言うと、$n\times n$マトリクスを完全に分解する計算時間は$cn^{3}$となり、スケーリング定数 $c$ はマトリクスがコアに格納されていればわずかに大きくなる。
関連論文リスト
- Optimized Inference for 1.58-bit LLMs: A Time and Memory-Efficient Algorithm for Binary and Ternary Matrix Multiplication [8.779871128906787]
大規模言語モデル(LLM)は、高度な計算インフラに依存しながら推論の非効率さに悩まされる。
3次重み付き1.58ビットLLMの推論時間とメモリ効率を改善するアルゴリズムを提案する。
その結果,時間とメモリの両面でのアプローチの優位性が確認され,推論時間は最大29倍,メモリ使用量は最大6倍に短縮された。
論文 参考訳（メタデータ） (2024-11-10T04:56:14Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - A Structured Sparse Neural Network and Its Matrix Calculations Algorithm [0.0]
非対称な三対角行列を導入し, 対角方向のスパース成分とオフセット部分および超対角線を導入した。
行列逆が存在しない場合には、最小二乗型擬逆が提供される。
その結果,行列のサイズが大きくなると計算コストが著しく向上することがわかった。
論文 参考訳（メタデータ） (2022-07-02T19:38:48Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - Sparse Factorization of Large Square Matrices [10.94053598642913]
本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。
近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。
近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-09-16T18:42:21Z) - Multiplying Matrices Without Multiplying [0.0]
行列の乗算は機械学習における最も基本的で計算集約的な操作の1つである。
本稿では,既存の手法を大幅に上回る学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-21T05:08:54Z) - Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication [1.9518237361775532]
大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
論文 参考訳（メタデータ） (2020-06-25T18:28:10Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。