問題タブ [sparse-matrix]

R には少なくとも 2 つの疎行列パッケージがあります。密な表現でメモリに収まるには大きすぎて疎なデータセットを扱っているため、これらを調べています。基本的な線形代数ルーチンと、それらを操作する C コードを簡単に記述できる機能が必要です。最も成熟しており、使用するのに最適なライブラリはどれですか?

これまでに見つけた

• 多くの逆依存関係を持つマトリックスであり、最も使用されているものであることを意味します。
• 逆デプスが少ないSparseM。
• さまざまなグラフ ライブラリには、おそらくこれの独自の (暗黙的な) バージョンがあります。例えば​​igraphとnetwork (後者はstatnetの一部です)。これらは私のニーズに対して特殊すぎます。

誰でもこれを経験したことがありますか？

RSeek.orgを少し検索すると、 Matrixパッケージが最もよく言及されているようです。私はよくCRAN タスク ビューをかなり信頼できるものと考えており、多変量タスク ビューでは Matrix と SparseM について言及しています。

大きなスパース行列（たとえば、10k + x 1M +）が与えられた場合、密行列（すべてゼロ以外の要素）を形成する行と列のサブセット（必ずしも連続ではない）を見つける必要があります。このサブ行列は、アスペクト比の制約内で可能な限り大きくする必要があります（最大の合計ではなく、要素の最大数）。

この問題に対する既知の正確なまたはアプロキサメートの解決策はありますか？

グーグルでのクイックスキャンは、多くの近いが正確ではない結果を与えるようです。どのような用語を探す必要がありますか？

編集：明確にするために; サブ行列は連続である必要はありません。実際、行と列の順序は完全に任意であるため、隣接関係は完全に無関係です。

チャド・オケレの考えに基づく考え

1. 行を最大数から最小数の順に並べます（必須ではありませんが、パフォーマンスに役立つ場合があります）
2. 「大きな」オーバーラップがある2つの行を選択します
3. 重複を減らさない他のすべての行を追加します
4. そのセットを記録する
5. オーバーラップを最小限に抑える行を追加します
6. 結果が小さくなるまで＃3で繰り返します
7. 別の開始ペアで＃2からやり直します
8. 結果が十分に良いと判断するまで続けます

私は、4 次元データ、つまり 3D 空間内の位置にあるいくつか (3 ～ 30) の変数を使用する心臓シミュレーション ツールに取り組んでいます。

現在、シミュレートする組織の外側にある 3D ボックス内のポイントの 2/3 以上を残す組織ジオメトリを追加しているため、他のポイントではなくアクティブなポイントを効率的に保存する方法が必要です。

重要なのは、次のことができる必要があることです。

• 制約された 3D ボックス内のすべてのアクティブ ポイントを反復処理します (イテレータ、おそらく?)
• 1 つの点にアクセスしたら、その直交する近傍 (x、y、z) +/- 1 を見つけます。

それはおそらく複数の質問です！私の主な関心事は、まばらなデータを効率的に表現する方法です。

私はCを使用しています。

Rでスパース行列を操作するためのオプションについて学習した後、 Matrixパッケージを使用して、次のデータフレームからスパース行列を作成し、他のすべての要素をにしたいと思いますNA。

通常どおり要素にアクセスして、次のスパース行列を作成できることを知っています。

しかし、デフォルト値をNAにしたい場合は、次のことを試しました。

このエラーが発生しました

それだけでなく、要素にアクセスするのにはるかに長い時間がかかることがわかりました。

このマトリックスをどのように作成する必要がありますか？1つのマトリックスの操作が非常に遅いのはなぜですか？

上記のデータのコードスニペットは次のとおりです。

経験豊富なプログラマーが何らかの洞察を持っていることを願っています。私はブースト ublas 疎行列、具体的には mapping_matrix を使用していますが、最終的に発生する断続的なバグがありますが、プログラムの初期段階では発生しません。これは大きなプログラムなので、すべてのコードを掲載することはできませんが、核となるアイデアは、特定のクラスに属する関数を呼び出すことです。

変数 c は、クラスのメンバーとして定義されています

バグが発生すると、プログラムが停止したように見えます (クラッシュはしません)。Eclipse でデバッグすると、プログラムが boost maps_matrix コードに入り、std::map、std::_Rb_tree、std::less までいくつかのレベルに続くことがわかります。また、プログラムは時々 std::map、std::_Rb_tree、および std::_Select1st までトレースします。コードが実行されていて、_Rb_tree でメモリ内のアクティブな行が変更されている間、実行は std::map のレベルに戻ることはないようです。プログラムがスタックしている std::map の行は、次の関数の戻り値です。

プログラムが探している要素がcマトリックスにあるように思えますが、どういうわけか、基礎となるストレージメカニズムが「それを置き忘れた」のです。ただし、なぜそれを修正するのか、またはどのように修正するのかはわかりません。それはまた、完全にベースから外れている可能性があります。

あなたが提供できるどんな助けも大歓迎です。この質問に正しい情報が含まれていない場合は、何が欠けているか教えてください。ありがとうございました。

次の疎行列 A があります。

次に、そこから次の情報を取得したいと思います。

1. 行列が列方向にスキャンされるときのエントリの累積数。収量：

   Ap = [0, 2, 5, 9, 10, 12];

2. 行列が列方向にスキャンされるため、エントリの行インデックス。収量：

   Ai = [0, 1, 0, 2, 4, 1, 2, 3, 4, 2, 1, 4];

3. 行列が列方向にスキャンされるため、非ゼロの行列エントリ。収量：

   斧 = [2, 3, 3, -1, 4, 4, -3, 1, 2, 2, 6, 1];

実際の行列 A は非常に大きくなる可能性があるため、Perl でこれらの要素をキャプチャできる効率的な方法はありますか? 特に、すべての行列 A を RAM に丸呑みすることなく。

次のコードで立ち往生しています。それは私が望むものを与えません。

ブール値を保持するブースト スパース マトリックスを使用し、それらをマップに格納するための比較関数を作成しようとしています。とてもシンプルな比較機能です。基本的には、マトリックスを 2 進数 (ベクトルにフラット化した後) として見て、その数値の値に基づいて並べ替えるという考え方です。これは次の方法で実現できます。

ただし、これはマトリックスがまばらであるため非効率的であり、同じ結果を得るために反復子を使用したいと考えています。イテレータを使用するアルゴリズムは単純に見えます。つまり、1) 各行列の最初の非ゼロ セルを取得し、2) 両方の j*maxJ+i を比較し、3) 等しい場合は、各行列の次の非ゼロ セルを取得して繰り返します。残念ながら、コードではこれは非常に面倒で、エラーが心配です。

私が疑問に思っているのは、(a)これを行うためのより良い方法はありますか?(b)両方の行列の「次のゼロ以外のセル」を取得する簡単な方法はありますか? 明らかに、1 つの疎行列を反復処理する場合のように、ネストされた for ループを使用することはできません。

ご協力いただきありがとうございます。

--

上記で提案したアルゴリズムが私の特定のアプリケーションで最適なソリューションであると思われるので、2 つのスパース行列で次の非ゼロ セルを取得する、トリッキーな部分のために開発したコードを投稿する必要があると考えました。このコードは理想的ではなく、あまり明確ではありませんが、改善方法がわかりません。誰かがバグを見つけた場合、またはそれを改善する方法を知っている場合は、コメントをいただければ幸いです。そうでなければ、これが他の誰かに役立つことを願っています。

次のように、C++で「スパース」ベクトルクラスを作成しようとしています。

内部的には、std::map<int, V>（V格納されている値のタイプは）で表されます。要素がマップに存在しない場合はDefault、テンプレート引数の値と等しいと見なします。

ただし、添え字演算子のオーバーロードに問題があります[]。このクラスのオブジェクトを、正しく[]機能することを期待するBoost関数に渡すため、演算子をオーバーロードする必要があります。[]

constバージョンは非常に単純です。インデックスがマップにあるかどうかを確認し、ある場合はその値を返すか、そうでない場合はその値を返しますDefault。

ただし、非constバージョンでは参照を返す必要があり、そこで問題が発生します。値が読み取られているだけの場合は、マップに何も追加する必要はありません（または追加したくありません）。しかし、それが書かれている場合、私はおそらくマップに新しいエントリを入れる必要があります。問題は、オーバーロードされた値が値の読み取りまたは[]書き込みのどちらであるかを認識しないことです。単に参照を返すだけです。

この問題を解決する方法はありますか？またはおそらくそれを回避するために？

Goldenthal らの非拡張クロス アルゴリズムの C# での実験的実装に取り​​組んでいます。

まず、Math.NET Iridium を使用して行列を組み立てて解決しましたが、すぐにこれを dnAnalytics に置き換えました。これは、dnAnalytics を使用すると行列を再利用できるため、リアルタイム パフォーマンス (小さな布) または反復的な解決にとって重要な追加のメモリ割り当てがほとんど不要になるからです。一般に。

問題は、dnAnalytics のソルバー (主に関心のあるのは LU と Bi-CG) が、過去の割り当てを再利用する代わりに、舞台裏で行列とベクトルを割り当てていることです。

=> すぐに使えるメモリを再利用するスパース線形代数ライブラリはありますか? それとも自分でコードを書き直す必要がありますか?

私はコンウェイのライフ ゲームをいじっており、最近、Hashlife や Golly などの驚くほど高速な実装を発見しました。(Golly のダウンロードはこちら - http://golly.sourceforge.net/ )

私が理解できないことの 1 つは、コーダーが無限グリッドをどのように実装するのかということです。何の無限の配列を保持することはできません. ゴリゴリと走って数機のグライダーが端を通り過ぎて飛び立ち、数分待ってすぐにズームアウトすると、グライダーがまだ宇宙に逃げているのが見えます.それでは、神の名において、この無限の概念はプログラムでどのように処理されるのでしょうか? よく文書化されたパターンはありますか？

どうもありがとう