問題タブ [sparse-matrix]

五角行列を解く最善の方法を見つけようとしています。ガウス消去法より速いものはありますか?

テンプレート化されたsparse_vectorクラスを実装しています。これはベクトルのようなものですが、デフォルトの構築値とは異なる要素のみを格納します。

したがって、sparse_vectorは、値がT（）ではないすべてのインデックスの遅延ソートされたインデックスと値のペアを格納します。

私は、数値ライブラリ内の既存のスパースベクトルに基づいて実装を行っていますが、非数値型Tも処理します。見てみましboost::numeric::ublas::coordinate_vectorたeigen::SparseVector。

両方のストア：

単純に使ってみませんか

私の主な質問は、両方のシステムの長所と短所は何ですか、そしてどちらが最終的に優れているかです。

ペアのベクトルは、size_とcapacity_を管理し、付随するイテレータクラスを単純化します。また、2つではなく1つのメモリブロックがあるため、再割り当ての半分が発生し、参照の局所性が向上する可能性があります。

他のソリューションでは、検索中にキャッシュラインがインデックスデータのみでいっぱいになるため、検索が速くなる可能性があります。Tが8バイトタイプの場合、アライメントの利点もいくつかありますか？

ペアのベクトルがより良い解決策であるように私には思えますが、両方のコンテナーがもう一方の解決策を選択しました。なんで？

まず第一に、私はJavaの初心者なので、これが可能かどうかさえわかりません! 基本的に、私はリレーショナルデータの巨大な（300万以上）データソースを持っています（つまり、AはB + C + Dと友達であり、BはD + G + Zと友達です（ただし、Aではありません-つまり、相互的ではありません）など）。この (必ずしも接続されていない) 有向グラフ内のすべてのサイクルを検索します。

Finding all cycles in graphというスレッドを見つけました。これは、少なくとも表面的には、私が求めていることを実行するように見える、Donald Johnson の (基本的な) サイクル検出アルゴリズムを示しています (試してみます火曜日に仕事に戻ったら、その間に聞いても問題ないと思います!)。

Johnson のアルゴリズムの Java 実装のコード (そのスレッド) をざっとスキャンしたところ、関係のマトリックスが最初のステップのように見えたので、私の質問は次のとおりだと思います。

a) Java は 3+million*3+million 行列を処理できますか? (A-friends-with-B を 2 値疎行列で表すことを計画していました)

b) 最初の問題として、すべての接続されたサブグラフを見つける必要がありますか?それとも、循環探索アルゴリズムが互いに素なデータを処理しますか?

c) これは実際に問題の適切な解決策ですか? 「基本」サイクルについての私の理解では、下のグラフでは、ABCDEF を選択するのではなく、ABF、BCD などを選択しますが、タスクを考えると、それは世界の終わりではありません。

d) 必要に応じて、関係の相互性を強制することで問題を単純化できます。つまり、A-friends-with-B <==> B-friends-with-A です。本当に必要な場合は、データ サイズを削減することもできますが、現実的には、常に 1mil マーク前後になります。

z) これは P タスクですか、それとも NP タスクですか?! 私は噛むことができる以上に噛んでいますか？

ありがとうございました。アンディ

この素晴らしい SO の回答は、 の優れたスパース ソルバーを示しAx=bていますが、 のx各要素xが.>=0<=N

また、巨大（約2e6x2e6）ですが、行ごとの要素が非常にまばらAです。<=4

アイデア/推奨事項はありますか？MATLAB のようなものを探していますlsqlinが、巨大なスパース マトリックスがあります。

私は基本的に、スパース行列で大規模な有界変数最小二乗問題を解決しようとしています:

編集： CVXで：

非常に大きな解像度で画像を作成する必要がありますが、画像は比較的「まばら」で、画像の一部の領域のみを描画する必要があります。

たとえば、次のコードで

最後に作成した PNG 画像は 200 ～ 300 MB 程度しかありません。

問題は、最初に 5GB の BufferedImage を作成しないようにするにはどうすればよいですか? 大きな寸法の画像が必要ですが、色情報が非常にまばらです。

そんなに多くのメモリを消費しないように、BufferedImage のストリームはありますか?

非常に大きな行列で k-means クラスタリングを実行しようとしています。

マトリックスは約 500000 行 x 4000 列ですが、非常にまばらです (行ごとに "1" の値が 2 つだけ)。

全体がメモリに収まらないので、スパース ARFF ファイルに変換しました。しかし、R は明らかにスパース ARFF ファイル形式を読み取ることができません。また、データをプレーンな CSV ファイルとして持っています。

このようなスパース行列を効率的にロードするために R で利用できるパッケージはありますか? 次に、クラスター パッケージの通常の k-means アルゴリズムを使用して続行します。

どうもありがとう

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

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

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

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

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

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

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

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

3D長方形空間を表すスパース行列があります。いくつかの境界に沿って、値がどうなるかを知っています（定数です）。他の境界は、反射、差動などである可能性があります。

すべての境界が微分であるかのように問題を設定してから、戻って解ベクトルbのノードを定数に設定する必要がありますか？

ありがとう！

よくある問題だと思いますが、何と呼ばれる工程か分からないので、例を挙げて説明します。コンセプトは、まばらなデータセットを完全なシリーズ (曜日、月、順序付きセット (ランキングなど) など) に結合したいというものです。スパース データの空の位置は、完全なシリーズの横に NULL として表示されます。

SQL Server で次のクエリを実行して、毎月の売り上げを調べたとします。

ただし、たとえば、売上が今年の 5 月と 8 月にのみ発生した場合、返される結果は次のようになります。

返される結果セットを次のようにします。

これを行う唯一の方法は次のとおりです。

データを結合する完全な日付と英数字のシリーズを作成するより良い方法はありますか? そして、これは何と呼ばれていますか？

ありがとう！