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

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

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

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

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

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

$H*H^T = N*E_N$,

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

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

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

Данным алгоритм описывает получение матриц Адамара только порядка степени 2, то есть $m$ и $N$ связаны соотношением $N = 2^m$.

Получение матрицы порядка $N$ состоит из следующих $m$ шагов:

Шаг 1: $H_1 = (1);$

Шаг 2: $H_2 = \begin{pmatrix} 1 & 1 \\1 & -1 \end{pmatrix};$

Шаг 3: $H_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \\1 & -1 & 1 & -1 \\1 & 1 &- 1 & -1 \\1 & -1 & -1 & 1 \end{pmatrix}.$

...

Шаг $m$: искомая матрица $H_m$.

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

Вычислительное ядро рекурсивного алгоритма состоит из $\;N^2\;$ присвоений значений матрицы Адамара

$H_{1,1} = 1$;

$H_{ij} = H_{i(j - \frac{N}{2})}$, где $i = 1..\frac{N}{2}$, $j = \frac{N}{2}+1..N$;

$H_{ij} = H_{(i-\frac{N}{2})j}$, где $i = \frac{N}{2}+1..N$, $j = 1.. \frac{N}{2}$;

$H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})}$, где $i = \frac{N}{2}+1..N$, $j = \frac{N}{2}+1..N$.

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

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

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

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

Сначала заполняется правый верхний блок матрицы $H$

$H_{ij} = H_{i(j - \frac{N}{2})}$, где $i = 1..\frac{N}{2}$, $j = \frac{N}{2}+1..N$;

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

$H_{ij} = H_{(i-\frac{N}{2})j}$, где $i = \frac{N}{2}+1..N$, $j = 1.. \frac{N}{2}$.

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

$H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})}$, где $i = \frac{N}{2}+1..N$, $j = \frac{N}{2}+1..N$.

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

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

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

Зависимость данных для матрицы размерностью $4*4$ можно увидеть на рис.1.

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

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

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

Входные данные: $N$ - размерность матрицы.

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

Выходные данные: матрица размером $N\times N$.

Объем выходных данных: $N^2$.

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

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

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

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

Реализация MATLAB

Реализация PYTHON

Реализация WOLFRAM

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

3 Литература

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

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

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