Разреженная матрица

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Разрежённая матрица получается при использовании метода конечных элементов в двух измерениях. На картинке ненулевые элементы показаны чёрным.

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

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

  • есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
  • в каждой строке не превышает 10 в типичном случае;
  • ограничено , где .
  • таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей[1].

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

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

Представление[править | править код]

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

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


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

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

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


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

Мы представляем исходную матрицу , 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, как запирающий элемент

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

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, только строки и столбцы меняются ролями - значения храним по столбцам, по второму массиву можем определить строку, после подсчётов с третьим массивом - узнаём столбцы.

Библиотеки программ[править | править код]

Для вычислений с разрежёнными матрицами создан ряд библиотек для различных языков программирования, среди них:

Примечания[править | править код]

  1. 1 2 Писсанецки, 1988, Введение.
  2. SparseLib++. Дата обращения: 1 августа 2012. Архивировано 21 сентября 2012 года.
  3. uBLAS / Boost. Дата обращения: 1 августа 2012. Архивировано 4 августа 2012 года.
  4. Alan George, Esmond Ng. A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — P. 17-20. — ISBN 978-1-4503-0245-6. — doi:10.1145/1057931.1057933.
  5. T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006. Дата обращения: 1 августа 2012. Архивировано 29 июля 2012 года.
  6. Sparse matrices (scipy.sparse), SciPy Reference Guide. Дата обращения: 22 апреля 2017. Архивировано 23 апреля 2017 года.
  7. Sparse linear algebra (scipy.sparse.linalg), SciPy Reference Guide. Дата обращения: 22 апреля 2017. Архивировано 23 апреля 2017 года.

Литература[править | править код]

  • 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 с.