10.6. Методы синтеза алгоритмов БПХ-m

Для многомерного дискретного преобразования Хартли (ДПХ-т) также возможно построение быстрых алгоритмов (БПХ-m). В данном разделе рассматривается метод ПСА в построении БПХ-m, гнездовые алгоритмы и тензорные алгоритмы БПХ-.

Как было показано в гл. 2, существуют две формы многомерного сепарабельное и несепарабельное ДПХ- Далее показано, что обе формы в конечном счете, представимы в виде коронекеровского преобразования матриц одномерных ДПХ

где матрица имеет простую конструкцию (относительно ядра преобразования) и определяется выражениями (2.62), (2.64).

Таким образом, основой построения алгоритмов БПХ-m являются методы факторизации ядра

Для метода ПСА при построении БПХ-m мы получаем оценки, аналогичные (10.2) (с учетом замены модулей на причем аналогичной является и задача транспонирования матриц промежуточных данных. Приведем лишь конкретные оценки вычислительной эффективности для

ПСА БПХ-2 размерностью (считается, что ):

1. БПХ-2 по основанию 2

или

(оценки и а получаются при использовании факторизации типа (9.10));

2. БПХ-2 по основанию 4

или

(в оценке а учитывается разложение (9.20)).

3. БПХ-2 с расщепленным основанием

или

Рассмотрим теперь возможности построения гнездовых алгоритмов для БПХ-2.

Для построения таких алгоритмов БПХ-2 можно непосредственно использовать матричную модель алгоритма одномерного БПХ, например по основанию 2. Тогда согласно (9.6)

где

Согласно (10.51) исходное выражение для гнездового алгоритма БПХ-2 имеет вид

Умножение матриц на вектор промежуточных данных можно выполнить методом ПСА. Однако матрицу

целесообразно преобразовать к форме, имеющей меньшее число весовых коэффициентов. Рассмотрим этот вопрос подробнее. Умножение на вектор промежуточных данных эквивалентно матричному выражению вида

Представим в виде клеточной матрицы, состоящей из подматриц

Тогда матричное выражение (10.54) может быть разбито на подматрицы

Матрицы (10.55) с учетом (10.52) могут быть представлены в виде

где

Далее преобразуем матрицу

Для этого представим в виде

где матрица перестановки, определяемая правилом

Тогда

Отсюда

где

Обозначим через перестановку вида

где — матрица "идеальной" перестановки (см. гл. 1).

Тогда где

Преобразуем в виде где

Тогда

причем циркулярные матрицы.

Каждая циркулянтная матрица может быть факторизована в виде

отсюда

где

Умножение на каждую матрицу требует восьми умножений и 12 сложений, следовательно, обшее число арифметических операций в (10.57) равно умножений и сложений. Число нетривиальных арифметических операций определяется с учетом сравнений

тогда умножение на требует четыре умножения и 10 сложений, отсюда

Таким образом, вычислительная сложность (10.56) равна

Из полученных оценок легко определить вычислительную сложность на этапе вычислений гнездового алгоритма (10.53)

Окончательно

Сравнение полученных оценок с оценками для алгоритма БПХ-2, определенного через ПСА (по основанию 2), показывает, что при незначительном (порядка 8%) увеличении числа сложений гнездовой алгоритм БПХ-2 требует на 25% меньше умножений.

Число умножений в гнездовом алгоритме БПХ-2 можно еще уменьшить, если применить для метод факторизации косоциркулянтных матриц, т.е.

где

При такой факторизации получаем следующие оценки вычислительной сложности для гнездового алгоритма: