Вычислительная эффективность: разреженная или полная

Question

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

Хотя хранить полную матрицу в разреженной форме тривиально, я просто хочу знать причину этого факта.

Я предполагаю, что чтение индекса в разреженном виде будет основным фактором, влияющим на время вычислений. Любые другие элегантные мысли?

Answer 1

Рассмотрим следующую плотную матрицу:

1 2 3
4 5 6
7 8 9

Если я храню его в непрерывном блоке:

1 2 3 4 5 6 7 8 9

Я могу получить прямой доступ к элементам матрицы по номеру строки и столбца с некоторой базовой арифметикой.

Теперь рассмотрим эту разреженную матрицу:

1 0 0
0 0 2
0 3 0

Чтобы эффективно хранить эту матрицу, я отбрасываю ненулевые элементы, поэтому теперь она становится

1 2 3

Но этой информации явно недостаточно для выполнения таких операций, как умножение матрицы на вектор! Поэтому нам нужно добавить дополнительную информацию , чтобы извлечь элементы из матрицы.

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

1. Выполнить дополнительную работу для доступа к элементам
2. Храните больше информации, чтобы сохранить структуру матрицы

Итак, как вы можете видеть, преимущества хранения возникают только в том случае, если в матрице достаточно нулей, чтобы компенсировать дополнительную информацию, которую мы храним, чтобы сохранить структуру матрицы. Например, в формате Yale мы экономим только на памяти, когда число ненулевых (NNZ) значений меньше (m(n − 1) − 1) / 2, где m = количество строк и n = число столбцов.

Answer 2

Есть несколько причин, по которым почти полная разреженная матрица требует больших вычислительных затрат, чем просто использование полной матрицы.Наиболее очевидным, как вы указали, является то, что разреженные элементы должны быть проиндексированы (для общей разреженной матрицы, я полагаю, Matlab использует схему Compressed Row Storage ).

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