問題タブ [matrix-multiplication]

行列乗算のパフォーマンスを比較するためだけに、Java で 2 つの行列クラスを作成しました。1 つのクラス (Mat1)には、行列のdouble[][] A行が であるメンバーが格納されます。もう一方のクラス (Mat2) には、 が格納され、は の転置です。iA[i]ATTA

正方行列 M があり、 の積が欲しいとしましょうM.mult(M)。製品を呼び出しますP。

M が Mat1 インスタンスの場合、使用されるアルゴリズムは単純なものでした。

M が私が使用した Mat2 の場合:

これは同じアルゴリズムですT[j][k]==A[k][j]。1000x1000 行列では、2 番目のアルゴリズムは私のマシンで約 1.2 秒かかりますが、最初のアルゴリズムは少なくとも 25 秒かかります。2番目の方が速いと思っていましたが、それほどではありません。問題は、なぜこれほど高速なのかということです。

私の唯一の推測は、データが 1 ワードよりも大きなチャンクでキャッシュに取り込まれるため、2 番目のアルゴリズムが CPU キャッシュをより有効に利用できるということです。すぐ下の行に移動してキャッシュします（配列は行の優先順で格納されるため、メモリ内には約 1000 ワードです）。キャッシュされるデータはありません。

誰かに尋ねたところ、メモリ アクセス パターンがより使いやすいためだと彼は考えていました (つまり、2 番目のバージョンでは TLB のソフト フォールトが少なくなるからです)。私はこれについてまったく考えていませんでしたが、TLB フォールトがどのように減少するかを見ることができます。

それで、それはどれですか？または、パフォーマンスの違いには他の理由がありますか?

多分あなたは次の問題を解決する方法についての考えを持っているでしょう。

ジョンは息子のジョニーに数学のおもちゃを買うことにしました。彼の最も好きなおもちゃの1つは、さまざまな色のブロックです。ジョンはCの異なる色のブロックを購入することにしました。色ごとに、彼はグーゴル（10 ^ 100）ブロックを購入します。同じ色のすべてのブロックは同じ長さです。ただし、異なる色のブロックは長さが異なる場合があります。Jhonnyは、これらのブロックを使用して1xnの大きなブロックを作成することにしました。彼はこれをどのように行うことができるのか疑問に思います。色が異なる位置がある場合、2つの方法が異なると見なされます。この例は、サイズ5の赤いブロック、サイズ3の青いブロック、サイズ3の緑のブロックを示しています。これは、長さ11の大きなブロックを作成する12の方法があることを示しています。

各テストケースは、1≤C≤100の整数で始まります。次の行はc個の整数で構成されています。i番目の整数1≤leni≤750は、i番目の色の長さを示します。次の行は正の整数N≤10^15です。

この問題は、T<=25のテストケースでは20秒で解決する必要があります。答えを計算する必要がありますMOD 100000007（素数）。

これは、 Coppersmith-Winogradアルゴリズムと高速べき乗を使用して、O（N ^ 2.376 * log（max（leni）））で比較的効率的に解くことができる行列指数問題に推論できます。しかし、Coppersmith-Winogradは大きな定数係数を暗示しているため、より効率的なアルゴリズムが必要と思われます。他に何かアイデアはありますか？数論または分割統治問題である可能性があります

次の行列乗算を行う行列乗算コードがあります。ここで、行列 A * 行列 B = 行列 C

今、私はそれをマルチスレッドの行列乗算に変えたいと思っています。私のコードは次のとおりです:

私は構造体を使用します

私の方法は

そして私のメインの中にあるのは

しかし、最初の行列乗算と同じ結果が得られないようです (これは正しいです) 誰かが私を正しい方向に向けることができますか?

その結果を得るためのモードや方法はありますか? 投稿で私の画像を見てください 私の結果が縦の数字（黒い線）と横の数字（赤い線）の積であることを望みます

いくつかの図を含む OpenGL シーンがあります。「レンダリング」後に図形の頂点の位置を計算するために何をする必要があるか教えてください。おそらくいくつかの行列を手動で乗算する必要があることはわかっていますが、どれがどのように乗算されるのかわかりません。

助けてくれてありがとう！

私は行列の数学がひどいですが、1つをスケーリングする必要がある状況があります。マトリックスはここで定義されたカスタムクラスのインスタンスであり、私のスケーリングオブジェクトは3つのfloat（x、y、z）を含むベクトルです。私はすでにその道を進んでいて、関係する数学を理解していないので、一般的な説明ではなく、実際に必要なコードが欲しいです。幸いなことに、マトリックスをスケーリングできれば、私が達成しようとしていることはかなり簡単です。

ここで明確にするために、私が更新しているコードがあります。リンクされたオブジェクトの階層を相対変換で繰り返し、mat＆を絶対変換に更新します。

}

この単純なアルゴリズムで行列乗算を実行しています。より柔軟にするために、動的に作成された配列を含むマトリックスにオブジェクトを使用しました。

このソリューションを静的配列を使用した最初のソリューションと比較すると、4 倍遅くなります。データ アクセスを高速化するにはどうすればよいですか? アルゴリズムを変更したくありません。

---

編集

---

上記の質問を修正しました！以下に完全なソースコードを追加し、あなたのアドバイスのいくつかを試しました:

• スワップkとjループの反復 -> パフォーマンスの向上
• 宣言さdim()れoperator()() たinline-> パフォーマンスの向上
• const 参照による引数の受け渡し ->パフォーマンスの低下! なぜ？なので使いません。

パフォーマンスは、以前のプログラムとほぼ同じになりました。もう少し改善が必要かもしれません。

しかし、別の問題があります。関数でメモリ エラーが発生しますmult_strassen(...)。なんで？
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

---

古いプログラム
main.c http://pastebin.com/qPgDWGpW

c99 main.c -o matrix -O3

---

新しいプログラム
matrix.h http://pastebin.com/TYFYCTY7
matrix.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

g++ main.cpp matrix.cpp -o matrix -O3.

---

編集

---

ここにいくつかの結果があります。標準アルゴリズム (std)、j と k ループの順序を入れ替えたもの (swap)、ブロック サイズ 13 のブロック アルゴリズム (block) の比較。

C++ で行列乗算用のStrassen アルゴリズムを実装しようとしましたが、期待どおりの結果が得られませんでした。ご覧のとおり、strassen は常に標準の実装よりも時間がかかり、次元が 2 の累乗の場合のみ、標準の実装と同じくらい高速です。何が悪かったのか？

---

プログラム
matrix.h http://pastebin.com/TYFYCTY7
matrix.cpp http://pastebin.com/wYADLJ8Y
main.cpp http://pastebin.com/48BSqGJr

g++ main.cpp matrix.cpp -o matrix -O3.

R で行列を操作する場合、それぞれ cbind と rbind を使用して、それらを並べて配置したり、互いの上に積み重ねたりすることができます。他の次元で行列または配列を積み重ねるための同等の関数は何ですか?

たとえば、次の例では、それぞれが 4 つの要素を持つ 2x2 行列のペアを作成します。

それらを 8 つの要素を持つ 2x2x2 配列に結合するコードは何ですか?