11

Eigen バージョンでは、「真の」固定サイズの行列とベクトル、より優れたアルゴリズム (uBlas での LDLT と LU) を使用し、内部で SIMD 命令を使用します。では、次の例で uBlas よりも遅いのはなぜですか?

私は何か間違ったことをしていると確信しています.Eigenはより高速であるか、少なくとも同等である必要があります.

#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/lu.hpp>
#include <boost/numeric/ublas/symmetric.hpp>
#include <boost/progress.hpp>
#include <Eigen/Dense>
#include <iostream>

using namespace boost;
using namespace std;
const int n=9;
const int total=100000;

void test_ublas()
{
    using namespace boost::numeric::ublas;
    cout << "Boost.ublas ";
    double r=1.0;
    {
        boost::progress_timer t;
        for(int j=0;j!=total;++j)
        {
            //symmetric_matrix< double,lower,row_major,bounded_array<double,(1+n)*n/2> > A(n,n);
            matrix<double,row_major,bounded_array<double,n*n> > A(n,n);
            permutation_matrix< unsigned char,bounded_array<unsigned char,n> > P(n);
            bounded_vector<double,n> v;
            for(int i=0;i!=n;++i)
                for(int k=0;k!=n;++k)
                    A(i,k)=0.0;
            for(int i=0;i!=n;++i)
            {
                A(i,i)=1.0+i;
                v[i]=i;
            }
            lu_factorize(A,P);
            lu_substitute(A,P,v);
            r+=inner_prod(v,v);
        }
    }
    cout << r << endl;
}

void test_eigen()
{
    using namespace Eigen;
    cout << "Eigen ";
    double r=1.0;
    {
        boost::progress_timer t;
        for(int j=0;j!=total;++j)
        {
            Matrix<double,n,n> A;
            Matrix<double,n,1> b;
            for(int i=0;i!=n;++i)
            {
                A(i,i)=1.0+i;
                b[i]=i;
            }
            Matrix<double,n,1> x=A.ldlt().solve(b);
            r+=x.dot(x);
        }
    }
    cout << r << endl;
}

int main()
{
    test_ublas();
    test_eigen();
}

出力は次のとおりです。

Boost.ublas 0.50 s

488184
Eigen 2.66 s

488184

(Visual Studio 2010 x64 リリース)

編集：

為に

const int n=4;
const int total=1000000;

出力は次のとおりです。

Boost.ublas 0.67 s

1.25695e+006
Eigen 0.40 s

5.4e+007

このような動作は、uBlas バージョンがその場で因数分解を計算するのに対し、Eigen バージョンは行列の COPY (LDLT) を作成するためだと思います。そのため、キャッシュにうまく適合しません。

Eigenでインプレース計算を行う方法はありますか? それとも、それを改善する他の方法がありますか？

編集：

Fezvez のアドバイスに従って、LDLT の代わりに LLT を使用すると、次のようになります。

Eigen 0.16 s

488184

それは良いことですが、それでも不必要な行列スタック割り当てを行います:

sizeof(A.llt()) == 656

私はそれを避けることを好みます-それはさらに速くなるはずです。

編集：

LDLT (内部マトリックスは保護されています) からサブクラス化し、直接入力することにより、割り当てを削除しました。LDLT の結果は次のようになります。

Eigen 0.26 s
488209

それは機能しますが、回避策です-実際の解決策ではありません...

LLT からのサブクラス化も機能しますが、それほど大きな効果はありません。

4

2 に答える 2

8

ublas バージョンはその場で解決するため、ベンチマークは公平ではありませんが、Eigen バージョンはそうするように簡単に調整できます。

b=A.ldlt().solve(b);
r+=b.dot(b);

g++-4.6 -O2 -DNDEBUG でコンパイルすると、(2.3GHz CPU で) 次のようになります。

Boost.ublas 0.15 s
488184

Eigen 0.08 s
488184

また、最適化を有効にしてコンパイルし、32 ビット システムまたは (32 ビット コンパイル チェーン) を実行している場合は SSE2 を有効にしてコンパイルしたことを確認してください。

編集:マトリックスのコピーも回避しようとしましたが、これによりゲインがまったくなくなりました。

また、n を大きくすると、速度差が大きくなります (ここでは n=90):

Boost.ublas 0.47 s
Eigen 0.13 s
于 2012-11-15T07:46:19.307 に答える
2

インプレース計算に関するヒントに従いました。

まったく同じコードを使用し、関数A.llt().solveInPlace(b);and A.ldlt().solveInPlace(b);(b を x に置き換えます) を使用すると、それが得られました。

There were  100000  Eigen standard LDLT linear solvers applied in  12.658  seconds 
There were  100000  Eigen standard LLT linear solvers applied in  4.652  seconds 

There were  100000  Eigen in place LDLT linear solvers applied in  12.7  seconds 
There were  100000  Eigen in place LLT linear solvers applied in  4.396  seconds

この種の問題には、LDLT ソルバーよりも LLT ソルバーの方が適しているのではないでしょうか? (サイズ 9 の行列を扱っていることがわかります)

(ちなみに、次元 9 の線形ソルバーに関する以前の質問に少し答えましたが、Eigen の LDLT の実装には多くのオーバーヘッドがあることを知り、非常に残念です...)

于 2012-11-14T13:13:41.760 に答える