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

еееее Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.

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

Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (раздел 2.2), А.М.Теплов (разделы 2.4, 2.5)

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

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

Матрица Адамара [math]\displaystyle{ H }[/math] порядка [math]\displaystyle{ n }[/math] представляет собой матрицу размера n×n из элементов [math]\displaystyle{ +1 }[/math] и [math]\displaystyle{ -1 }[/math], такую, что: [math]\displaystyle{ H \cdot H^T = n \cdot E_n, }[/math] где [math]\displaystyle{ E_n }[/math] — это единичная матрица размера n×n.

Матрицы Адамара находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (ортогональные блок-схемы), квантовой информатике и прочих областях.

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:

• умножение строчки или столбца на −1;
• перестановка строчек или столбцов местами.

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

Матрица Адамара называется нормализованной, если её первая строка и столбец состоят только из единиц.

Под матрицией Адамара [math]\displaystyle{ H_m }[/math] подразумевается матрица порядка [math]\displaystyle{ 2^m }[/math]

Примерами матриц Адамара различных размеров являются следующие матрицы:

[math]\displaystyle{ H_0 = (1); }[/math]

[math]\displaystyle{ H_1 = \begin{pmatrix} 1 & 1 \\1 & -1 \end{pmatrix}; }[/math]

[math]\displaystyle{ H_2 = \begin{pmatrix} 1 & 1 & 1 & 1 \\1 & -1 & 1 & -1 \\1 & 1 &- 1 & -1 \\1 & -1 & -1 & 1 \end{pmatrix}. }[/math]

Вообще, если [math]\displaystyle{ H_m }[/math] матрица Адамара порядка [math]\displaystyle{ 2^m }[/math], то матрица [math]\displaystyle{ H_{m+1} = \begin{pmatrix} H_m & H_m \\H_m & -H_m \end{pmatrix} }[/math] является матрицей Адамара порядка [math]\displaystyle{ 2^{m+1} }[/math]

Кроме того, матрицу Адамара порядка [math]\displaystyle{ 2^m }[/math] можно получить по следующей формуле [math]\displaystyle{ H^{\otimes m} = H_1 \otimes ... \otimes H_1 }[/math], где знак [math]\displaystyle{ \otimes }[/math] означает тензорное произведение.

Также существует недоказанная гипотеза Адамара, которая утверждает, что существуют матрицы Адамара порядка [math]\displaystyle{ 4k }[/math] для любого натурального [math]\displaystyle{ k }[/math], однако матрица Адамара порядка [math]\displaystyle{ 268 }[/math] до сих пор не построена, как и для ряда других порядков больше [math]\displaystyle{ 268 }[/math]. Поэтому в данной работе будут рассматриваться матрицы Адамара порядка [math]\displaystyle{ 2^m }[/math].

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

Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка [math]\displaystyle{ 2^m }[/math] будет производится поэлементно с помощью следующей формулы:

[math]\displaystyle{ (H_m)_{ij}=(-1)^ {\sum_{k}{(i \& j)_k}}, }[/math]

где [math]\displaystyle{ \& - }[/math] побитовая операция И,

[math]\displaystyle{ (i \& j)_k - }[/math] [math]\displaystyle{ k }[/math] -ый разряд в двоичном представлении числа [math]\displaystyle{ (i \& j) }[/math].

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

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

[math]\displaystyle{ (H_m)_{ij}=(-1)^ {\sum_{k}{(i \& j)_k}}. }[/math]

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

Как и в описании ядра алгоритма, основной частью алгоритма является вычисления очередного элемента матрицы Адамара с помощью следующего выражения:

[math]\displaystyle{ (-1)^ {\sum_{k}{(i \& j)_k}}. }[/math]

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

Для вычисления очередного элемента матрицы Адамара нужно выполнить следующие шаги:

1. Побитовое умножение [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math]:  [math]\displaystyle{ result = i \& j }[/math] ;

2. Нахождение числа единиц в двоичной записи числа [math]\displaystyle{ result }[/math]: [math]\displaystyle{ sum = \sum_{k}{(result)_k} }[/math];

3. Нахождение элемента матрицы Адамара: [math]\displaystyle{ (H_m)_{ij}=(-1)^{sum} }[/math].

Возможная реализация на языке C++:

int get_sign(unsigned N) {
    int i;
    for (i=0; N; N>>=1) { i+=N&1;}
    return (i&1) ? -1 : 1;
}
void adamar(int **e, int size) {
    for (unsigned int i = 0; i < size; ++i)
        for (unsigned int j = 0; j < size; ++j)
            e[i][j]=get_sign(i&j);
}

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

Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:

• [math]\displaystyle{ 2^{2m} }[/math] операций побитового умножения.

На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:

• от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
• от 0 до m или m операций сложения в зависимости от программной реализации;
• от 0 до m или m операций логического умножения в зависимости от программной реализации.

На третьем шаге для всех элементов необходимо сумарно выполнить:

• [math]\displaystyle{ 2^{2m} }[/math] операций побитового умножения;
• [math]\displaystyle{ 2^{2m} }[/math] операций сравнения с нулем.

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

• [math]\displaystyle{ (m+2)2^{2m} }[/math] операций логического умножения;
• [math]\displaystyle{ m\cdot2^{2m} }[/math] операций сложения;
• [math]\displaystyle{ m\cdot2^{2m} }[/math] операций логического сдвига на один бит;
• [math]\displaystyle{ 2^{2m} }[/math] операций сравнения с нулем.

Всего [math]\displaystyle{ (3m+3)2^{2m} }[/math] операций.

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

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

• [math]\displaystyle{ i\&j }[/math] - операция побитового умножения, где [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math] соответствующие координаты элемента [math]\displaystyle{ h_{ij} }[/math];
• NoO (number of ones) - вычисление количества единиц числа в двоичной системе. Состоит из последовательного применения операций сложения и побитового умножения;
• Sign - определение знака соответствующего элемента. Если результат предыдущего шага - чётное число, то знак положительный, иначе - отрицательный.

Рисунок 1. Граф алгоритма построения матрицы Адамара.

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

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

Высота канонической ярусно-параллельной формы равна 3. Ширина ЯПФ равна [math]\displaystyle{ 2^{2m} }[/math].

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

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

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

Выходные данные: матрица Адамара [math]\displaystyle{ H_{m} }[/math] размерностью [math]\displaystyle{ 2^m }[/math].

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

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

• Вычислительная мощность алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:

[math]\displaystyle{ \,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \approx 3m+3 \right). }[/math];

• Алгоритм построения матрицы Адамара является недетерминированным, так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2ⁿ × 2ⁿ);
• Данный алгоритм построения матрицы Адамара является несбалансированным. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы [math]\displaystyle{ n }[/math] не кратно количеству процессов [math]\displaystyle{ s }[/math], на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве [math]\displaystyle{ a=n\operatorname{mod}s }[/math].

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

Особенности реализации последовательного алгоритма

Учитывая, что рассматриваемый алгоритм строит симметричные матрицы Адамара, можно уменьшить количество вычисляемых элементов c [math]\displaystyle{ 2^{2n} }[/math] до [math]\displaystyle{ \frac{2^n+2^{2n}}{2} }[/math] путем вычисления только диагональных и наддиагональных элементов.