Разре́женная/разрежённая матрица — матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевая, матрица считается плотной или заполненной.
Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов[1]:
есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
в каждой строке не превышает 10 в типичном случае;
ограничено , где .
таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей[1].
При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто - и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.
Существует несколько способов хранения (представления) разрежённых матриц, различающихся:
удобством изменения структуры матрицы (активно используется косвенная адресация) — это структуры в виде списков и словарей.
скоростью доступа к элементам и возможной оптимизацией матричных вычислений (чаще используются плотные блоки-массивы, увеличивая локальность доступа к памяти).
Словарь по ключам (DOK — Dictionary of Keys)
строится как словарь, где ключ — это пара (строка, столбец), а значение — это соответствующий строке и столбцу элемент матрицы.
Список списков (LIL — List of Lists)
строится как список строк, где строка — это список узлов вида (столбец, значение).
Список координат (COO — Coordinate list)
хранится список из элементов вида (строка, столбец, значение).
Мы представляем исходную матрицу , cодержащую ненулевых значений в виде трёх массивов:
массив значений — массив размера , в котором хранятся ненулевые значения, взятые подряд из первой непустой строки, затем идут значения из следующей непустой строки и т. д.
массив индексов столбцов — массив размера хранит номера столбцов соответствующих элементов из массива значений.
массив индексации строк — массив размера (кол_во_строк + 1), для индекса хранит количество ненулевых элементов в строках с первой до строки включительно, стоит отметить что последний элемент массива индексации строк совпадает с , а первый всегда равен .
Примеры:
Пусть , тогда
массив_значений={1,2,4,2,6}массив_индексов_столбцов={0,1,1,1,2}массив_индексации_строк={0,2,3,5}-- в начале хранится 0, как запирающий элемент
Пусть , тогда
массив_значений={1,2,3,4,1,11}массив_индексов_столбцов={0,1,3,2,1,3}массив_индексации_строк={0,3,4,6}-- в начале хранится 0, как запирающий элемент
Для того, чтобы восстановить исходную матрицу, нужно взять некоторое значение в первом массиве и соответствующий индекс ,
тогда номер столбца , а номер строки находится, как наименьшее , для которого , это удобно, например, при матричном умножении на плотный вектор
voidsmdv(constcrsm*A,double*b,constdouble*v)// b += Av{// crsm это структура {int n, int m, int nnz, double aval[], double aicol[], double airow[]};for(introw=0;row<n;++row)for(inti=A->airow[row];i<A->airow[row+1];++i)b[row]+=A->aval[i]*v[A->aicol[i]];}
То же самое, что и CRS, только строки и столбцы меняются ролями — значения храним по столбцам, по второму массиву можем определить строку, после подсчётов с третьим массивом — узнаём столбцы.
Библиотеки программ
Для вычислений с разрежёнными матрицами создан ряд библиотек для различных языков программирования, среди них:
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 с.