Алговики - Вклад [ru]

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

2016-10-16T10:19:47Z

Mikhail Tsarev: /* Свойства алгоритма */

{{Assignment}}

{{algorithm
| name = Построение матрицы Адамара
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: Хоткин Кирилл 623 гр., Царев Михаил 615 гр.

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\, \approx 3m+3.</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа m, которое формирует матрицу размерности 2''m'' × 2''m'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

# [http://www.exponenta.ru/soft/matlab/potemkin/book2/chapter5/hadamard.asp MATLAB];
# [https://reference.wolfram.com/language/ref/HadamardMatrix.html WOLFRAM];
# [http://pydoc.net/Python/rogues/0.3.0/rogues.matrices.hadamard/ Python];
# [http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_97.html Octave];

Стоит отметить, что во многих вычислительных пакетах встроена операция тензорного произведения матриц, которая позволяет строить матрицу Адамара по определению. Этот факт позволяет использовать матрицу Адамара в этих вычислительных пакетах:
# [https://ru.wikipedia.org/wiki/Maple MAPLE];
# [https://ru.wikipedia.org/wiki/Mathcad MATCATH];

== Литература ==

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

2016-10-15T20:58:38Z

Mikhail Tsarev: /* Существующие реализации алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\, \approx 3m+3.</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

# [http://www.exponenta.ru/soft/matlab/potemkin/book2/chapter5/hadamard.asp MATLAB];
# [https://reference.wolfram.com/language/ref/HadamardMatrix.html WOLFRAM];
# [http://pydoc.net/Python/rogues/0.3.0/rogues.matrices.hadamard/ Python];
# [http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_97.html Octave];

Стоит отметить, что во многих вычислительных пакетах встроена операция тензорного произведения матриц, которая позволяет строить матрицу Адамара по определению. Этот факт позволяет использовать матрицу Адамара в этих вычислительных пакетах:
# [https://ru.wikipedia.org/wiki/Maple MAPLE];
# [https://ru.wikipedia.org/wiki/Mathcad MATCATH];

== Литература ==

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

2016-10-15T20:57:44Z

Mikhail Tsarev: /* Свойства алгоритма */

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

2016-10-15T20:57:14Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \approx 3m+3 \right).</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:56:52Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \approx3m+3).</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:54:12Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \sim (3m+3),\,m\to+\infty \right).</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:53:59Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \sim [3m+3],\,m\to+\infty \right).</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:53:21Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

=== Свойства алгоритма ===
* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:
:<math>\,\frac{(3m+3)2^{2m}}{1+2^{2m}}\left( \sim [\frac{n}{4}],\,n\to+\infty \right).</math>;
* Алгоритм построения матрицы Адамара является ''недетерминированным'', так как число операций меняется в зависимости от входных данных (числа n, которое формирует матрицу размерности 2''n'' × 2''n'');
* Данный алгоритм построения матрицы Адамара является ''несбалансированным''. Так как каждый элемент матрицы может обрабатываться независимо от других, вычисление элементов можно распределить по процессам. В случае, когда количество элементов матрицы <math>n</math> не кратно количеству процессов <math>s</math>, на некоторые процессы ложится дополнительная задача вычисления элементов матрицы в количестве <math>a=n\operatorname{mod}s</math>.

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:49:05Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

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

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

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

2016-10-15T20:48:38Z

Mikhail Tsarev: /* Свойства алгоритма */

еееее
Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(m2^{2m})</math>
| pf_height = <math>O(1)</math>
| pf_width = <math>O(2^{2n})</math>
| input_data = <math>1</math>
| output_data = <math>2^{2n}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
* умножение строчки или столбца на −1;
* перестановка строчек или столбцов местами.

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

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

Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>

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

<math>H_0 = (1);</math>

<math>H_1 =
\begin{pmatrix} 1 & 1
\\1 & -1
\end{pmatrix};
</math>

<math>H_2 =
\begin{pmatrix} 1 & 1 & 1 & 1
\\1 & -1 & 1 & -1
\\1 & 1 &- 1 & -1
\\1 & -1 & -1 & 1
\end{pmatrix}.
</math>

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

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

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

=== Математическое описание алгоритма ===
Описанные ранее способы построения матрицы Адамара не являются оптимальными, поэтому вычисление матрицы Адамара порядка <math>2^m</math> будет производится поэлементно с помощью следующей формулы:

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

где <math>\& - </math> побитовая операция И,

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

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

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

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

<math>(-1)^ {\sum_{k}{(i \& j)_k}}.</math>

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

1. Побитовое умножение <math>i</math> и <math>j</math>: <math>result = i \& j </math> ;

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

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

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

<source lang="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);
}
</source>

=== Последовательная сложность алгоритма ===
Для выполнения первого шага алгоритма для всех элементов матрицы Адамара необходимо суммарно выполнить:
* <math>2^{2m}</math> операций побитового умножения.
На втором шаге алгоритма необходимо выполнить для каждого элемента матрицы Адамара:
* от 0 до m или m логических сдвигов на один бит в зависимости от программной реализации;
* от 0 до m или m операций сложения в зависимости от программной реализации;
* от 0 до m или m операций логического умножения в зависимости от программной реализации.
На третьем шаге для всех элементов необходимо сумарно выполнить:
* <math>2^{2m}</math> операций побитового умножения;
* <math>2^{2m}</math> операций сравнения с нулем.

Взяв в расчет не самую лучшую программную реализацию второго шага, всего потребуется выполнение следующего количества операций:
* <math>(m+2)2^{2m}</math> операций логического умножения;
* <math>m\cdot2^{2m}</math> операций сложения;
* <math>m\cdot2^{2m}</math> операций логического сдвига на один бит;
* <math>2^{2m}</math> операций сравнения с нулем.
Всего <math>(3m+3)2^{2m}</math> операций.

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

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

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

[[File:Hadamar matrix.png|thumb|center|1400px|Рисунок 1. Граф алгоритма построения матрицы Адамара.]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные''': m - размерность матрицы <math>H_m</math>.

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

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

'''Объём выходных данных''': <math>2^{2m}</math>.

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

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

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

=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

Файл:Hadamar graph.png

2016-10-15T20:01:34Z

Mikhail Tsarev:

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

2016-10-15T15:59:10Z

Mikhail Tsarev:

Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
{{algorithm
| name = Сюда тоже запилим
| serial_complexity = <math>O(n^3)</math>
| pf_height = <math>O(n)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>\frac{n (n + 1)}{2}</math>
| output_data = <math>\frac{n (n + 1)}{2}</math>
}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])

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

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

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

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

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

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

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

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

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

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

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

=== Свойства алгоритма ===
==Программная реализация алгоритма==
===Особенности реализации последовательного алгоритма===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

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

== Литература ==

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

2016-10-15T15:31:42Z

Mikhail Tsarev:

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