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

Материал из Алговики
< Участник:Бугаков Юрий
Версия от 01:40, 13 октября 2016; Бугаков Юрий (обсуждение | вклад) (Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Важную роль в алгебре…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску

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

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

Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века одним из крупнейших французских математиков Жаком Адамаром (1865-1963).

Квадратная матрица Н порядка n с элементами ±1 называется матрицей Адамара, если выполняется условие

[math] H_n\,H_n^T = n\,E_n [/math]

Матрица Hm эта матрица размера 2m × 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2m real numbers xn into 2m real numbers Xk. The Hadamard transform can be defined in two ways: recursively, or by using the binary (base-2) representation of the indices n and k.

For m > 1, we can also define Hm by:

[math]H_m = H_{1} \otimes H_{m-1}[/math]

where [math] \otimes [/math] represents the Kronecker product. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1.

Equivalently, we can define the Hadamard matrix by its (k, n)-th entry by writing

[math]k = \sum^{m-1}_{i=0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0[/math]

and

[math]n = \sum^{m-1}_{i=0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \cdots + n_1 2 + n_0[/math]

where the kj and nj are the binary digits (0 or 1) of k and n, respectively. Note that for the element in the top left corner, we define: [math]k = n = 0[/math]. In this case, we have:

[math]\left( H_m \right)_{k,n} = \frac{1}{2^\frac{m}{2}} (-1)^{\sum_j k_j n_j}[/math]

This is exactly the multidimensional [math]\scriptstyle 2 \,\times\, 2 \,\times\, \cdots \,\times\, 2 \,\times\, 2[/math] DFT, normalized to be unitary, if the inputs and outputs are regarded as multidimensional arrays indexed by the nj and kj, respectively.

Вот несколько примеров матриц Адамара:

[math]\begin{align} H_0 = &+1\\ H_1 = \frac{1}{\sqrt2} &\begin{pmatrix}\begin{array}{rr} 1 & 1\\ 1 & -1 \end{array}\end{pmatrix} \end{align}[/math]

(This H1 is precisely the size-2 DFT. It can also be regarded as the Fourier transform on the two-element additive group of Z/(2).)

[math]\begin{align} H_2 = \frac{1}{2} &\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}\\ H_3 = \frac{1}{2^{\frac{3}{2}}} &\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}\\ (H_n)_{i,j} = \frac{1}{2^{\frac{n}{2}}} &(-1)^{i \cdot j} \end{align}[/math]

1.1.1 Симметричность и положительная определённость матрицы

Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций в сравнении с, например, разложением по методу Гаусса. При этом альтернативное (без вычисления квадратных корней) LU-разложение, использующее симметрию матрицы, всё же несколько быстрее метода Холецкого (не использует извлечение квадратных корней), но требует хранения всей матрицы. Благодаря тому, что разлагаемая матрица не только симметрична, но и положительно определена, её LU-разложения, в том числе и разложение методом Холецкого, имеют наименьшее эквивалентное возмущение из всех известных разложений матриц.

1.1.2 Режим накопления

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

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

Исходные данные: положительно определённая симметрическая матрица [math]A[/math] (элементы [math]a_{ij}[/math]).

Вычисляемые данные: нижняя треугольная матрица [math]L[/math] (элементы [math]l_{ij}[/math]).

Формулы метода:

[math] \begin{align} l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align} [/math]

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление [math]\frac{1}{l_{ii}}[/math] и затем умножение на него всех (видоизменённых) [math]a_{ji}[/math] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

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

Вычислительное ядро последовательной версии метода Холецкого можно составить из множественных (всего их [math]\frac{n (n - 1)}{2}[/math]) вычислений скалярных произведений строк матрицы:

[math]\sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]

в режиме накопления или без него, в зависимости от требований задачи. Во многих последовательных реализациях упомянутый способ представления не используется. Дело в том, что в них вычисление сумм типа

[math]a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]

в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений

[math]a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]

в режиме накопления или без него.

Тем не менее, в популярных зарубежных реализациях точечного метода Холецкого, в частности, в библиотеках LINPACK и LAPACK, основанных на BLAS, используются именно вычисления скалярных произведений в виде вызова соответствующих подпрограмм BLAS (конкретно — функции SDOT). На последовательном уровне это влечёт за собой дополнительную операцию суммирования на каждый из [math]\frac{n (n + 1)}{2}[/math] вычисляемый элемент матрицы [math]L[/math] и некоторое замедление работы программы (о других следствиях рассказано ниже в разделе «Существующие реализации алгоритма»). Поэтому в данных вариантах ядром метода Холецкого будут вычисления этих скалярных произведений.

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

Как записано и в описании ядра алгоритма, основную часть метода составляют множественные (всего [math]\frac{n (n - 1)}{2}[/math]) вычисления сумм

[math]a_{ji}-\sum_{p=1}^{i-1}l_{ip} l_{jp}[/math]

в режиме накопления или без него.

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

Последовательность исполнения метода следующая:

1. [math]l_{11}= \sqrt{a_{11}}[/math]

2. [math]l_{j1}= \frac{a_{j1}}{l_{11}}[/math] (при [math]j[/math] от [math]2[/math] до [math]n[/math]).

Далее для всех [math]i[/math] от [math]2[/math] до [math]n[/math] по нарастанию выполняются

3. [math]l_{ii} = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}[/math] и

4. (кроме [math]i = n[/math]): [math]l_{ji} = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}[/math] (для всех [math]j[/math] от [math]i + 1[/math] до [math]n[/math]).

После этого (если [math]i \lt n[/math]) происходит переход к шагу 3 с бо́льшим [math]i[/math].

Особо отметим, что вычисления сумм вида [math]a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math] в обеих формулах производят в режиме накопления вычитанием из [math]a_{ji}[/math] произведений [math]l_{ip} l_{jp}[/math] для [math]p[/math] от [math]1[/math] до [math]i - 1[/math], c нарастанием [math]p[/math].

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

Для разложения матрицы порядка n методом Холецкого в последовательном (наиболее быстром) варианте требуется:

  • [math]n[/math] вычислений квадратного корня,
  • [math]\frac{n(n-1)}{2}[/math] делений,
  • [math]\frac{n^3-n}{6}[/math] сложений (вычитаний),
  • [math]\frac{n^3-n}{6}[/math] умножений.

Умножения и сложения (вычитания) составляют основную часть алгоритма.

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения метода Холецкого.

При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам с кубической сложностью.

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

Опишем граф алгоритма[1][2][3] как аналитически, так и в виде рисунка.

Граф алгоритма состоит из трёх групп вершин, расположенных в целочисленных узлах трёх областей разной размерности.

Первая группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию SQRT. Единственная координата каждой из вершин [math]i[/math] меняется в диапазоне от [math]1[/math] до [math]n[/math], принимая все целочисленные значения.

Аргумент этой функции

  • при [math]i = 1[/math] — элемент входных данных, а именно [math]a_{11}[/math];
  • при [math]i \gt 1[/math] — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами [math]i - 1[/math], [math]i[/math], [math]i - 1[/math].

Результат срабатывания операции является выходным данным [math]l_{ii}[/math].

Вторая группа вершин расположена в двумерной области, соответствующая ей операция [math]a / b[/math]. Естественно введённые координаты области таковы:

  • [math]i[/math] — меняется в диапазоне от [math]1[/math] до [math]n-1[/math], принимая все целочисленные значения;
  • [math]j[/math] — меняется в диапазоне от [math]i+1[/math] до [math]n[/math], принимая все целочисленные значения.

Аргументы операции следующие:

  • [math]a[/math]:
    • при [math]i = 1[/math] — элементы входных данных, а именно [math]a_{j1}[/math];
    • при [math]i \gt 1[/math] — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами [math]i - 1, j, i - 1[/math];
  • [math]b[/math] — результат срабатывания операции, соответствующей вершине из первой группы, с координатой [math]i[/math].

Результат срабатывания операции является выходным данным [math]l_{ji}[/math].

Третья группа вершин расположена в трёхмерной области, соответствующая ей операция [math]a - b * c[/math]. Естественно введённые координаты области таковы:

  • [math]i[/math] — меняется в диапазоне от [math]2[/math] до [math]n[/math], принимая все целочисленные значения;
  • [math]j[/math] — меняется в диапазоне от [math]i[/math] до [math]n[/math], принимая все целочисленные значения;
  • [math]p[/math] — меняется в диапазоне от [math]1[/math] до [math]i - 1[/math], принимая все целочисленные значения.

Аргументы операции следующие:

  • [math]a[/math]:
    • при [math]p = 1[/math] элемент входных данных [math]a_{ji}[/math];
    • при [math]p \gt 1[/math] — результат срабатывания операции, соответствующей вершине из третьей группы, с координатами [math]i, j, p - 1[/math];
  • [math]b[/math] — результат срабатывания операции, соответствующей вершине из второй группы, с координатами [math]p, i[/math];
  • [math]c[/math] — результат срабатывания операции, соответствующей вершине из второй группы, с координатами [math]p, j[/math];

Результат срабатывания операции является промежуточным данным алгоритма.

Описанный граф можно посмотреть на рис.1 и рис.2, выполненных для случая [math]n = 4[/math]. Здесь вершины первой группы обозначены жёлтым цветом и буквосочетанием sq, вершины второй — зелёным цветом и знаком деления, третьей — красным цветом и буквой f. Вершины, соответствующие операциям, производящим выходные данные алгоритма, выполнены более крупно. Дублирующие друг друга дуги даны как одна. На рис.1 показан граф алгоритма согласно классическому определению , на рис.2 к графу алгоритма добавлены вершины , соответствующие входным (обозначены синим цветом) и выходным (обозначены розовым цветом) данным.

Рисунок 1. Граф алгоритма без отображения входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление.
Рисунок 2. Граф алгоритма с отображением входных и выходных данных. SQ - вычисление квадратного корня, F - операция a-bc, Div - деление, In - входные данные, Out - результаты.

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

Для разложения матрицы порядка [math]n[/math] методом Холецкого в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • [math]n[/math] ярусов с вычислением квадратного корня (единичные вычисления в каждом из ярусов),
  • [math]n - 1[/math] ярус делений (в каждом из ярусов линейное количество делений, в зависимости от яруса — от [math]1[/math] до [math]n - 1[/math]),
  • по [math]n - 1[/math] ярусов умножений и сложений/вычитаний (в каждом из ярусов — квадратичное количество операций, от [math]1[/math] до [math]\frac{n^2 - n}{2}[/math].

Таким образом, в параллельном варианте, в отличие от последовательного, вычисления квадратных корней и делений будут определять довольно значительную долю требуемого времени. При реализации на конкретных архитектурах наличие в отдельных ярусах ЯПФ отдельных вычислений квадратных корней может породить и другие проблемы. Например, при реализации на ПЛИСах остальные вычисления (деления и тем более умножения и сложения/вычитания) могут быть конвейеризованы, что даёт экономию и по ресурсам на программируемых платах; вычисления же квадратных корней из-за их изолированности приведут к занятию ресурсов на платах, которые будут простаивать большую часть времени. Таким образом, общая экономия в 2 раза, из-за которой метод Холецкого предпочитают в случае симметричных задач тому же методу Гаусса, в параллельном случае уже имеет место вовсе не по всем ресурсам, и главное - не по требуемому времени.

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения метода Холецкого в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает увеличение требуемой памяти почти в 2 раза.

При классификации по высоте ЯПФ, таким образом, метод Холецкого относится к алгоритмам со сложностью [math]O(n)[/math]. При классификации по ширине ЯПФ его сложность будет [math]O(n^2)[/math].

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

Входные данные: плотная матрица [math]A[/math] (элементы [math]a_{ij}[/math]). Дополнительные ограничения:

  • [math]A[/math] – симметрическая матрица, т. е. [math]a_{ij}= a_{ji}, i, j = 1, \ldots, n[/math].
  • [math]A[/math] – положительно определённая матрица, т. е. для любых ненулевых векторов [math]\vec{x}[/math] выполняется [math]\vec{x}^T A \vec{x} \gt 0[/math].

Объём входных данных: [math]\frac{n (n + 1)}{2}[/math] (в силу симметричности достаточно хранить только диагональ и над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. Например, в библиотеке, реализованной в НИВЦ МГУ, матрица A хранилась в одномерном массиве длины [math]\frac{n (n + 1)}{2}[/math] по строкам своего нижнего треугольника.

Выходные данные: нижняя треугольная матрица [math]L[/math] (элементы [math]l_{ij}[/math]).

Объём выходных данных: [math]\frac{n (n + 1)}{2}[/math] (в силу треугольности достаточно хранить только ненулевые элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. Например, в той же библиотеке, созданной в НИВЦ МГУ, матрица [math]L[/math] хранилась в одномерном массиве длины [math]\frac{n (n + 1)}{2}[/math] по строкам своей нижней части.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является квадратичным (отношение кубической к линейной).

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь линейна.

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

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

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

Эквивалентное возмущение [math]M[/math] у метода Холецкого всего вдвое больше, чем возмущение [math]\delta A[/math], вносимое в матрицу при вводе чисел в компьютер: [math] ||M||_{E} \leq 2||\delta A||_{E} [/math]

Это явление обусловлено положительной определённостью матрицы. Среди всех используемых разложений матриц это наименьшее из эквивалентных возмущений.

  1. ↑ Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.
  2. ↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.
  3. ↑ Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Бугаков_Юрий/Построение_матрицы_Адамара_произвольной_размерности&oldid=6229