Русская Википедия:Разреженная матрица
Шаблон:К переименованию Шаблон:К объединению
Разрежённая матрица — матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевая, матрица считается плотной.
Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементовШаблон:Sfn:
- есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
- в каждой строке не превышает 10 в типичном случае;
- ограничено <math>n^{1+\gamma}</math>, где <math>\gamma < 1</math>.
- таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулейШаблон:Sfn.
Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.
При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто - и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.
Представление
Существует несколько способов хранения (представления) разрежённых матриц, различающихся:
- удобством изменения структуры матрицы (активно используется косвенная адресация) — это структуры в виде списков и словарей.
- скоростью доступа к элементам и возможной оптимизацией матричных вычислений (чаще используются плотные блоки-массивы, увеличивая локальность доступа к памяти).
Словарь по ключам (DOK — Dictionary of Keys) строится как словарь, где ключ — это пара (строка, столбец), а значение — это соответствующий строке и столбцу элемент матрицы.
Список списков (LIL — List of Lists) строится как список строк, где строка — это список узлов вида (столбец, значение).
Список координат (COO — Coordinate list) хранится список из элементов вида (строка, столбец, значение).
Сжатое хранение строкой (CSR — Compressed Sparse Row, CRS — Compressed Row Storage, Йельский формат)
Мы представляем исходную матрицу <math>M^{n\times m}</math>, cодержащую <math>N_{NZ}</math> ненулевых значений в виде трёх массивов:
- массив значений — массив размера <math>N_{NZ}</math>, в котором хранятся ненулевые значения, взятые подряд из первой непустой строки, затем идут значения из следующей непустой строки и т. д.
- массив индексов столбцов — массив размера <math>N_{NZ}</math> хранит номера столбцов соответствующих элементов из массива значений.
- массив индексации строк — массив размера <math>n+1</math> (кол_во_строк + 1), для индекса <math>i</math> хранит количество ненулевых элементов в строках с первой до <math>i - 1</math> строки включительно, стоит отметить что последний элемент массива индексации строк совпадает с <math>N_{NZ}</math>, а первый всегда равен <math>0</math>.
Примеры:
Пусть <math>M = \begin{pmatrix} 1 & 2 & 0\\ 0 & 4 & 0\\ 0 & 2 & 6\end{pmatrix}</math>, тогда
массив_значений = {1, 2, 4, 2, 6}
массив_индексов_столбцов = {0, 1, 1, 1, 2}
массив_индексации_строк = {0, 2, 3, 5} -- в начале хранится 0, как запирающий элемент
Пусть <math>M = \begin{pmatrix} 1 & 2 & 0 & 3\\ 0 & 0 & 4 & 0\\ 0 & 1 & 0 & 11\end{pmatrix}</math>, тогда
массив_значений = {1, 2, 3, 4, 1, 11}
массив_индексов_столбцов = {0, 1, 3, 2, 1, 3}
массив_индексации_строк = {0, 3, 4, 6} -- в начале хранится 0, как запирающий элемент
Для того, чтобы восстановить исходную матрицу, нужно взять некоторое значение <math>v</math> в первом массиве и соответствующий индекс <math>i_{v} : Arr_{values}[i_v] = v</math>, тогда номер столбца <math>n_{c} = Arr_{cols}[i_v]</math>, а номер строки <math>n_r</math> находится, как наименьшее <math>n_r</math>, для которого <math>Arr_{rows}[n_r+1] \geq i_v+1</math>, это удобно, например, при матричном умножении на плотный вектор
void smdv(const crsm *A, double *b, const double *v) // b += Av
{
// crsm это структура {int n, int m, int nnz, double aval[], double aicol[], double airow[]};
for(int row = 0; row < n; ++row)
for(int i = A->airow[row]; i < A->airow[row+1]; ++i)
b[row] += A->aval[i] * v[A->aicol[i]];
}
Сжатое хранение столбцом (CSС — Compressed Sparse Column, CСS — Compressed Column Storage)
То же самое, что и CRS, только строки и столбцы меняются ролями — значения храним по столбцам, по второму массиву можем определить строку, после подсчётов с третьим массивом — узнаём столбцы.
Библиотеки программ
Для вычислений с разрежёнными матрицами создан ряд библиотек для различных языков программирования, среди них:
- SparseLib++ (C++)[1]
- uBLAS (C++, в составе Boost)[2]
- SPARSPAK (Фортран)[3]
- CSparse (Си)[4]
- Модуль Sparse из библиотеки SciPy (Python)[5][6].
Примечания
Литература
- Шаблон:Книга перевод: Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
