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

Построение матрицы Адамара произвольного размера
Последовательный алгоритм
Последовательная сложность	[math]O(n*(2^{n})^2))[/math]
Объём входных данных	[math]1[/math]
Объём выходных данных	[math](2^n)^2[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(n)[/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] (Описано в [2]).

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] требует рассчета [math](2^{n})^2[/math] элементов матрицы. Это включает в себя:

1. [math](2^{n})^2[/math] побитовых умножений индексов элемента [math]i \& j[/math].

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

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

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

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

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

Рисунок 1. Двухмерная модель алгоритма.

Рисунок 1. Трехмерная модель алгоритма. In - взодные данные, Out - результаты, [math] \& [/math] - операция умножения,[math] \sum [/math] - операция подсчета значащих единиц,[math] \pm [/math] - операция определения знака элемента по четности

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

2. Операция [math] \sum [/math] -подсчет количества значащих единиц. Состоит из последовательных сдвигов и побитового умножения с 1.

3. Операция [math] \pm [/math] - определение четности количества значащих единиц. Состоит из побитового умножения количества значащих единиц с 1.

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

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

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

Ширина ярусно-параллельной формы будет равна [math]O((2^n)^2)[/math] - количество рассчитываемых элементов. Высота ярусно-параллельной формы будет равна [math]O(2+2n)=O(n)[/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})^2[/math].

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

• Соотношение последовательной и параллельной сложности можно определить как отношение высоты ярусно-параллельной формы и общей последовательно сложности, то есть [math]\frac{ (2+2n)(2^n)^2 }{2+2n} = (2^n)^2 [/math]. Таким образом, соотношение - экспоненциально.

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

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

[math]\frac{ (2^{n})^2(2+2n) } {1+(2^{n})^2 } [/math] ( то есть [math]\approx 2n[/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).