Участник:Nikita/Построение матрицы Адамара

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

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

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

Исходные данные - это порядок генерируемой матрицы Адамара [math]\displaystyle{ n }[/math], удовлетворяющее следующим свойствам:

• [math]\displaystyle{ n\gt 0 }[/math];

• [math]\displaystyle{ n }[/math] делится на 4;

• [math]\displaystyle{ n-1 }[/math] - простое число.

Вспомогательные данные:

• Число [math]\displaystyle{ p=n-1 }[/math];
• Вектор вычетов [math]\displaystyle{ R }[/math] (элементы [math]\displaystyle{ r_i }[/math]) размера [math]\displaystyle{ 2p }[/math]. В этом векторе индексация идет от нуля, первые [math]\displaystyle{ p }[/math] элементов образуются следующим образом:
  • ыфвыв

Вычисляемые данные:

• Матрица Адамара [math]\displaystyle{ H }[/math] (элементы [math]\displaystyle{ h_{ij} }[/math]) размера [math]\displaystyle{ n \times n }[/math].