Ссылка для сложности самого низкого порядка разреженной симметричной матрицы, предварительно умножающей полный вектор

Question

В статье, которую я пишу, я использую матрицу n x n, умножающую плотный вектор размерности n. В своей естественной форме эта матрица имеет O (n ^ 2) пространственную сложность, а умножение занимает время O (n ^ 2).

Однако известно, что матрица симметрична и имеет нулевые значения по диагонали. Матрица также очень разрежена: большинство недиагональных элементов равны нулю.

Может ли кто-нибудь связать меня с алгоритмом / бумагой / структурой данных, который использует разреженное представление симметричной матрицы для приближения к O (nlogn) или, возможно, даже к O (n), в случаях высокой разреженности?

Answer 1

Я бы взглянул на библиотеку csparse Тима Дэвиса. Есть также соответствующая книга, которая описывает целый ряд алгоритмов разреженных матриц.

В редком случае можно выполнить операцию A*x для сложности O(|A|), то есть линейной по количеству ненулевых элементов в матрице.

Answer 2

Вас интересуют параллельные алгоритмы такого рода http://www.cs.cmu.edu/~scandal/cacm/node9.html