В. Матричное описание преобразований. Факторизация матриц.

Матричные преобразования по-разному описываются в различных книгах и статьях. Далее приводятся формулы преобразований, указанные в работах [124, 127]. Будем дальше пользоваться принятым в этих работах обозначением матрицы М.

Предварительно вернемся еще раз к источникам, о которых было сказано в начале раздела А. На формирование рассматриваемого в дальнейшем общего метода выполнения быстрых дискретных ортогональных преобразований оказало влияние опубликование статьи [165]. Однако основы современной теории быстрых матричных ортогональных преобразований были изложены лишь позднее в книге [100], оказавшей большое влияние на все последующие работы, проводившиеся в этом направлении. Характеризуя обобщенный метод выполнения матричных преобразований, авторы книги [100] пишут следующее. "Матрицы, являющиеся кронекеровским произведением нескольких одинаковых матриц, обладают одним важным свойством: их можно представить в виде обычного произведения нескольких матриц, т.е. факторизовать или разложить на множители". Далее они пишут о том, что это свойство было сформулировано в указанной нами выше статье [165]. Существенное развитие обобщенный метод выполнения быстрых дискретных ортогональных преобразований получил в упоминавшихся работах [22, 124, 126] и в других работах, на которые будут дальше сделаны ссылки в нашей книге.

После сделанных замечаний, в ходе которых было пояснено и понятие факторизации, укажем, как матрицы преобразований приводятся к простейшим. Согласно [124, 126] факторизация матриц преобразований Фурье, Уолша, Хаара и других ортогональных преобразований сводится к выполнению в различных случаях операций со следующими элементарными матрицами:

При факторизации некоторых матриц используется величина равная при и равная 1 при Используются также преобразование перестановки по двоичной инверсии и преобразование перестановки из кода Грея в прямой двоичный код Рекуррентные формулы

вычисления этих преобразований следующего вида:

и

Приведены формулы для матриц размерности

Факторизация матриц производится на основе применения указанных в [124, 127] теорем, формулировка которых поясняется нами с помощью табл. 4.13. Для последней приняты следующие обозначения: исходная матрица; для подматриц и других в нижнем индексе указана размерность подматрицы, в верхнем индексе ее номер.

В верхней части таблицы в разделах с 1 по 4 приведена формулировка четырех теорем: если имеет место то, что записано в соответствующем разделе слева, то заданная матрица может быть преобразована к виду, представленному в правой части данного раздела таблицы. Например, первая из этих теорем формулируется так: если матрица может быть разделена горизонтальной чертой, как указано в левой части раздела 1, на две подгруппы, каждая из которых является обыкновенным произведением двух матриц, то выражение заданной матрицы может быть приведено к виду, показанному в разделе 1 справа. Теорема доказывается просто: представляя в полученном выражении кронекеровскую сумму в виде матрицы, рассматривая здесь второй множитель как обычный вектор-столбец, определяя их произведение по правилам обычного умножения матриц, приходим к исходному выражению Аналогичным образом путем прямой проверки доказываются и другие из этих теорем. В выражениях, полученных в разделах единичная матрица размерности единичная матрица размерности В выражении, полученном в разделе Как отмечено в книге [ 124], теорема 3 была первоначально доказана для квадратных матриц в работе [165].

При записи условий основных теорем нами были использованы материалы книги [124]. Автором ее в дальнейшем формулировка этих теорем была расширена. В работе [127] они указаны в таком виде, как представлено в нижней части табл. 4.13. Если раньше рассматривалось разделение исходной матрицы горизонтальной чертой на две части, то здесь введены в рассмотрение в общем виде поэтажно-кронекеровские матрицы. Соответственно с этим теорема 1 сформулирована так, как указано в разделе 1 нижней части таблицы. Следствием этой теоремы является равенство где вектор-столбец, состоящий из единиц (здесь использовано обозначение отличающееся от вышеприведенных). Другие три теоремы, отличающиеся по нумерации от ранее указанных, приведены в разделах 2,3 и 4 нижней части таблицы. Для раздела 4 принято следующее обозначение: вектор-строка размерности

Таблица 4.13 (см. скан)

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

быстрых преобразований, для которых здесь приняты обозначения

Преобразование Уолша -точечной последовательности

Быстрое преобразование Хаара

Полученная матрица БПХ порядка следующим образом охарактеризована в работе [127]. Она, "представлена в виде произведения диагональной матрицы и слабозаполненных матриц с числом ненулевых элементов в каждой строке не более двух".

Для реализации прямого и обратного БПФ рекомендуется использование соответственно следующих матричных преобразований:

и

Путем матричных преобразований легко осуществляется переход от одних упорядочений преобразования Уолша к другим его упорядочениям. Это иллюстрируется следующими формулами, приведенными в работе [127], где для преобразований Уолша, упорядоченных по Уолшу, Пэли и Адамару, приняты соответственно обозначения

Имеется аналогия и между факторизованными представлениями матриц и [127]. Общность результатов матричной реализации соответствующих алгоритмов не обнаруживается непосредственно при сравнении отвечающих им формул. В большей степени видно, насколько

сходны эти алгоритмы, из проведенного в § 3 сравнения графа БПУ с таким же по виду графом БПФ. Однако методика описанных выше матричных преобразований является единой, в равной мере она применима при выполнении различных быстрых дискретных ортогональных преобразований.

Указанная общая методика преобразований находит сейчас все большее применение. Вместе с тем в некоторых случаях оказывается целесообразным использование матриц особого вида. Ниже приводятся сведения о матричных методах преобразований, примененных в сочетании с методами теории чисел и полиномов для описания и оценки упоминавшегося в гл. III алгоритма Винограда. В работе Зохара (см. источник [49] в списке литературы к главам I, II, III) показано, как основные понятия теории чисел, такие как упоминавшиеся у нас в гл. III понятия сравнения чисел по модулю, первообразных корней и другие, а также китайская теорема об остатках в полиномиальном ее варианте используются для раскрытия особенностей алгоритма Винограда вместе с некоторыми не упоминавшимися нами ранее понятиями теории матриц.

В данном случае рассматриваются матрицы специального вида, называемые матрицами Ханкеля. Отличительной особенностью их является то, что в матрице Ханкеля одинаковы все элементы, находящиеся на любой диагонали, идущей вниз справа налево. Для определения такой матрицы достаточно указать элементы первой ее строки и последнего ее столбца. Если элементы последнего столбца образуются перестановкой элементов первой строки, то для задания матрицы достаточно указать лишь элементы первой ее строки. Для этой матрицы, называемой лево-циркулянтной (ЛЦ-матрицей), каждая следующая строка образуется из предшествующей ее строки путем кругового сдвига последней влево, при котором элемент, появляющийся слева за пределами исходной строки, переносится в правую часть вновь образуемой строки. Линейное преобразование, представляемое ЛЦ-матрицей, называют лево-циркулянтным преобразованием (ЛЦП). Если матрицы не являются в целом ЛЦ-матрицами, но содержат ЛЦ-подматрицы, то для них принято название квазилево-циркулянтных матриц (КЛЦ). В упоминавшейся работе Зохара показано, как для раскрытия сущности алгоритма Винограда и при анализе его особенностей применяется ЛЦП вместе с преобразованиями, основанными на использовании выводов теории чисел и полиномов. При матричных преобразованиях здесь производятся действия с КЛЦ.