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

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

Работу выполнил студент 611 группы Раев Евгений.

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

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

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

[math]H \cdot H^T = n \cdot E_n,[/math]

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

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

[math]\begin{align} H = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}[/math]

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

[math]H_n = H_{1} \otimes H_{n-1}[/math], где знак [math] \otimes [/math] означает тензорное произведение.

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

[math]\begin{align} H = &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}[/math]

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

[math] H_{0} = 1, [/math]

[math] 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}, [/math]

[math] 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} [/math]

[math] 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} [/math]

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

[math]H^{\otimes n} = H_1 \otimes ... \otimes H_1[/math]

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

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

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

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

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

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

[math]H_{i,j} = (-1)^{\sum i j}[/math]

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

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

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

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

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

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

2. Побитовое умножение индексов : [math]res = ij[/math].

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

4. Получение знака элемента по его четности: [math]sign = (-1)^{count}[/math].

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

#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 Последовательная сложность алгоритма

Построение матрицы Адамара порядка [math]2^n[/math] требует:

1. [math]2^{2n}[/math] побитовых умножений [math]ij[/math]

2. Длина битового представления числа считается по формуле [math]1+[log_2 n][/math], где [math]n[/math] - искомое число. Значит, на данном шаге для каждого значения побитового умножения [math]ij[/math] будет произведено [math]1+[log_2 n][/math] операций сдвига и [math]1+[log_2 n][/math] операций умножения на 1 (для определения значащей единицы), то есть всего [math]2 \cdot 2^{2n} \cdot(1+[log_2 n])[/math] операций.

3. [math]2^{2n}[/math] побитовых умножений количества значащих единиц с 1 для определения четности числа

Следовательно, последовательная сложность алгоритма, равна [math]2^{2n} + 2 \cdot 2^{2n} \cdot(1+[log_2 n]) + 2^{2n}[/math], то есть [math]2^{2n}(4+2[log_2 n])[/math]

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

На рисунке ниже изображен информационный граф алгоритма. Всего возможно [math](2^n)^2[/math] параллельных ветвей, так как каждый элемент матрицы может считаться независимо друг от друга.

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

1. Побитовое умножение индексов.[math]ij[/math], где [math]i[/math] и [math]j[/math] соответствующие координаты элемента [math]h_{kl}[/math];

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

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

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

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

Основной вклад в высоту ярусно-параллельной формы вносит 2 шаг, осуществляющий подсчет количества значащих единиц.

Ширина ярусно-параллельной формы будет равна [math]O(n^2)[/math].

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

Входные данные: Одно натуральное число n. Данный алгоритм на основе этого числа строит матрицу Адамара [math]H_n[/math] размерности [math]2^{n}\times 2^{n}[/math].

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

Выходные данные: [math]2^{n}\cdot 2^n[/math] чисел, которые представляют собой элементы [math]H_{i,j}[/math] матрицы Адамара [math]H_{n}[/math] размерности [math]2^{n}\times 2^{n}[/math]. Вообще говоря, в силу симметричности матрицы Адамара, можно хранить только половину от этих данных, но алгоритм в статье не предполагает такой оптимизации).

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

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

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

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

• Вычилительная мощность данного алгоритма (как соотношение последовательной сложности к сумме вхоных и выходных данных) равна:

[math]\frac{ 2^{2n}(4+2[log_2 n]) } {1+2^{2n} } [/math] ( то есть [math]\approx 2[log_2 n][/math] если [math]n -\gt +\infty[/math])

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

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

• Wolfram
• MATLAB
• SciPy

3 Литература

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

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