6

Xで を解決する必要があるこの問題がありAX=Bます。A15000 x 15000 のオーダーで、まばらで対称的です。B15000 X 7500 で、まばらではありません。X を解くための最速の方法は何ですか?

2通り考えられます。

  1. 可能な限り簡単な方法、X = A\B

  2. forループを使用して、

    invA = A\speye(size(A))
for i = 1:size(B,2)
    X(:,i) = invA*B(:,i);
end

上記の2つよりも良い方法はありますか？そうでない場合、私が言及した2つの中でどちらが最適ですか?

4

4 に答える 4

9

まず最初に - A の逆数を計算することは決してありません。A が対角行列の場合を除いて、決してスパースではありません。単純な三重対角行列で試してみてください。その行だけで、メモリとパフォーマンスの観点からコードが強制終了されます。また、逆数の計算は、他の方法よりも数値的に正確ではありません。

通常、\問題なく動作するはずです。MATLAB は行列が疎であることを認識し、疎分解を実行します。行列Bを右辺として与えると、1 つの連立方程式のみをbベクトルで解く場合よりもパフォーマンスが大幅に向上します。だからあなたはそれを正しくします。ここで試すことができる他の唯一の技術的なことは、持っている行列に応じて、 、またはを明示的に呼び出しlu、後方/前方置換を自分で実行することです。たぶん、そこで時間を節約できます。cholldl

実際には、連立方程式の線形システム、特にスパース システムを解く方法は、問題に大きく依存します。しかし、私が想像するほとんどすべての (まばらな) ケースでは、15k システムの因数分解はほんの一瞬しかかからないはずです。それは今日では大規模なシステムではありません。コードが遅い場合、これはおそらく因子がそれほどまばらではなくなったことを意味します。スパース分解中の塗りつぶし (ゼロ以外のエントリの追加) を最小限に抑えるために、行列が適切に並べ替えられていることを確認する必要があります。それが重要なステップです。システムを再注文する方法に関するいくつかのテストと説明については、このページをご覧ください。そして、この SO スレッドで並べ替えの例を簡単に見てください。

于 2012-10-11T08:18:04.793 に答える
3

2 つのうちどちらが速いかは自分で答えられるので、次のオプションを提案してみます。GPUを使って解いてください。このSO 投稿、A/b のmatlab ベンチマークなど、オンラインで多くの詳細を見つけることができます。さらに、 LAMG (Lean Algebraic Multigrid)の MATLAB アドオンもあります。LAMG は高速グラフ ラプラシアン ソルバーです。Ax=b を O(m) 時間とストレージで解くことができます。

于 2012-10-11T04:12:23.603 に答える
2

行列Aが対称正定である場合、システムを効率的かつ安定して解くためにできることは次のとおりです。

  • 最初に、コレスキー分解 を計算しA=L*L'ます。スパース行列があり、それを利用して反転を加速したいのでchol、スパース パターンを破壊する直接適用しないでください。代わりに、こちらで説明されている並べ替え方法のいずれかを使用してください。
  • 次に、システムを次のように解きますX = L'\(L\B)

最後に、潜在的な複素数を扱っていない場合は、すべてをL'byL.'に置き換えることができます。これにより、複素共役を計算する代わりに転置しようとしているため、さらに高速になります。

pcg別の代替手段は、Matlabの前処理付き共役勾配法です。これは、速度と正確さをトレードオフできるため、実際には非常に人気があります。つまり、反復回数を減らし、(通常はかなり良い) 近似解が得られます。また、行列を明示的に格納する必要はありませんが、行列がメモリに収まらない場合は、 で行列Aベクトル積を計算できます。A

于 2012-10-11T05:43:34.367 に答える
1

テストでこれを解決するのに永遠に時間がかかる場合は、おそらく解決のために仮想メモリを使用しています。15k平方（フル）マトリックスは、メモリに格納するために1.8ギガバイトのRAMを必要とします。

>> 15000^2*8
ans =
      1.8e+09

これを解決するには、本格的なRAMと、64ビットバージョンのMATLABが必要になります。問題を解決するのに十分なRAMがない限り、因数分解は役に立ちません。

行列が本当にスパースである場合、MATLABのスパース形式を使用して行列を格納していますか？そうでない場合、MATLABは行列がスパースであることを認識せず、スパース因数分解を使用しません。

Aはどのくらいまばらですか？多くの人は、ゼロで半分満たされた行列は「スパース」であると考えています。それは時間の無駄です。そのサイズの行列では、行列のスパース因数分解から真に得るには、99％をはるかに超えるゼロが必要です。これは記入によるものです。結果として得られる因数分解された行列は、それ以外の場合、ほとんどの場合ほぼ満杯です。

より多くのRAMを取得できない場合（RAMはご存知のとおりです。確かに、これを解決するために無駄に費やした時間を考慮すると）、反復ソルバーを試す必要があります。これらのツールはマトリックスを因数分解しないため、マトリックスが本当にスパースである場合、仮想メモリには入りません。これは大幅な節約です。

反復ツールは、可能な限り機能するために前処理行列を必要とすることが多いため、最適な前処理行列を見つけるには、ある程度の調査が必要になる場合があります。

于 2012-10-11T08:47:59.293 に答える