Участник:Khotkin/Построение матрицы Адамара произвольного размера: различия между версиями
Khotkin (обсуждение | вклад) |
Khotkin (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
Вообще, если <math>H_m</math> матрица Адамара порядка <math>2^m</math>, то матрица | Вообще, если <math>H_m</math> матрица Адамара порядка <math>2^m</math>, то матрица | ||
<math>H_{m+1} = | <math>H_{m+1} = | ||
| − | \begin{pmatrix} H_m & | + | \begin{pmatrix} H_m & H_m |
| − | \\ | + | \\H_m & -H_m |
| − | \end{pmatrix} | + | \end{pmatrix}; |
</math> | </math> | ||
является матрицей Адамара порядка <math>2^{m+1}</math> | является матрицей Адамара порядка <math>2^{m+1}</math> | ||
| − | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| − | |||
| − | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| − | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | |||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| − | |||
| − | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| − | |||
| − | |||
| − | |||
=== Информационный граф === | === Информационный граф === | ||
| − | |||
| − | |||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| − | |||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| − | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
==Программная реализация алгоритма== | ==Программная реализация алгоритма== | ||
===Особенности реализации последовательного алгоритма=== | ===Особенности реализации последовательного алгоритма=== | ||
| − | |||
=== Локальность данных и вычислений === | === Локальность данных и вычислений === | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| − | |||
| − | |||
| − | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| − | |||
| − | |||
| − | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
| − | |||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
Версия 19:28, 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 Общее описание алгоритма
- 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 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Матрица Адамара H порядка n представляет собой матрицу размера n×n из элементов +1 и -1, такую, что: H \cdot H^T = n \cdot E_n, где E_n — это единичная матрица размера n×n.
Матрицы Адамара находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (ортогональные блок-схемы), квантовой информатике и прочих областях.
Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
- умножение строчки или столбца на −1;
- перестановка строчек или столбцов местами.
Матрицы Адамара, получаемые друг из друга многократным применением указанных выше преобразований называются эквивалентными.
Матрица Адамара называется нормализованной, если её первая строка и столбец состоят только из единиц.
Под матрицией Адамара H_m подразумевается матрица порядка 2^m
Примерами матриц Адамара различных размеров являются следующие матрицы:
H_0 = (1);
H_1 = \begin{pmatrix} 1 & 1 \\1 & -1 \end{pmatrix};
H_2 = \begin{pmatrix} 1 & 1 & 1 & 1 \\1 & -1 & 1 & -1 \\1 & 1 &- 1 & -1 \\1 & -1 & -1 & 1 \end{pmatrix}.
Вообще, если H_m матрица Адамара порядка 2^m, то матрица H_{m+1} = \begin{pmatrix} H_m & H_m \\H_m & -H_m \end{pmatrix}; является матрицей Адамара порядка 2^{m+1}
