Участник:Khotkin/Построение матрицы Адамара произвольного размера: различия между версиями

Версия 18:59, 15 октября 2016

Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.

Сюда тоже запилим
Последовательный алгоритм
Последовательная сложность	$O(n^3)$
Объём входных данных	$\frac{n (n + 1)}{2}$
Объём выходных данных	$\frac{n (n + 1)}{2}$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(n)$
Ширина ярусно-параллельной формы	$O(n^2)$

Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (разделы 2.4, 2.5)

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

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

Матрица Адамара $H$ порядка $n$ представляет собой матрицу размера n×n из элементов $+1$ и $-1$ , такую, что: $H \cdot H^T = n \cdot E_n,$ где $E_n$ — это единичная матрица размера n×n.

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

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

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

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

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

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

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

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

@@ Строка 16: / Строка 16: @@
 '''Матрица Адамара''' <math>H</math> порядка <math>n</math> представляет собой матрицу размера  ''n''×''n'' из элементов  <math>+1</math> и <math>-1</math>, такую, что: <math>H \cdot H^T = n \cdot E_n,</math>
-где <math>E_n</math> — это единичная матрица размера ''n''.
+где <math>E_n</math> — это единичная матрица размера ''n''×''n''.
 === Математическое описание алгоритма ===