Эту страницу предлагается объединить со страницей Разреженный массив . Пояснение причин и обсуждение — на странице Википедия:К объединению/8 декабря 2021 . Обсуждение длится не менее недели ( подробнее ). Не удаляйте шаблон до подведения итога обсуждения.

Разре́женная/разрежённая матрица — матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевая, матрица считается плотной или заполненной .

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов :

• есть O(n) . Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
• в каждой строке не превышает 10 в типичном случае;
• ограничено ${\displaystyle n^{1+\gamma }}$ , где ${\displaystyle \gamma <1}$ .
• таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей .

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

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

Представление

Существует несколько способов хранения (представления) разрежённых матриц, различающихся:

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

Словарь по ключам (DOK — Dictionary of Keys) строится как словарь, где ключ — это пара ( строка, столбец ), а значение — это соответствующий строке и столбцу элемент матрицы.

Список списков (LIL — List of Lists) строится как список строк, где строка — это список узлов вида ( столбец, значение ).

Список координат (COO — Coordinate list) хранится список из элементов вида (строка, столбец, значение).

Сжатое хранение строкой (CSR — Compressed Sparse Row, CRS — Compressed Row Storage, Йельский формат)

Мы представляем исходную матрицу ${\displaystyle M^{n\times m}}$ , cодержащую ${\displaystyle N_{NZ}}$ ненулевых значений в виде трёх массивов:

• массив значений — массив размера ${\displaystyle N_{NZ}}$ , в котором хранятся ненулевые значения, взятые подряд из первой непустой строки, затем идут значения из следующей непустой строки и т. д.
• массив индексов столбцов — массив размера ${\displaystyle N_{NZ}}$ хранит номера столбцов соответствующих элементов из массива значений.
• массив индексации строк — массив размера ${\displaystyle n+1}$ (кол_во_строк + 1), для индекса ${\displaystyle i}$ хранит количество ненулевых элементов в строках с первой до ${\displaystyle i-1}$ строки включительно, стоит отметить что последний элемент массива индексации строк совпадает с ${\displaystyle N_{NZ}}$ , а первый всегда равен ${\displaystyle 0}$ .

Примеры:

Пусть ${\displaystyle M={\begin{pmatrix}1&2&0\\0&4&0\\0&2&6\end{pmatrix}}}$ , тогда

массив_значений          = {1, 2, 4, 2, 6}
массив_индексов_столбцов = {0, 1, 1, 1, 2}
массив_индексации_строк  = {0, 2, 3, 5} -- в начале хранится 0, как запирающий элемент

Пусть ${\displaystyle M={\begin{pmatrix}1&2&0&3\\0&0&4&0\\0&1&0&11\end{pmatrix}}}$ , тогда

массив_значений          = {1, 2, 3, 4, 1, 11}
массив_индексов_столбцов = {0, 1, 3, 2, 1,  3}
массив_индексации_строк  = {0, 3, 4, 6} -- в начале хранится 0, как запирающий элемент

Для того, чтобы восстановить исходную матрицу, нужно взять некоторое значение ${\displaystyle v}$ в первом массиве и соответствующий индекс ${\displaystyle i_{v}:Arr_{values}[i_{v}]=v}$ , тогда номер столбца ${\displaystyle n_{c}=Arr_{cols}[i_{v}]}$ , а номер строки ${\displaystyle n_{r}}$ находится, как наименьшее ${\displaystyle n_{r}}$ , для которого ${\displaystyle Arr_{rows}[n_{r}+1]\geq i_{v}+1}$ , это удобно, например, при матричном умножении на плотный вектор

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++ )
• uBLAS (C++, в составе Boost )
• SPARSPAK ( Фортран )
• CSparse ( Си )
• Модуль Sparse из библиотеки SciPy ( Python ) .

Примечания

Литература

• Reginald P. Tewarson. Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 . перевод: Тьюарсон Р. Разрежённые матрицы = Sparse Matrices. — М. : Мир, 1977. — 191 с.
• Писсанецки С. Технология разрежённых матриц = Sparse Matrix Technology. — М. : Мир, 1988. — 410 с. — ISBN 5-03-000960-4 .
• Джордж А., Лю Дж. Численное решение больших разрежённых систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М. : Мир, 1984. — 333 с.

Для улучшения этой статьи желательно : Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.