Участник:Маркова Екатерина/Построение матрицы Адамара

Построение матрицы Адамара
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(N^2) }[/math]
Объём входных данных	[math]\displaystyle{ 1 }[/math]
Объём выходных данных	[math]\displaystyle{ N^2 }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ }[/math]

Основной автор статьи: Маркова Е.А. 615 гр.

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

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

Матрица Адамара [math]\displaystyle{ H }[/math] - это квадратная матрица размера [math]\displaystyle{ N\times N }[/math], составленная из чисел [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ -1 }[/math], столбцы которой ортогональны, так что справедливо соотношение:

[math]\displaystyle{ H*H^T = N*E_N }[/math],

где [math]\displaystyle{ E_N }[/math] - это единичная матрица размера [math]\displaystyle{ N }[/math]. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.

Предложенный алгоритм является рекурсивным и описывает получение матриц Адамара только порядка степени 2. На каждом следующем шаге алгоритма, новая матрица составляется из матрицы, полученной на предыдущем этапе, путем заполнения соответствующих блоков.

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

Пусть [math]\displaystyle{ H_m }[/math] [math]\displaystyle{ - }[/math] матрица Адамара порядка [math]\displaystyle{ 2^m }[/math] и [math]\displaystyle{ -H_m }[/math] [math]\displaystyle{ - }[/math] матрица с противоположными элементами. Тогда матрица [math]\displaystyle{ H_{2m} }[/math] получается следующим образом: [math]\displaystyle{ H_{2m} = \begin{bmatrix} H_m & H_m \\ H_m & -H_m \end{bmatrix} }[/math]

Данным алгоритм описывает получение матриц Адамара только порядка степени 2, то есть [math]\displaystyle{ m }[/math] и [math]\displaystyle{ N }[/math] связаны соотношением [math]\displaystyle{ N = 2^m }[/math].

Получение матрицы порядка [math]\displaystyle{ N }[/math] состоит из следующих [math]\displaystyle{ m }[/math] шагов:

Шаг 1: [math]\displaystyle{ H_1 = (1); }[/math]

Шаг 2: [math]\displaystyle{ H_2 = \begin{pmatrix} 1 & 1 \\1 & -1 \end{pmatrix}; }[/math]

Шаг 3: [math]\displaystyle{ H_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \\1 & -1 & 1 & -1 \\1 & 1 &- 1 & -1 \\1 & -1 & -1 & 1 \end{pmatrix}. }[/math]

...

Шаг [math]\displaystyle{ m }[/math]: искомая матрица [math]\displaystyle{ H_m }[/math].

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

Вычислительное ядро рекурсивного алгоритма состоит из [math]\displaystyle{ \;N^2\; }[/math] присвоений значений матрицы Адамара

[math]\displaystyle{ H_{1,1} = 1 }[/math];

[math]\displaystyle{ H_{ij} = H_{i(j - \frac{N}{2})} }[/math], где [math]\displaystyle{ i = 1..\frac{N}{2} }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math];

[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})j} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = 1.. \frac{N}{2} }[/math];

[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math].

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

Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.

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

В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.

Сначала заполняется правый верхний блок матрицы [math]\displaystyle{ H }[/math]

[math]\displaystyle{ H_{ij} = H_{i(j - \frac{N}{2})} }[/math], где [math]\displaystyle{ i = 1..\frac{N}{2} }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math];

затем левый нижний блок

[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})j} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = 1.. \frac{N}{2} }[/math].

Последним заполняется нижний правый блок матрицы

[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math].

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

Для заполнения матрицы [math]\displaystyle{ H }[/math] размера [math]\displaystyle{ N\times N }[/math] необходимо [math]\displaystyle{ \;N^2\; }[/math] присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.

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

Зависимость данных для матрицы размерностью [math]\displaystyle{ 4*4 }[/math] можно увидеть на рис.1.

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

Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо. Внутри каждой части происходит [math]\displaystyle{ 2^{2N}-2^{2(N-1)} }[/math] независимых присвоений, где [math]\displaystyle{ N }[/math] - номер шага алгоритма, причем размерность матрицы на шаге [math]\displaystyle{ N }[/math] равна [math]\displaystyle{ 2^N }[/math]. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки.

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

Входные данные: [math]\displaystyle{ N }[/math] - размерность матрицы.

Объем входных данных: 1.

Выходные данные: матрица размером [math]\displaystyle{ N\times N }[/math].

Объем выходных данных: [math]\displaystyle{ N^2 }[/math].

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

Алгоритм полностью детерминирован.

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

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

Реализация MATLAB

Реализация PYTHON

Реализация WOLFRAM

На языке Java реализован класс Hadamard не входящий в стандарт языка. С кодом можно ознакомиться по ссылке.

Литература

1. Мак-Вильямс Ф., Слоэн Н. — "Теория кодов, исправляющих ошибки" (1979)

2. Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — "Алгебраический аппарат квантовой информатики 2"

3. М. Н. Аршинов, Л. Е. Садовский — "Коды и математика" (1983)