17

我希望标题中问题的答案是我在做一些愚蠢的事情!

这是问题所在。我想计算一个实数对称矩阵的所有特征值和特征向量。我已经使用GNU Scientific Library在 MATLAB(实际上,我使用 Octave 运行它)和 C++ 中实现了代码。我在下面为这两种实现提供了我的完整代码。

据我所知,GSL 附带了它自己的 BLAS API 实现(以下我将其称为 GSLCBLAS)并使用我编译的这个库:

g++ -O3 -lgsl -lgslcblas

GSL在此建议使用替代 BLAS 库,例如自优化ATLAS库,以提高性能。我正在运行 Ubuntu 12.04,并且已经从Ubuntu 存储库安装了 ATLAS 软件包。在这种情况下,我编译使用:

g++ -O3 -lgsl -lcblas -latlas -lm

对于这三种情况,我以 100 的步长对大小为 100 到 1000 的随机生成的矩阵进行了实验。对于每个大小,我使用不同的矩阵执行 10 次特征分解,并平均花费的时间。结果如下:

结果图

性能上的差异是荒谬的。对于大小为 1000 的矩阵,Octave 在不到一秒的时间内执行分解;GSLCBLAS 和 ATLAS 大约需要 25 秒。

我怀疑我可能错误地使用了 ATLAS 库。欢迎任何解释;提前致谢。

关于代码的一些注释:

  • 在 C++ 实现中,不需要使矩阵对称,因为该函数只使用它的下三角部分

  • 在 Octave 中,线triu(A) + triu(A, 1)'强制矩阵是对称的。

  • 如果你想在你自己的 Linux 机器上编译 C++ 代码,你还需要添加 flag -lrt,因为这个clock_gettime函数。

  • 不幸的是,我认为不会clock_gettime在其他平台上退出。考虑将其更改为gettimeofday.

八度码

K = 10;

fileID = fopen('octave_out.txt','w');

for N = 100:100:1000
    AverageTime = 0.0;

    for k = 1:K
        A = randn(N, N);
        A = triu(A) + triu(A, 1)';
        tic;
        eig(A);
        AverageTime = AverageTime + toc/K;
    end

    disp([num2str(N), " ", num2str(AverageTime), "\n"]);
    fprintf(fileID, '%d %f\n', N, AverageTime);
end

fclose(fileID);

C++ 代码

#include <iostream>
#include <fstream>
#include <time.h>

#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#include <gsl/gsl_eigen.h>
#include <gsl/gsl_vector.h>
#include <gsl/gsl_matrix.h>

int main()
{
    const int K = 10;

    gsl_rng * RandomNumberGenerator = gsl_rng_alloc(gsl_rng_default);
    gsl_rng_set(RandomNumberGenerator, 0);

    std::ofstream OutputFile("atlas.txt", std::ios::trunc);

    for (int N = 100; N <= 1000; N += 100)
    {
        gsl_matrix* A = gsl_matrix_alloc(N, N);
        gsl_eigen_symmv_workspace* EigendecompositionWorkspace = gsl_eigen_symmv_alloc(N);
        gsl_vector* Eigenvalues = gsl_vector_alloc(N);
        gsl_matrix* Eigenvectors = gsl_matrix_alloc(N, N);

        double AverageTime = 0.0;
        for (int k = 0; k < K; k++)
        {   
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    gsl_matrix_set(A, i, j, gsl_ran_gaussian(RandomNumberGenerator, 1.0));
                }
            }

            timespec start, end;
            clock_gettime(CLOCK_MONOTONIC_RAW, &start);

            gsl_eigen_symmv(A, Eigenvalues, Eigenvectors, EigendecompositionWorkspace);

            clock_gettime(CLOCK_MONOTONIC_RAW, &end);
            double TimeElapsed = (double) ((1e9*end.tv_sec + end.tv_nsec) - (1e9*start.tv_sec + start.tv_nsec))/1.0e9;
            AverageTime += TimeElapsed/K;
            std::cout << "N = " << N << ", k = " << k << ", Time = " << TimeElapsed << std::endl;
        }
        OutputFile << N << " " << AverageTime << std::endl;

        gsl_matrix_free(A);
        gsl_eigen_symmv_free(EigendecompositionWorkspace);
        gsl_vector_free(Eigenvalues);
        gsl_matrix_free(Eigenvectors);
    }

    return 0;
}
4

3 回答 3

6

我不同意之前的帖子。这不是线程问题,这是算法问题。matlab、R 和 octave 使用 C++ 库的原因是因为它们的 C++ 库使用更复杂、更好的算法。如果您阅读 octave 页面,您可以了解它们的作用[1]:

特征值是在几个步骤中计算的,首先是 Hessenberg 分解,然后是 Schur 分解,从中可以看出特征值。需要时,通过进一步操作 Schur 分解来计算特征向量。

解决特征值/特征向量问题并非易事。事实上,它是“C 中的数字食谱”建议您不要自己实现的少数几件事之一。(第 461 页)。GSL 通常很慢,这是我最初的反应。ALGLIB 的标准实现也很慢(我大约需要 12 秒!):

#include <iostream>
#include <iomanip>
#include <ctime>

#include <linalg.h>

using std::cout;
using std::setw;
using std::endl;

const int VERBOSE = false;

int main(int argc, char** argv)
{

    int size = 0;
    if(argc != 2) {
        cout << "Please provide a size of input" << endl;
        return -1;
    } else {
        size = atoi(argv[1]);
        cout << "Array Size: " << size << endl;
    }

    alglib::real_2d_array mat;
    alglib::hqrndstate state;
    alglib::hqrndrandomize(state);
    mat.setlength(size, size);
    for(int rr = 0 ; rr < mat.rows(); rr++) {
        for(int cc = 0 ; cc < mat.cols(); cc++) {
            mat[rr][cc] = mat[cc][rr] = alglib::hqrndnormal(state);
        }
    }

    if(VERBOSE) {
        cout << "Matrix: " << endl;
        for(int rr = 0 ; rr < mat.rows(); rr++) {
            for(int cc = 0 ; cc < mat.cols(); cc++) {
                cout << setw(10) << mat[rr][cc];
            }
            cout << endl;
        }
        cout << endl;
    }

    alglib::real_1d_array d;
    alglib::real_2d_array z;
    auto t = clock();
    alglib::smatrixevd(mat, mat.rows(), 1, 0, d, z);
    t = clock() - t;

    cout << (double)t/CLOCKS_PER_SEC << "s" << endl;

    if(VERBOSE) {
        for(int cc = 0 ; cc < mat.cols(); cc++) {
            cout << "lambda: " << d[cc] << endl;
            cout << "V: ";
            for(int rr = 0 ; rr < mat.rows(); rr++) {
                cout << setw(10) << z[rr][cc];
            }
            cout << endl;
        }
    }
}

如果你真的需要一个快速的图书馆,可能需要做一些真正的狩猎。

[1] http://www.gnu.org/software/octave/doc/interpreter/Basic-Matrix-Functions.html

于 2013-12-06T22:03:07.720 回答
3

我也遇到过这个问题。真正的原因是matlab中的eig()没有计算特征向量,但是上面的C版本代码可以。如下图所示,所用时间的差异可能大于一个数量级。所以比较是不公平的。

在 Matlab 中,根据返回值,实际调用的函数会有所不同。要强制计算特征向量,应使用[V,D] = eig(A)(参见下面的代码)。

计算特征值问题的实际时间很大程度上取决于矩阵属性和期望的结果,例如

  • 真实的或复杂的
  • Hermitian/对称与否
  • 密集或稀疏
  • 仅特征值、特征向量、仅最大特征值等
  • 串行或并行

有针对上述每种情况优化的算法。在 gsl 中,这些算法是手动选择的,因此错误的选择会显着降低性能。一些C++封装类或者matlab、mathematica等语言会通过一些方法选择优化后的版本。

此外,Matlab 和 Mathematica 使用了并行化。这些进一步扩大了您看到的差距几次,具体取决于机器。按理说,一般复数 1000x1000 的特征值和特征向量的计算大约是 1 秒和 10 秒,没有并行化。

比较 Matlab 和 C 图 比较 Matlab 和 C。“+ vec”表示代码包括特征向量的计算。CPU% 是在 N=1000 时对 CPU 使用率的粗略观察,上限为 800%,尽管它们应该完全使用所有 8 个内核。Matlab 和 C 之间的差距小于 8 倍。

比较 Mathematica 中的不同矩阵类型 图 比较 Mathematica 中不同的矩阵类型。程序自动选择的算法。

Matlab(带有特征向量的计算)

K = 10;

fileID = fopen('octave_out.txt','w');

for N = 100:100:1000
    AverageTime = 0.0;

    for k = 1:K
        A = randn(N, N);
        A = triu(A) + triu(A, 1)';
        tic;
        [V,D] = eig(A);
        AverageTime = AverageTime + toc/K;
    end

    disp([num2str(N), ' ', num2str(AverageTime), '\n']);
    fprintf(fileID, '%d %f\n', N, AverageTime);
end

fclose(fileID);

C++(不计算特征向量)

#include <iostream>
#include <fstream>
#include <time.h>

#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#include <gsl/gsl_eigen.h>
#include <gsl/gsl_vector.h>
#include <gsl/gsl_matrix.h>

int main()
{
    const int K = 10;

    gsl_rng * RandomNumberGenerator = gsl_rng_alloc(gsl_rng_default);
    gsl_rng_set(RandomNumberGenerator, 0);

    std::ofstream OutputFile("atlas.txt", std::ios::trunc);

    for (int N = 100; N <= 1000; N += 100)
    {
        gsl_matrix* A = gsl_matrix_alloc(N, N);
        gsl_eigen_symm_workspace* EigendecompositionWorkspace = gsl_eigen_symm_alloc(N);
        gsl_vector* Eigenvalues = gsl_vector_alloc(N);

        double AverageTime = 0.0;
        for (int k = 0; k < K; k++)
        {   
            for (int i = 0; i < N; i++)
            {
                for (int j = i; j < N; j++)
                {
                    double rn = gsl_ran_gaussian(RandomNumberGenerator, 1.0);
                    gsl_matrix_set(A, i, j, rn);
                    gsl_matrix_set(A, j, i, rn);
                }
            }

            timespec start, end;
            clock_gettime(CLOCK_MONOTONIC_RAW, &start);

            gsl_eigen_symm(A, Eigenvalues, EigendecompositionWorkspace);

            clock_gettime(CLOCK_MONOTONIC_RAW, &end);
            double TimeElapsed = (double) ((1e9*end.tv_sec + end.tv_nsec) - (1e9*start.tv_sec + start.tv_nsec))/1.0e9;
            AverageTime += TimeElapsed/K;
            std::cout << "N = " << N << ", k = " << k << ", Time = " << TimeElapsed << std::endl;
        }
        OutputFile << N << " " << AverageTime << std::endl;

        gsl_matrix_free(A);
        gsl_eigen_symm_free(EigendecompositionWorkspace);
        gsl_vector_free(Eigenvalues);
    }

    return 0;
}

数学

(* Symmetric real matrix + eigenvectors *)
Table[{NN, Mean[Table[(
     M = Table[Random[], {i, NN}, {j, NN}];
     M = M + Transpose[Conjugate[M]];
     AbsoluteTiming[Eigensystem[M]][[1]]
     ), {K, 10}]]
  }, {NN, Range[100, 1000, 100]}]

(* Symmetric real matrix *)
Table[{NN, Mean[Table[(
     M = Table[Random[], {i, NN}, {j, NN}];
     M = M + Transpose[Conjugate[M]];
     AbsoluteTiming[Eigenvalues[M]][[1]]
     ), {K, 10}]]
  }, {NN, Range[100, 1000, 100]}]

(* Asymmetric real matrix *)
Table[{NN, Mean[Table[(
     M = Table[Random[], {i, NN}, {j, NN}];
     AbsoluteTiming[Eigenvalues[M]][[1]]
     ), {K, 10}]]
  }, {NN, Range[100, 1000, 100]}]

(* Hermitian matrix *)
Table[{NN, Mean[Table[(
     M = Table[Random[] + I Random[], {i, NN}, {j, NN}];
     M = M + Transpose[Conjugate[M]];
     AbsoluteTiming[Eigenvalues[M]][[1]]
     ), {K, 10}]]
  }, {NN, Range[100, 1000, 100]}]

(* Random complex matrix *)
Table[{NN, Mean[Table[(
     M = Table[Random[] + I Random[], {i, NN}, {j, NN}];
     AbsoluteTiming[Eigenvalues[M]][[1]]
     ), {K, 10}]]
  }, {NN, Range[100, 1000, 100]}]
于 2014-07-19T17:54:44.200 回答
1

在 C++ 实现中,不需要使矩阵对称,因为该函数只使用它的下三角部分。

情况可能并非如此。在参考文献中指出:

int gsl_eigen_symmv(gsl_matrix *A,gsl_vector *eval,gsl_matrix *evec,gsl_eigen_symmv_workspace * w)

此函数计算实对称矩阵 A的特征值和特征向量。必须在 w 中提供适当大小的额外工作空间。A的对角线和下三角部分在计算过程中被破坏,但严格的上三角部分没有被引用。特征值存储在向量 eval 中并且是无序的。对应的特征向量存储在矩阵 evec 的列中。例如,第一列的特征向量对应于第一个特征值。保证特征向量相互正交并归一化为单位幅度。

似乎您还需要在 C++ 中应用类似的对称化操作才能获得至少正确的结果,尽管您可以获得相同的性能。

在 MATLAB 方面,由于其多线程执行,特征值分解可能会更快,如本参考中所述:

内置多线程

线性代数和数值函数,如 fft、\ (mldivide)、eig、svd 和 sort 在 MATLAB 中是多线程的。自 2008a 版以来,MATLAB 中默认启用多线程计算。这些函数在单个 MATLAB 会话中的多个计算线程上自动执行,从而使它们能够在支持多核的机器上更快地执行。此外,Image Processing Toolbox™ 中的许多功能都是多线程的。

为了测试 MATLAB 单核的性能,您可以通过以下方式禁用多线程

文件>首选项>常规>多线程

在 R2007a 或更新版本中,如此所述。

于 2013-08-02T05:52:16.543 回答