Участник:Blizn/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на вектор.: различия между версиями
Blizn (обсуждение | вклад) м (Blizn переименовал страницу [[Участник:Иванов Иван/Хранение ненулевых элементов разреженной матрицы. Умножение разреженной матрицы на век…) |
Blizn (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | {{algorithm | |
| + | | name = Умножение разреженной матрицы на вектор | ||
| + | | serial_complexity = <math>nz</math> | ||
| + | | pf_height = <math>O(n)</math> | ||
| + | | pf_width = <math>O(n)</math> | ||
| + | | input_data = <math>2nz+m+n+1</math> | ||
| + | | output_data = <math>n</math> | ||
| + | }} | ||
| + | Выполнила: [[Участник:Blizn|И.В. Близнякова]] (611 группа). | ||
| + | |||
| + | = Свойства и структура алгоритма = | ||
| + | |||
| + | == Общее описание алгоритма == | ||
| + | '''Разрежённая матрица''' — это матрица с преимущественно нулевыми элементами. В противном случае, если большая часть элементов матрицы ненулевые, матрица считается '''''плотной'''''. | ||
| + | |||
| + | Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов: | ||
| + | * есть <math>O(n)</math>. Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов; | ||
| + | * в каждой строке не превышает 10 в типичном случае; | ||
| + | * ограничено <math>n^{1+\gamma}</math>, где <math>\gamma < 1</math>. | ||
| + | * таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей. | ||
| + | |||
| + | === Хранение разреженной матрицы === | ||
| + | ==== Формат RR(C)O ==== | ||
| + | Рассмотрим сначала формат '''RR(C)O'''. Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное). В данном формате вместо одного двумерного массива, используются три одномерных. Значения ненулевых элементов матрицы и соответствующие им столбцовые индексы хранятся в этом формате по строкам в двух массивах <math>AN</math> и <math>JA</math>. Массив указателей <math>IA</math>, используется для ссылки на компоненты массивов <math>AN</math> и <math>JA</math>, с которых начинается описание очередной строки. Последняя компонента массива <math>IA</math> содержит указатель первой свободной компоненты в массивах <math>AN</math> и <math>JA</math>, т.е. равна числу ненулевых элементов матрицы, увеличенному на единицу. Здесь уместно привести пример. | ||
| + | |||
| + | Рассмотрим матрицу <math>A</math>: | ||
| + | :<math>\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}</math>, | ||
| + | тогда ее представление в формате '''RR(C)O''' будет иметь вид: | ||
| + | IA = [ 1 2 4 4 5 6 ] | ||
| + | JA = [ 4 1 3 2 3 ] | ||
| + | AN = [ 2 1 3 6 4 ] | ||
| + | Т.е. массив <math>AN</math> содержит все не нулевые элементы исходной матрицы <math>A</math>, массив <math>JA</math> номер столбца в котором находится соответствующий элемент из <math>AN</math> и наконец массив <math>IA</math> содержит номер с которого начинается описание элементов в массивах <math>JA</math> и <math>AN</math>. Таким образом информация об элементах 2-ой строки матрицы хранится в элементах с <math>IA[2] = 2</math> по <math>IA[3] - 1 = 3</math> включительно массивов <math>JA</math> и <math>AN</math>. Можно обратить внимание, что <math>IA[3] = IA[4] = 4</math>, а это означает, что 3-я строка матрицы <math>A</math> нулевая. | ||
| + | |||
| + | В общем случае описание <math>r</math>-й строки матрицы A хранится в компонентах с <math>IA[r]</math> до <math>IA[r + 1] - 1</math> включительно массивов <math>AN</math> и <math>JA</math>. Если <math>IA[r + 1] = IA[r]</math>, то это означает, что <math>r</math>-я строка нулевая. Количество элементов в массиве <math>IA</math> на единицу больше, чем число строк исходной матрицы, а количество элементов в массивах <math>JA</math> и <math>AN</math> равно числу ненулевых элементов исходной матрицы. | ||
| + | |||
| + | Данный способ представления называют ''полным'', поскольку представлена вся матрица <math>A</math>, ''упорядоченным'', поскольку элементы каждой строки матрицы <math>A</math> хранятся в соответствии с возрастанием столбцовых индексов, и строчным, поскольку информация о матрице <math>A</math> указывается по строкам. | ||
| + | |||
| + | Массивы <math>IA</math> и <math>JA</math> представляют портрет (структуру) матрицы <math>A</math>, задаваемый как множество списков смежности ассоциированного с <math>A</math> графа. Если алгоритм, реализующий какую-либо операцию над разреженными матрицами, разбит на этапы символической обработки, на котором определяется портрет результирующей матрицы, и численной обработки, на котором определяются значения элементов результирующей матрицы, то массивы <math>IA</math> и <math>JA</math> заполняются на первом этапе, а массив <math>AN</math> - на втором. | ||
| + | |||
| + | ==== Формат RR(C)U ==== | ||
| + | |||
| + | Рассмотрим теперь формат '''RR(C)U'''. | ||
| + | |||
| + | Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Unordered" (строчное представление, полное, но неупорядоченное). Формат '''RR(C)U''' отличается от '''RR(C)O''' тем, что в данном случае соблюдается упорядоченность строк, но внутри каждой строки элементы исходных матриц могут храниться в произвольном порядке. Для матрицы <math>A</math> нашего примера вполне можно было бы использовать и строчное представление, полное, но неупорядоченное такое: | ||
| + | IA = [ 1 2 4 4 5 6 ] | ||
| + | JA = [ 4 3 1 2 3 ] | ||
| + | AN = [ 2 1 3 6 4 ] | ||
| + | Такие неупорядоченные представления могут быть очень удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными. | ||
| + | |||
| + | ==== Замечания ==== | ||
| + | |||
| + | Несколько замечаний по поводу рассмотренных форматов представления: | ||
| + | # Очевидно, что представление матрицы в формате '''RR(C)O''' так же является и представлением в формате '''RR(C)U''', но не наоборот. | ||
| + | # Из представления матрицы в формате '''RR(C)''' нельзя получить информацию о точном количестве столбцов исходной матрицы. | ||
| + | # Целесообразно (в вопросе экономии памяти) использовать представления '''RR(C)''' в случае, если матрица содержит значительное число нулевых элементов. | ||
| + | |||
| + | === Умножение разреженной матрицы на вектор === | ||
| + | |||
| + | '''Умножение разреженной матрицы на вектор''' - важным приложением этих алгоритмов является вычисление векторов Ланцоша, необходимое при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы. Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция - это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется. | ||
| + | |||
| + | Мы рассмотрим умножение разреженной матрицы общего вида, хранимой в форме '''RR(C)U''' посредством массивов <math>IA</math>, <math>JA</math>, <math>AN</math> на заполненный вектор-столбец. | ||
| + | |||
| + | == Математическое описание алгоритма == | ||
| + | |||
| + | Исходные данные: разреженная матрица общего вида <math>A</math> с элементами <math>a_{ij}</math>, <math>i = 1,...,n</math> и <math>j = 1,...,m</math>. Заполненный вектор-столбец <math>b</math> с элементами <math>b_{j}</math>, <math>j =1,...,m</math>. | ||
| + | Вычисляемые данные: | ||
Версия 16:15, 22 октября 2016
| Умножение разреженной матрицы на вектор | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]nz[/math] |
| Объём входных данных | [math]2nz+m+n+1[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(n)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n)[/math] |
Выполнила: И.В. Близнякова (611 группа).
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если большая часть элементов матрицы ненулевые, матрица считается плотной.
Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов:
- есть [math]O(n)[/math]. Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
- в каждой строке не превышает 10 в типичном случае;
- ограничено [math]n^{1+\gamma}[/math], где [math]\gamma \lt 1[/math].
- таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей.
1.1.1 Хранение разреженной матрицы
1.1.1.1 Формат RR(C)O
Рассмотрим сначала формат RR(C)O. Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Ordered" (строчное представление, полное и упорядоченное). В данном формате вместо одного двумерного массива, используются три одномерных. Значения ненулевых элементов матрицы и соответствующие им столбцовые индексы хранятся в этом формате по строкам в двух массивах [math]AN[/math] и [math]JA[/math]. Массив указателей [math]IA[/math], используется для ссылки на компоненты массивов [math]AN[/math] и [math]JA[/math], с которых начинается описание очередной строки. Последняя компонента массива [math]IA[/math] содержит указатель первой свободной компоненты в массивах [math]AN[/math] и [math]JA[/math], т.е. равна числу ненулевых элементов матрицы, увеличенному на единицу. Здесь уместно привести пример.
Рассмотрим матрицу [math]A[/math]:
- [math]\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}[/math],
тогда ее представление в формате RR(C)O будет иметь вид:
IA = [ 1 2 4 4 5 6 ] JA = [ 4 1 3 2 3 ] AN = [ 2 1 3 6 4 ]
Т.е. массив [math]AN[/math] содержит все не нулевые элементы исходной матрицы [math]A[/math], массив [math]JA[/math] номер столбца в котором находится соответствующий элемент из [math]AN[/math] и наконец массив [math]IA[/math] содержит номер с которого начинается описание элементов в массивах [math]JA[/math] и [math]AN[/math]. Таким образом информация об элементах 2-ой строки матрицы хранится в элементах с [math]IA[2] = 2[/math] по [math]IA[3] - 1 = 3[/math] включительно массивов [math]JA[/math] и [math]AN[/math]. Можно обратить внимание, что [math]IA[3] = IA[4] = 4[/math], а это означает, что 3-я строка матрицы [math]A[/math] нулевая.
В общем случае описание [math]r[/math]-й строки матрицы A хранится в компонентах с [math]IA[r][/math] до [math]IA[r + 1] - 1[/math] включительно массивов [math]AN[/math] и [math]JA[/math]. Если [math]IA[r + 1] = IA[r][/math], то это означает, что [math]r[/math]-я строка нулевая. Количество элементов в массиве [math]IA[/math] на единицу больше, чем число строк исходной матрицы, а количество элементов в массивах [math]JA[/math] и [math]AN[/math] равно числу ненулевых элементов исходной матрицы.
Данный способ представления называют полным, поскольку представлена вся матрица [math]A[/math], упорядоченным, поскольку элементы каждой строки матрицы [math]A[/math] хранятся в соответствии с возрастанием столбцовых индексов, и строчным, поскольку информация о матрице [math]A[/math] указывается по строкам.
Массивы [math]IA[/math] и [math]JA[/math] представляют портрет (структуру) матрицы [math]A[/math], задаваемый как множество списков смежности ассоциированного с [math]A[/math] графа. Если алгоритм, реализующий какую-либо операцию над разреженными матрицами, разбит на этапы символической обработки, на котором определяется портрет результирующей матрицы, и численной обработки, на котором определяются значения элементов результирующей матрицы, то массивы [math]IA[/math] и [math]JA[/math] заполняются на первом этапе, а массив [math]AN[/math] - на втором.
1.1.1.2 Формат RR(C)U
Рассмотрим теперь формат RR(C)U.
Сокращенное название данного формата происходит от английского словосочетания "Row - wise Representation Complete and Unordered" (строчное представление, полное, но неупорядоченное). Формат RR(C)U отличается от RR(C)O тем, что в данном случае соблюдается упорядоченность строк, но внутри каждой строки элементы исходных матриц могут храниться в произвольном порядке. Для матрицы [math]A[/math] нашего примера вполне можно было бы использовать и строчное представление, полное, но неупорядоченное такое:
IA = [ 1 2 4 4 5 6 ] JA = [ 4 3 1 2 3 ] AN = [ 2 1 3 6 4 ]
Такие неупорядоченные представления могут быть очень удобны в практических вычислениях. Результаты большинства матричных операций получаются неупорядоченными, а их упорядочение стоило бы значительных затрат машинного времени. В то же время, за немногими исключениями, алгоритмы для разреженных матриц не требуют, чтобы их представления были упорядоченными.
1.1.1.3 Замечания
Несколько замечаний по поводу рассмотренных форматов представления:
- Очевидно, что представление матрицы в формате RR(C)O так же является и представлением в формате RR(C)U, но не наоборот.
- Из представления матрицы в формате RR(C) нельзя получить информацию о точном количестве столбцов исходной матрицы.
- Целесообразно (в вопросе экономии памяти) использовать представления RR(C) в случае, если матрица содержит значительное число нулевых элементов.
1.1.2 Умножение разреженной матрицы на вектор
Умножение разреженной матрицы на вектор - важным приложением этих алгоритмов является вычисление векторов Ланцоша, необходимое при итерационном решении линейных уравнений методом сопряженных градиентов, а также при вычислении собственных значений и собственных векторов матрицы. Достоинство этих процедур, с вычислительной точки зрения, состоит в том, что единственная требуемая матричная операция - это повторное умножение матрицы на последовательность заполненных векторов; сама матрица не меняется.
Мы рассмотрим умножение разреженной матрицы общего вида, хранимой в форме RR(C)U посредством массивов [math]IA[/math], [math]JA[/math], [math]AN[/math] на заполненный вектор-столбец.
1.2 Математическое описание алгоритма
Исходные данные: разреженная матрица общего вида [math]A[/math] с элементами [math]a_{ij}[/math], [math]i = 1,...,n[/math] и [math]j = 1,...,m[/math]. Заполненный вектор-столбец [math]b[/math] с элементами [math]b_{j}[/math], [math]j =1,...,m[/math]. Вычисляемые данные:
