Участник:Руфина Третьякова/Хранение ненулевых элементов разреженных матриц. Умножение разреженной матрицы на вектор: различия между версиями
Trrufina (обсуждение | вклад) |
Trrufina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
'''Входные данные''': | '''Входные данные''': | ||
число строк матрицы ''n''; | |||
разреженная матрица в формате CSR: | разреженная матрица в формате CSR: | ||
''IA'', ''JA'' ''A'' | строчные указатели ''IA'', | ||
столбцовые указатели''JA'', | |||
ненулевые элементы ''A''; | |||
вектор ''x''. | вектор ''x''. | ||
'''Выходные данные''': произведение матрицы на вектор ''y''. | '''Выходные данные''': произведение матрицы на вектор ''y''. | ||
''Q'' := '''new''' priority queue | ''Q'' := '''new''' priority queue | ||
'''for | '''for''' ''i'' = 1,n: | ||
'''for''' ''k'' = ''IA(i)'', ''IA(i+1)''-1: | |||
y(i) += A(k)*x(JA(k)); | |||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
Версия от 21:09, 12 октября 2016
| Умножение разреженной матрицы на вектор | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ }[/math] |
| Объём входных данных | [math]\displaystyle{ }[/math] |
| Объём выходных данных | [math]\displaystyle{ }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ }[/math] |
Авторы статьи: Третьякова Р. М. (группа 603), Буторина Е. В. (группа 603)
Свойства и структура алгоритма
Общее описание алгоритма
Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной. Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных. При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.
Математическое описание алгоритма
Исходные данные: матрица [math]\displaystyle{ A }[/math] (элементы [math]\displaystyle{ A_{ij}, i, j = 1, \ldots, n }[/math]).,
вектор [math]\displaystyle{ b }[/math]
Вычисляемые данные: вектор [math]\displaystyle{ c }[/math]
Вычислительное ядро алгоритма
Макроструктура алгоритма
Псевдокод алгоритма:
Входные данные:
число строк матрицы n;
разреженная матрица в формате CSR:
строчные указатели IA,
столбцовые указателиJA,
ненулевые элементы A;
вектор x.
Выходные данные: произведение матрицы на вектор y.
Q := new priority queue
for i = 1,n:
for k = IA(i), IA(i+1)-1:
y(i) += A(k)*x(JA(k));
Схема реализации последовательного алгоритма
Метод можно описать следующим образом:
Последовательная сложность алгоритма
Для вычисления сингулярных чисел и векторов матрицы порядка n в последовательном варианте требуется:
- [math]\displaystyle{ }[/math] делений,
- [math]\displaystyle{ }[/math] сложений (вычитаний),
- [math]\displaystyle{ }[/math] умножений.
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Масштабируемость алгоритма и его реализации
Существующие реализации алгоритма
Литература
1. С. Писсанецки Технология разреженных матриц. Изд. Мир, 1988.