問題タブ [matrix-multiplication]

アルゴリズムとデータ構造の自習をしているところですが、Strassenの行列乗算アルゴリズムのC＃（またはC ++）実装を持っている人がいるかどうか知りたいですか？

私はそれを実行して、それが何をするのかを見て、それがどのように機能するのかについてもっと理解したいと思います。

全て、

マルチスレッド技術を使用して、大きな非正方形（たとえば、サイズが65536xn、n <65536）の非スパース行列を乗算するCまたはC ++ライブラリ（できればオープンソース）の推奨事項を探しています。ありがとう。

-&&

連鎖行列の乗算とは何か、通常の乗算​​とはどのように違うのかを理解しようとしています。私はいくつかの情報源をチェックしましたが、すべてが私が理解できるように非常に学術的に説明されているようです。

最適化された方法で操作を実現するのは動的計画法アルゴリズムの一種だと思いますが、それ以上は進みませんでした。

ありがとう

次の質問がさまざまなフォーラムで何度も行われていることは知っていますが、さまざまな解決策を表示しても問題が解決しないか
、OpenGLES2.0を使用してピラミッドをモデル化しようとしているという意味がわかりませんでした。 iPhone。
ユーザーがタッチスクリーンを使用してこのピラミッドを回転できるようにして、形状のすべての面を表示できるようにしたいと思います。
私は、OpenGL ES 2.0プログラミングガイドの本に記載されているライブラリに触発された、独自のマトリックスユーティリティを使用しています。
2つのユニフォームと2つの属性を受け取る単純な頂点シェーダーがあります。
これが私の頂点シェーダーです：

したがって、レンダリング中に、modelViewと射影行列の2つの行列を作成します。

これが私の射影行列が初期化される方法です：

私のピラミッドの頂点は次のように設定されています：

最後に、これが私の描画コードです：

すべてが正常に機能しているようです。私のピラミッドはここにあり、Z軸を逆方向に移動しています。
図形を回転し始めると問題が発生します。図形がユーザーの周りではなく、ユーザーの周りを回転しているように見えます。
たとえば、画面を左から右にタッチすると、ピラミッドが画面の右端から出て、左端から画面に戻ってくるのが見えます。まるで、まるで自分の周りを一周したかのようです。 p。

私は自分のマトリックス管理コードについてかなり確信しているので、この質問のコードが多すぎるのを避けるために、ここに投稿しないことにしました。必要に応じてあげることができます。

私が間違ったことについて何か考えがありますか？

どうもありがとう ！

トム

F# で 2 つの行列の要素乗算によって要素を並列化しようとしています。考えてもよくわかりません。タスクを作成しようとし続けていますが、コンパイルしたくありません。私の動作しない乱雑なコードは次のとおりです。

非常に大きな行列 (1 億行 x 1 億列) があり、多数の重複値が隣り合っています。例えば：

このような行列をできるだけコンパクトに格納するためのデータ構造/アルゴリズムが必要です。たとえば、上記の行列は、(行列が任意に大きく引き伸ばされたとしても) O(1) スペースしかとらないはずです。これは、各領域が 1 つの値しか持たない一定数の長方形領域しかないためです。

繰り返しは行と下の列の両方で発生するため、行列を行ごとに圧縮する単純な方法では十分ではありません。(これには、行列を格納するために最低でも O(num_rows) のスペースが必要です。)

行列の表現も行ごとにアクセスできる必要があるため、列ベクトルに対して行列の乗算を行うことができます。

PDE である問題を解決しようとしています.3D 離散化ドメインは、6 つの境界のそれぞれに異なる境界条件を持つことができます (またはすべて同じです)。

このスパース行列を圧縮形式にする最良の方法は何ですか? ここでは、CSR が唯一の選択肢になるのでしょうか? ellpack を使用することも考えましたが、境界条件の変更に対してどのように機能するかわかりません。

3D 空間の 2D マトリックス表現について考えると、主に 7 つの対角線で対角線が支配的になりますが、これらの対角線は境界に沿って変化する可能性があります。値を保存する形式と、毎回同じ対角線からのオフセットを使用できるようには思えません。

明らかに、私はこの問題を設定して、多くのベクトル行列乗算を行っている CG ソルバーのキャッシュ フレンドリーにしようとしています。

私は 3x3 行列 M を知っていて、1x3 行列 P を見つけたいと思っています。与えられた条件は次のとおりです。

与えられた[m11 m12 m13; m21 m22 m23; m31 m32 m33]

[p1 p2 p3]Matlabを使用する自明ではない (ゼロではない) 解決策を見つけなければなりません。

コードの一部であるため、Matlab で実行したいと考えています。必要に応じて、条件も指定します。
p1 + p2 + p3 = 1

PS:逆行列を与える「inv」関数を試しましたが、簡単な解決策を提供しています。'svg'関数と'null'関数についても読んだことがありますAx=Bが、私の問題はxA=B型であるため、それらが型を対象としているとは思えません。

私が作成している単純な 2D ゲームでは、マトリックスを使用して z 軸を中心にスプライトを回転させようとしています。スプライトを回転させようとすると、スプライトの原点ではなく、画面の原点 (下、左) を中心に回転しているように見えるため、明らかに何か間違っています。私のクワッドはすでに原点にあるので混乱しているので、変換する必要はないと思いました->回転して元に戻します。コード スニペットと小さなビデオまたは誤った変換を次に示します。

== 更新:

構造体とレンダリング コードは次のとおりです。

oolongengine code.google.com/p/oolongengine/source/browse/trunk/Oolong%20Engine2/Math/Matrix.cpp のマトリックス クラスを使用しています。

すべてのクワッドを変換し、後で OpenGL を使用してレンダリングします。これが私のデータ構造体とレンダリングコードです:

C＃/。NET（さらにはJava）での行列の乗算が非常に遅くなる理由がよくわかりません。

このベンチマークを見てください（ソース）：更新されたベンチマークを見つけようとしています。

C＃の整数および倍精度のパフォーマンスは、MSVC++でコンパイルされたC++に非常に近いものです。ダブルの場合は87％、32ビット整数の場合は99％高速です。かなり良いと思います。しかし、次に行列の乗算を見てください。ギャップはC＃に広がり、約19％速くなります。これは私には理解できないかなり大きな矛盾です。行列の乗算は、単純な数学の集まりにすぎません。どうしてこんなに遅くなっているの？同等の数の単純な浮動小数点または整数演算とほぼ同じくらい高速であるべきではありませんか？

これは、ゲームやXNAで特に懸念されます。この場合、物理エンジンなどで行列とベクトルのパフォーマンスが重要になります。少し前に、Monoはいくつかの気の利いたベクトルと行列クラスを介してSIMD命令のサポートを追加しました。SIMDを使用したC++ほど高速ではありませんが、ギャップを埋め、Monoを手書きのC++よりも高速にします。（ソース）

何が起きてる？

編集：よく見ると、2番目のグラフを読み間違えました。C＃はかなり近いように見えます。最初のベンチマークは、ひどく間違ったことをしているだけですか？申し訳ありませんが、最初のベンチマークのバージョン番号を見逃しました。いつも聞いている「C＃線形代数は遅い」の参考資料として手に取った。私は別のものを見つけようとします。