|
|
| Строка 1: |
Строка 1: |
| − | Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
| + | ___ |
| − | {{algorithm
| |
| − | | name = Сюда тоже запилим
| |
| − | | serial_complexity = <math>O(n^3)</math>
| |
| − | | pf_height = <math>O(n)</math>
| |
| − | | pf_width = <math>O(n^2)</math>
| |
| − | | input_data = <math>\frac{n (n + 1)}{2}</math>
| |
| − | | output_data = <math>\frac{n (n + 1)}{2}</math>
| |
| − | }}
| |
| − | | |
| − | Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])
| |
| − | | |
| − | == Свойства и структура алгоритма ==
| |
| − | | |
| − | === Общее описание алгоритма ===
| |
| − | | |
| − | '''Матрица Адамара''' <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''×''n''.
| |
| − | | |
| − | Матрицы Адамара находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (ортогональные блок-схемы), квантовой информатике и прочих областях.
| |
| − | | |
| − | Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
| |
| − | * умножение строчки или столбца на −1;
| |
| − | * перестановка строчек или столбцов местами.
| |
| − | | |
| − | Матрицы Адамара, получаемые друг из друга многократным применением указанных выше преобразований называются эквивалентными.
| |
| − | | |
| − | Матрица Адамара называется нормализованной, если её первая строка и столбец состоят только из единиц.
| |
| − | | |
| − | Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>
| |
| − | | |
| − | Примерами матриц Адамара различных размеров являются следующие матрицы:
| |
| − | | |
| − | <math>H_0 = (1);</math>
| |
| − | | |
| − | <math>H_1 =
| |
| − | \begin{pmatrix} 1 & 1
| |
| − | \\1 & -1
| |
| − | \end{pmatrix};
| |
| − | </math>
| |
| − | | |
| − | <math>H_2 =
| |
| − | \begin{pmatrix} 1 & 1 & 1 & 1
| |
| − | \\1 & -1 & 1 & -1
| |
| − | \\1 & 1 &- 1 & -1
| |
| − | \\1 & -1 & -1 & 1
| |
| − | \end{pmatrix}.
| |
| − | </math>
| |
| − | | |
| − | Вообще, если <math>H_m</math> матрица Адамара порядка <math>2^m</math>, то матрица
| |
| − | <math>H_{m+1} =
| |
| − | \begin{pmatrix} H_m & H_m
| |
| − | \\H_m & -H_m
| |
| − | \end{pmatrix}
| |
| − | </math>
| |
| − | является матрицей Адамара порядка <math>2^{m+1}</math>
| |
| − | | |
| − | Кроме того, матрицу Адамара порядка <math>2^m</math> можно получить по следующей формуле <math>H^{\otimes m} = H_1 \otimes ... \otimes H_1</math>, где знак <math> \otimes </math> означает тензорное произведение.
| |
| − | | |
| − | === Математическое описание алгоритма ===
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − | === Макроструктура алгоритма ===
| |
| − | === Схема реализации последовательного алгоритма ===
| |
| − | === Последовательная сложность алгоритма ===
| |
| − | === Информационный граф ===
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − | === Свойства алгоритма ===
| |
| − | ==Программная реализация алгоритма==
| |
| − | ===Особенности реализации последовательного алгоритма===
| |
| − | === Локальность данных и вычислений ===
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − | === Выводы для классов архитектур ===
| |
| − | === Существующие реализации алгоритма ===
| |
| − | == Литература ==
| |
