問題タブ [sparse-matrix]

グラフ内のノード間の接続をリストする大きな csv ファイルがあります。例：

0001,95784
0001,98743
0002,00082
0002,00091

したがって、これは、ノード ID 0001 がノード 95784 および 98743 などに接続されていることを意味します。これを numpy の疎行列に読み込む必要があります。これどうやってするの？私はPythonが初めてなので、これに関するチュートリアルも役立ちます。

そこにRユーザーがいるかどうかはわかりませんが、念のため:

私は R の初心者であり、親切にも次の R コード スニペットを「手渡されました」:

これを自分のデータセットで実行しようとすると、システムが狂ったようにスラッシングしてスワップしました。これには単純な理由があることに気付きました。ファイル freq-matrix には大きな (22GB) 行列が含まれており、それをメモリに読み込もうとしていたのです。

私はMatrixパッケージを使用するように言われました。なぜなら、freq-matrix には至る所に非常に多くのゼロがあり、そのようなケースをうまく処理できるからです。それは役に立ちますか？もしそうなら、このコードを変更する方法についてのヒントは大歓迎です。私は R の経験がなく、サイトで入手できる紹介 PDF を読み始めたところです。

どうもありがとう

~l

優れた (最善の場合、積極的に維持されている) C++ マトリックス ライブラリを探しています。有理数の複合体を数値型として使用したいので、テンプレート化する必要があります。私が扱っている行列は、主にまばらでユニタリです。

ライブラリを提案し、それらを使用する理由を簡単に説明してください.

編集：

私が扱っている主な操作は、行列の乗算、ベクトルとクロネッカー積によるスカラー乗算です。行列のサイズは指数関数的であり、少なくとも 1024x1024 エントリまでの行列を処理できるようにしたいと考えています。

私は二次元行列を持っています。私の行列はまばらです。パフォーマンスの問題に直面しています。プログラムのパフォーマンスを向上させるためにスパース行列を処理するために Java で使用できる API またはクラスを教えてください。

たとえば、私が欲しい

Numpy では、行列の行と列を取得するために ix_() が使用されますが、スパース行列では機能しないようです。たとえば、次のコードは密行列を使用しているため機能します。

ix_() を使用して、0 番目と 2 番目の行と列に対応する要素にインデックスを付けました。これにより、マトリックスの 4 つのコーナーが得られます。

問題は、ix_ がスパース行列では機能しないように見えることです。前のコードから続けて、次のことを試します。

この例外があることを示す大きなエラーメッセージが表示されます。

SciPy が提供する他の疎行列形式でこれを試しましたが、すべてが同じ例外を発生させるわけではありませんが、いずれも ix_() で機能しないようです。

私が示した例では、それほど大きくも疎でもなかったマトリックスを使用しましたが、私が扱っているものは非常に疎で潜在的に非常に大きいため、要素を 1 つずつリストするのは賢明ではないようです。

SciPy で疎行列を使用してこの種のインデックス作成を行う (できれば簡単な) 方法を知っている人はいますか? それとも、この機能はこれらの疎行列に組み込まれていませんか?

大規模なスパース反復 (共役勾配、MINRES、GMRES など) 線形代数システムを解くための優れたライブラリは何ですか? 私はよく自分自身のルーチンをコーディングしてきましたが、人々が好む「既製」のパッケージを知りたいと思っています。PETSc、TAUCS、IML++、その他いくつかのことを聞いたことがあります。これらがどのように積み重なっているのか、他に何があるか疑問に思っています。私の好みは、使いやすさと、無料で入手できるソフトウェアです。

長方形の領域でポアソン方程式を解こうとしていますが、これはAx = bのような線形問題になりますが、境界条件がわかっているので、解の値を持つノードがあります。私の質問は...xの座標のいくつかがわかっていて、未決定の値がこれらにも依存している場合、スパースシステムAx = bをどのように解くことができますか？そもそも解決策のいくつかを知っていることを除けば、通常の解決策と同じです。

ありがとう！

予備行列を解くには、

一般に、マトリックスはどのくらいの大きさでなければなりませんか（経験則として）

学群降下のような方法がブルート フォース ソルバー (スパース性を利用しない) よりも高速になるには?

Gauss-Seidel法を使用してスパース行列ソルバーを作成しています。プロファイリングにより、プログラムの時間の約半分がソルバー内で費やされていると判断しました。パフォーマンスが重要な部分は次のとおりです。

関連するすべての配列はfloatタイプです。実際には、それらは配列ではなく、オーバーロードされた[]演算子を持つオブジェクトであり、（私は）最適化する必要がありますが、次のように定義されています。

の場合d_nx = d_ny = 128、これはIntel i7 920で1秒間に約3500回実行できます。これは、内側のループ本体が1秒間に3500 * 128 * 128=5,700万回実行されることを意味します。いくつかの単純な計算しか含まれていないので、それは2.66GHzプロセッサの低い数値として私を驚かせます。

多分それはCPUパワーによってではなく、メモリ帯域幅によって制限されますか？1つの128*128floatアレイは65kBを消費するため、6つのアレイすべてがCPUのL3キャッシュ（8 MB）に簡単に収まるはずです。レジスタに何もキャッシュされていないと仮定すると、内部ループ本体で15回のメモリアクセスをカウントします。64ビットシステムでは、これは反復ごとに120バイトであるため、5,700万*120バイト=6.8GB/秒です。L3キャッシュは2.66GHzで動作するため、同じ桁数です。私の推測では、記憶は確かにボトルネックです。

これをスピードアップするために、私は次のことを試みました：

• でコンパイルしg++ -O3ます。（まあ、私は最初からこれをやっていた。）

• OpenMPプラグマを使用した4コア以上の並列化。同じ配列からの読み取りと同じ配列への書き込みを回避するために、Jacobiアルゴリズムに変更する必要があります。これには、2倍の反復を行う必要があり、ほぼ同じ速度の最終結果が得られます。

• インデックスの代わりにポインタを使用するなど、ループ本体の実装の詳細をいじる。無効。

この男をスピードアップするための最良のアプローチは何ですか？アセンブリで内部ボディを書き直すのに役立ちますか（最初にそれを学ぶ必要があります）？代わりにこれをGPUで実行する必要があります（これは方法を知っていますが、とても面倒です）？他に明るいアイデアはありますか？

（NB私は答えに「いいえ」を取ります：「それは大幅に速くすることはできません、なぜなら...」）

更新：要求に応じて、完全なプログラムは次のとおりです。

私はそれを次のようにコンパイルして実行します：

（私の「実際の」プログラムは他の多くのことも行うので、毎秒3500回の反復ではなく8000回実行します。しかしそれは代表的なものです。）

アップデート2：NaNとInfの値が遅くなる可能性があるため、単一化された値は代表的ではない可能性があると言われました。次に、サンプルコードのメモリをクリアします。ただし、実行速度には違いはありません。