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

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

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

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

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

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

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$ необходимо $\frac{3N^2}{4}$. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.

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

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

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

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