SelfAdjointEigenSolver C ++ Eigen не быстрее с нулями в матрице - PullRequest
Новая
       111

SelfAdjointEigenSolver C ++ Eigen не быстрее с нулями в матрице

1 голос
/ 10 июля 2020

Большинство решателей собственных векторов фокусируются на диагонализации матрицы с помощью вращений (например, Гивенса или вращений Якоби), поэтому я бы предположил, что если бы уже было много нулей в входная матрица, которую решатель будет быстрее (т.е. чем больше нулей от диагонали, тем ближе матрица к диагонали). Это не похоже на C ++ Eigen's SelfAdjointEigenSolver.

Ниже приведена тестовая программа, в которой я генерирую случайную матрицу 632 x 632 A (только нижний треугольник angular часть матрицы обрабатывается, так как предполагается, что матрица является симметричной c). Сначала я обнуляю некоторый процент матрицы, а затем время 100 обращений к eigenSolver.compute(A). Количество нулей не влияет, пока A не станет чисто диагональной матрицей. 

#include <iostream>
#include <chrono>
#include <random>
#include <Eigen/Dense>

int main() {
    constexpr int N = 632;
    Eigen::MatrixXf A = Eigen::MatrixXf::Random(N,N);

    constexpr float zeroRate = 0.75;
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(0.0,1.0);
    for (int i = 0; i < N; i++) 
        for (int j = i+1; j < N; j++) {
            double number = distribution(generator);
            if (number <= zeroRate)
                A(i,j) = A(j,i) = 0;
        }

    Eigen::SelfAdjointEigenSolver<Eigen::MatrixXf> eigenSolver(N);
    
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100; i++)
        eigenSolver.compute(A); // only lower triangle processed
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
    std::cout << "eigenSolver.compute() runtime: " << duration << " milliseconds" << std::endl;

    return 0;
}

Время работы (3,2 ГГц Intel Core i5, g++ -Wall -O3 -std=c++11): 

zero rate    time
---------   -------
   0.00      11986 ms
   0.50      11946 ms
   0.75      11526 ms
   0.90      11886 ms
   0.95      11901 ms
   1.00       3438 ms

Может ли кто-нибудь объяснить мне, почему я не получаю более быстрое время выполнения для большего количества нулей?

...