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

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

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

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

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

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

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

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

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

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

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

Сначала заполняется правый верхний блок матрицы [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].

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

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

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

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

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

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

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

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

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

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

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

Нахождение матрицы Адамара доступно в среде MATLAB и реализовано через функцию hadamard(n).[1]

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