Участник:Руфина Третьякова/Хранение ненулевых элементов разреженных матриц. Умножение разреженной матрицы на вектор

Умножение разреженной матрицы на вектор
Последовательный алгоритм
Последовательная сложность	$nnz$
Объём входных данных	$2(nnz+n)+1$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы
Ширина ярусно-параллельной формы

Авторы статьи: Третьякова Р. М. (группа 603), Буторина Е. В. (группа 603)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

1.2 Математическое описание алгоритма

Исходные данные: разреженная матрица $M^{n*n}$, вектор $x^{n*1}$

Наиболее удобным форматом для вычисления произведения матрицы на вектор является "Compressed Sparse Row" или сокращенно CSR-формат.

Рассмотрим CSR-представление разреженной матрицы: пусть число ненулевых элементов матрицы равно $nnz$ CSR-формат представляет матрицу $M$ в виде 3-х одномерных массивов:

массив $A$ размера $nnz$ содержит ненулевые значения матрицы, $JA$ размера $nnz$ - номера столбцов ненулевых элементов., $IA$ размера $n$- содержит номер с которого начинается описание элементов строки в массивах $A$ и $JA$. Этот формат позволяет производить перемножение матрицы $M$ на вектор $x$ за $O(nnz)$ умножений и сложений.

Например, это разреженная матрица с 4-мя ненулевыми элементами

$\begin{pmatrix} 0 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 4 & 0 & 0 \\ \end{pmatrix}$,

представляемая в формате CSR 
   A  = [ 1 2 3 4 ]
   IA = [ 0 1 2 3 4 ]
   JA = [ 3 0 2 1 ]

Вычисляемые данные: вектор $M*x=y$

1.3 Вычислительное ядро алгоритма

$y_i = \sum_{k = IA_i}^{IA_{i+1}} A_k x_{JA_k}$

1.4 Макроструктура алгоритма

Псевдокод алгоритма:

 Входные данные:
   число строк матрицы n; 
   разреженная матрица в формате CSR:
     строчные указатели IA,
     столбцовые указателиJA, 
     ненулевые элементы A;
   вектор x.
 Выходные данные: произведение матрицы на вектор y.
 read CSR n, IA, JA, A;
 read x
 for i = 1,n:
   for k = IA(i), IA(i+1)-1:
           y(i) += A(k)*x(JA(k));
 write y;

1.5 Схема реализации последовательного алгоритма

Метод можно описать следующим образом:

1. привести матрицу $M$ к формату CSR
2. для $i$ от $0$ до $n-1$ вычислить $y_i$ по формуле $y_i = \sum_{k = IA_i}^{IA_{i+1}} A_k x_{JA_k}$

1.6 Последовательная сложность алгоритма

Для вычисления матрично-векторного произведения матрицы размера $n*n$ и вектора размера n в последовательном варианте требуется:

• $nnz$ сложений,
• $nnz$ умножений.

1.8 Ресурс параллелизма алгоритма

Для параллельного умножения матрицы на вектор порядка $n$ требуется последовательно выполнить следующие ярусы:

1.9 Входные и выходные данные алгоритма

Входными данными алгоритма являются:

1. размер разреженной матрицы $n$;
2. вектор $AI$ размерности $n+1$;
3. вектор $AJ$ размерности $nnz$;
4. вектор $A$ размерности $nnz$;
5. вектор $x$ размерности $n$.

Суммарная размерность входных данных: $2(nnz + n) + 1$

Выходными данными является

1. вектор $y$ размерности $n$.

Объем выходных данных: $n$.

1.10 Свойства алгоритма

Пусть используется $k$ процессоров, матрица размера $n*n$, в которой $nnz$ ненулевых элементов, тогда:

• Параллельная сложность алгоритма - $O(nnz*\frac{k}{n})$

• Последовательная сложность алгоритма - $nnz$

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Последовательная реализация имеется в пакете SPARSKIT [1], Python.Scipy [2]

Параллельный алгоритм реализован в библиотеке Matlab [3], Intel MKL [4]

3 Литература

[1] С. Писсанецки. Технология разреженных матриц. Изд. Мир, 1988.

[2] В. В. Воеводин, Вл.В. Воеводин. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002.