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

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

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

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

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

• [math]n\gt 0[/math];

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

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

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

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

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

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