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

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

Выполнила: И.В. Близнякова (611 группа).

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

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

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

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

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

1.1.1 Хранение разреженной матрицы

1.1.1.1 Формат RR(C)O

Рассмотрим сначала формат RR(C)O. Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное). В данном формате вместо одного двумерного массива, используются три одномерных. Значения ненулевых элементов матрицы и соответствующие им столбцовые индексы хранятся в этом формате по строкам в двух массивах $AN$ и $JA$. Массив указателей $IA$, используется для ссылки на компоненты массивов $AN$ и $JA$, с которых начинается описание очередной строки. Последняя компонента массива $IA$ содержит указатель первой свободной компоненты в массивах $AN$ и $JA$, т.е. равна числу ненулевых элементов матрицы, увеличенному на единицу. Здесь уместно привести пример.

Рассмотрим матрицу $A$:

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

тогда ее представление в формате RR(C)O будет иметь вид:

  IA = [ 1 2 4 4 5 6 ]
  JA = [ 4 1 3 2 3 ]
  AN = [ 2 1 3 6 4 ]

Т.е. массив $AN$ содержит все не нулевые элементы исходной матрицы $A$, массив $JA$ номер столбца в котором находится соответствующий элемент из $AN$ и наконец массив $IA$ содержит номер с которого начинается описание элементов в массивах $JA$ и $AN$. Таким образом информация об элементах 2-ой строки матрицы хранится в элементах с $IA[2] = 2$ по $IA[3] - 1 = 3$ включительно массивов $JA$ и $AN$. Можно обратить внимание, что $IA[3] = IA[4] = 4$, а это означает, что 3-я строка матрицы $A$ нулевая.

В общем случае описание $r$-й строки матрицы A хранится в компонентах с $IA[r]$ до $IA[r + 1] - 1$ включительно массивов $AN$ и $JA$. Если $IA[r + 1] = IA[r]$, то это означает, что $r$-я строка нулевая. Количество элементов в массиве $IA$ на единицу больше, чем число строк исходной матрицы, а количество элементов в массивах $JA$ и $AN$ равно числу ненулевых элементов исходной матрицы.

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

Массивы $IA$ и $JA$ представляют портрет (структуру) матрицы $A$, задаваемый как множество списков смежности ассоциированного с $A$ графа. Если алгоритм, реализующий какую-либо операцию над разреженными матрицами, разбит на этапы символической обработки, на котором определяется портрет результирующей матрицы, и численной обработки, на котором определяются значения элементов результирующей матрицы, то массивы $IA$ и $JA$ заполняются на первом этапе, а массив $AN$ - на втором.

1.1.1.2 Формат RR(C)U

Рассмотрим теперь формат RR(C)U.

Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Unordered" (строчное представление, полное, но неупорядоченное). Формат RR(C)U отличается от RR(C)O тем, что в данном случае соблюдается упорядоченность строк, но внутри каждой строки элементы исходных матриц могут храниться в произвольном порядке. Для матрицы $A$ нашего примера вполне можно было бы использовать и строчное представление, полное, но неупорядоченное такое:

  IA = [ 1 2 4 4 5 6 ]
  JA = [ 4 3 1 2 3 ]
  AN = [ 2 1 3 6 4 ]

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

1.1.1.3 Замечания

Несколько замечаний по поводу рассмотренных форматов представления:

1. Очевидно, что представление матрицы в формате RR(C)O так же является и представлением в формате RR(C)U, но не наоборот.
2. Из представления матрицы в формате RR(C) нельзя получить информацию о точном количестве столбцов исходной матрицы.
3. Целесообразно (в вопросе экономии памяти) использовать представления RR(C) в случае, если матрица содержит значительное число нулевых элементов.

1.1.2 Умножение разреженной матрицы на вектор

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

Мы рассмотрим умножение разреженной матрицы общего вида, хранимой в форме RR(C)U посредством массивов $IA$, $JA$, $AN$ на заполненный вектор-столбец.

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

Исходные данные: разреженная матрица общего вида $A$ с элементами $a_{ij}$, $i = 1,...,n$ и $j = 1,...,m$. Заполненный вектор-столбец $b$ с элементами $b_{j}$, $j =1,...,m$. Вычисляемые данные: