Эффективное блочно-разреженное умножение матрицы с Eigen

Question

Предположим, что у меня есть разреженная матрица, за исключением блоков по диагонали (фиксированного размера).

Eigen::SparseMatrix<float> lhs;

LHS составляет около 2%, не редки, но может быть очень большим. Тогда, скажем, у меня есть вектор:

Eigen::MatrixXf rhs = Eigen::MatrixXf::Random(SomeSz, 1);

На данный момент, давайте предположим, что это плотная.

Я хочу, чтобы эффективно вычислить:

result.noalias() = lhs * rhs;

Если бы я был компилировать с -O3 -march = родной -mtune = родной (с Clang), будет это производить оптимальный результат?

Кроме того, что, если ки были разреженными:

Eigen::SparseMatrix<float> rhs; rhs.resize(SomeSz, 1); rhs.reserve(SomeSz/SomeFactor);

Is:

result = lhs * rhs;

еще оптимально/неоптимальным?

Я предполагаю, что я спрашиваю, будет ли Эйген использовать блок-разреженную структуру и выполнять только необходимые вычисления.

Answer 1

Прежде всего, в плотном случае для rhs, если rhs - вектор, то, пожалуйста, сообщите об этом Eigen, используя VectorXf. Затем, с Eigen 3.3, вы можете использовать многопоточность, скомпилировав ее с помощью -fopenmp и используя основное хранилище lhs.

В редком случае да Eigen будет учитывать разреженность как lhs, так и rhs. Сложность будет действительно rhs.nonZeros()*average_nnz_per_col_of_lhs, в отличие от rhs.size()*average_nnz_per_col_of_lhs с плотным rhs. Так что если rhs действительно разрежен, то, возможно, стоит попробовать. Будет рассмотрен только полезный столбец lhs. В этом случае лучше сохранить основную колонку lhs.