Участник:Евгений Раев/Построение матрицы Адамара произвольного размера

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

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

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

Матрица Адамара $H$ — это квадратная матрица размера n×n, составленная из чисел 1 и −1, столбцы которой ортогональны, так что справедливо соотношение

$H \cdot H^T = n \cdot E_n,$

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

Матрица оператора Адамара имееет вид

$\begin{align} H = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

Соответственно, существует итерационная формула нахождения матриц Адамара, через тензорное произведение матрицы оператора Адамара на матрицу Адамара меньшего порядка:

$H_n = H_{1} \otimes H_{n-1}$

Мы будем использовать в дальнейшем нормализованную матрицу оператора Адамара, без коэффицента (для удобности вывода):

$\begin{align} H = &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}$

Представим пример высчитывания матриц Адамара:

$H_{0} = 1,$

$H_{1} = H_{1} \otimes H_{0} = \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \otimes 1 = \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix},$

$H_{2} = H_{1} \otimes H_{1} = \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \otimes \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} = \begin{pmatrix}\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\end{pmatrix}$

$H_{3} = H_{1} \otimes H_{2} = \begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \otimes \begin{pmatrix}\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\end{pmatrix} = \begin{pmatrix}\begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1\\ 1 & 1 & 1 & -1 & -1 & -1 & -1 & -1\\ 1 & -1 & 1 & 1 & -1 & 1 & -1 & 1\\ 1 & 1 & -1 & 1 & -1 & -1 & 1 & 1\\ 1 & -1 & -1 & -1 & -1 & 1 & 1 & -1\\ \end{array}\end{pmatrix}$

Таким образом, получаем последовательность матриц Адамамра размерностью $2^n$

$H^{\otimes n} = H_1 \otimes ... \otimes H_1$, где знак $\otimes$ означает тензорное произведение.

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

Тензорное произведение довольно затратно для реализации на вычислительной технике (необходимо хранить в памяти матрицу предыдущего порядка), поэтому существует формула для определения элемента матрицы Адамара по его индексам:

$H_{i,j} = (-1)^{\sum i_{2 } j_{2 }}$, где $i_{2}$ и $j_{2}$ - битовые представляения значений индексов, а $i_{2 } j_{2 }$ - побитовое умножение.

То есть, знак элемента матрицы Адамара зависит от количества едининц в побитовом произведении индексов - если это число чётное - то знак положительный, если нечётное - отрицательный.

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

Вычислительное ядро расчете элементов матрицы Адамара это вычисление элемента матрицы Адамара по его индексам:

$H_{i,j} = (-1)^{\sum i_{2 } j_{2 }}$

Данная операция независима для каждого элемента, соответственно именно она подлежит распараллеливанию.

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

В вычислительном ядре используется операция опеределения четности суммы значачих единиц в результате побитового умножения двух чисел.

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

Последовательность исполнения метода следующая:

1. Определение индексов находимого элемента матрицы Адамара: $i$ и $j$.

2. Побитовое умножение индексов : $res = i_{2} j_{2}$.

3. Подсчет количества значащих единиц в $res$: $count = \sum res$.

4. Получение знака элемента: $sign = (-1)^{count}$.

Данному алгоритму соответствует приведенный ниже код на языке С++:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int get_sign(int i, int j) //Get sign Hadamard matrix's element by indices
{
    int res = i & j;
    int count;
    for (count=0; res; res>>=1) 
        { 
            if (res & 1)
                count++;
        }
    if (count & 1 ==1)
        return -1;
    else
        return 1;
}

int print_HadamardMatrix(int N) //print Hadamard matrix 2^n size
{
    int matr_size(pow(2,N));
    for (int i = 0; i < matr_size; i++)
    {
        for (int j = 0; j < matr_size; j++) 
        {

            if (get_sign(i,j)==1) 
                    cout <<" 1 ";
            else 
                    cout <<"-1 ";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

int main(int argc, const char * argv[]) 
{
    if(argc!=2) 
    {
        printf("Matrix size missing\n");
        return 1;
    }
    int N(atoi(argv[1]));
    print_HadamardMatrix(N);

    return 0;
}

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

Построение матрицы Адамара порядка $N = 2^n$ требует:

1. $N^2$ побитовых умножений $ij$

2. $N$ операций сдвига.

3. Првиет

Для построения матрицы Адамара порядка $N=2^n$ в первом шаге потребуется $N^2$ побитовых умножений k&l. Во втором шаге, как говорилось выше, сложность метода вычисления количества единиц числа в двоичном представлении равна удвоенному количеству единиц. В наихудшем случае сложность равна $2log_2N$, при k=l=N-1, а в наилучшем 0. Для нахождения степени всех элементов матрицы потребуются $2N^2[\frac{log_2N}{4}]$ операций. В третьем шаге для определения знака потребуется $N^2$ операций.

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

На рисунке ниже изображен информационный граф алгоритма.

Рисунок 1. Граф алгоритма.

1. Побитовое умножение индексов.$i_{2}j_{2}$, где $i$ и $j$ соответствующие координаты элемента $h_{kl}$;

2. Подсчет количества значащих единиц. Состоит из последовательных сдвигов и побитового "И" с 1.

3. Определение четности количества - побитовое "И" количества значащих единиц с 1.

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

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

Объём входных данных: 1 (число n).

Выходные данные: матрица Адамара $H_{n}$ размерностью $2^n$.

Объём выходных данных: $2^{n+n}$.

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

• Соотношение последовательной и параллельной сложности является линейным.

• Алогритм построения матрицы Адамара не является детерминированным.

3 Литература

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

[2] Википедия – свободная энциклопедия [Электронный ресурс]. - https://en.wikipedia.org/wiki/Hadamard_transform. - (дата обращения: 15.10.2016).