Какой самый быстрый способ представления и умножения разреженных логических матриц?

Question

Итак, я использую булевы матрицы, размер которых обычно составляет от пары дюжин до пары сотен, они обычно довольно разрежены (всего 2-4 ненулевых элемента в большинстве строк и столбцов), и в моей среде выполнения преобладаютих умножение.

Какая структура данных лучше всего подходит для ускорения умножения в этих обстоятельствах?

В настоящее время я храню каждую матрицу в последовательном наборе битов (массив из 64-битных длин) построчно,и умножение их в основном по стандартному алгоритму, просто ускорилось из-за быстрой операции по нахождению следующего установленного бита в слове и векторизации с помощью операций битовой маски.

Должен ли я действительно использовать какое-то разреженное представление?

Answer 1

Вы можете рассмотреть возможность использования представления дерева квадрантов.Квадродерево может довольно хорошо кодировать разреженную матрицу и обеспечивает довольно простую (и эффективную кеширование) реализацию рекурсивного умножения.Сделайте базовый вариант матрицей 8x8, чтобы вы могли реализовать умножение как (оптимизированную для сборки?) 64-битную на 64-битную операцию.

Answer 2

Список 1 х и у. Например:

[0,2,0,12,0,60,1,2,1,39 ... и т. Д.]

Это означает, что есть 1 при 0,2, а 1 при 0,12 и т. Д.

Приятно то, что вам на самом деле не нужен новый тип данных, и его довольно просто анализировать.

Чтобы умножить, вы должны искать все совпадающие / частично совпадающие индексы.

Answer 3

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

Например, для матрицы 100 × 100 с 300 ненулевыми элементами, использующими двумерное представление массива, для умножения требуется 100 × 100 × 100 = 1 000 000 «операций». Использование набора индексов требует только 300 × 300 = 90000 операций. (Конечно, эти операции не сравнимы напрямую.)