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

Версия 23:43, 12 октября 2016

Умножение разреженной матрицы на вектор
Последовательный алгоритм
Последовательная сложность	[math][/math]
Объём входных данных	[math][/math]
Объём выходных данных	[math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

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

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
- 2.1 Масштабируемость алгоритма и его реализации
- 2.2 Существующие реализации алгоритма
3 Литература

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

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

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

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

Исходные данные: матрица [math]A[/math] (элементы [math]A_{ij}, i, j = 1, \ldots, n[/math]).,

вектор [math]b[/math]

Вычисляемые данные: вектор [math]c[/math]

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

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

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

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

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

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

[math][/math] делений,
[math][/math] сложений (вычитаний),
[math][/math] умножений.

1.7 Информационный граф

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

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

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

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

2.1 Масштабируемость алгоритма и его реализации

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

3 Литература

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

@@ Строка 20: / Строка 20: @@
 === Математическое описание алгоритма ===
-Исходные данные:
+Исходные данные:  матрица <math>A</math> (элементы <math>A_{ij}, i, j = 1, \ldots, n</math>).,
-Вычисляемые данные:
+ вектор <math>b</math>
+Вычисляемые данные: вектор  <math>c</math>
 === Вычислительное ядро алгоритма ===