論文の概要: Fast Matrix Multiplication Without Tears: A Constraint Programming
Approach
- arxiv url: http://arxiv.org/abs/2306.01097v1
- Date: Thu, 1 Jun 2023 19:15:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 18:12:12.500762
- Title: Fast Matrix Multiplication Without Tears: A Constraint Programming
Approach
- Title（参考訳）: 涙のない高速な行列乗算:制約プログラミングアプローチ
- Authors: Arnaud Deza, Chang Liu, Pashootan Vaezipoor, Elias B. Khalil
- Abstract要約: $N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。
これにより、高速行列乗法における制約満足度問題が発生する。
本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
- 参考スコア（独自算出の注目度）: 8.52818380743467
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is known that the multiplication of an $N \times M$ matrix with an $M
\times P$ matrix can be performed using fewer multiplications than what the
naive $NMP$ approach suggests. The most famous instance of this is Strassen's
algorithm for multiplying two $2\times 2$ matrices in 7 instead of 8
multiplications. This gives rise to the constraint satisfaction problem of fast
matrix multiplication, where a set of $R < NMP$ multiplication terms must be
chosen and combined such that they satisfy correctness constraints on the
output matrix. Despite its highly combinatorial nature, this problem has not
been exhaustively examined from that perspective, as evidenced for example by
the recent deep reinforcement learning approach of AlphaTensor. In this work,
we propose a simple yet novel Constraint Programming approach to find
non-commutative algorithms for fast matrix multiplication or provide proof of
infeasibility otherwise. We propose a set of symmetry-breaking constraints and
valid inequalities that are particularly helpful in proving infeasibility. On
the feasible side, we find that exploiting solver performance variability in
conjunction with a sparsity-based problem decomposition enables finding
solutions for larger (feasible) instances of fast matrix multiplication. Our
experimental results using CP Optimizer demonstrate that we can find fast
matrix multiplication algorithms for matrices up to $3\times 3$ in a short
amount of time.
- Abstract（参考訳）: $N \times M$行列と$M \times P$行列の乗算は、単純な$NMP$アプローチが示唆するよりも少ない乗算で行うことが知られている。
最も有名な例はストラッセンのアルゴリズムで、8つの乗法の代わりに 2$ 2$ の行列を 7 で乗算する。
これにより、高速行列乗法における制約満足度問題が発生し、出力行列上の正しさ制約を満たすために、$R < NMP$ 乗法項の集合を選択して組み合わせなければならない。
組み合わせ性が高いにもかかわらず、最近のAlphaTensorの深層強化学習アプローチのように、この問題は、その観点から徹底的に検討されていない。
本研究では, 高速行列乗算のための非可換アルゴリズムや, 非可換性を証明するための制約プログラミング手法を提案する。
本稿では, 対称性を破る制約と有効不等式を提案する。
実現可能な面では、スパース性に基づく問題分解と組み合わせた解法性能変動の活用により、高速行列乗算のより大きな(実現可能な)インスタンスの解を見つけることができる。
cpオプティマイザを用いた実験結果から,行列の高速行列乗算アルゴリズムを,短時間で3-\times 3$まで得ることができた。
関連論文リスト
- 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) - Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。
ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
論文 参考訳（メタデータ） (2024-01-10T18:38:43Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - 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) - Multiplying Matrices Without Multiplying [0.0]
行列の乗算は機械学習における最も基本的で計算集約的な操作の1つである。
本稿では,既存の手法を大幅に上回る学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-21T05:08:54Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - What if Neural Networks had SVDs? [66.91160214071088]
様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。
本稿では,行列演算を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-29T12:58:52Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。