5.2. Гнездовой метод факторизации

Пусть, как и ранее, дана форма представления (5.1), где каждое имеет каноническое разложение (4.13), тогда, используя свойство 5 кронекеровского произведения из разд. 1.2, непосредственно получаем

Применяя к (5.9) теорему факторизации, окончательно получаем

Такой метод факторизации называется гнездовым Nesting. При такой факторизации в (5.10) происходит группировка весовых коэффициентов в одной диагональной матрице . Гнездовой алгоритм для ДПФ был впервые предложен Виноградом

[8] в форме (5.9) (WFTA - Winograd Fourier Transform Algorithm)

где матрицы перестановок по правилам "китайского" и "руританского" соответствий.

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

Представление (5.12) классифицируется как многомерный гнездовой алгоритм для простых модулей Случай многомерных гнездовых алгоритмов для сложносоставных модулей будет рассмотрен в гл. 10.

Наиболее подробно методы построения простых модулей а также гнездовых конструкций типа (5.11) приведены в [10, 11]. В [12] рассмотрен модифицированный вариант алгоритма Винограда, называемый вертикально-гнездовым алгоритмом Данный алгоритм основан на представлении (4.18), на основе которого получаем гнездовой алгоритм вида:

где

Рассмотрим основные параметры вычислительной эффективности гнездовых алгоритмов. Пусть факторизуется согласно (5.11) (с учетом дальнейшей факторизации (5.10)), тогда число вещественных умножений и сложений соответственно равно

где общее число вещественных операций умножений и сложений в модулях число вещественных тривиальных умножений в модулях

Из (5.14) следует, что число умножений не зависит от порядка расположения сомножителей Однако в отличие от алгоритмов типа АПМ число сложений для гнездовых алгоритмов зависит от порядка следования и поэтому для данного класса алгоритмов возможна оптимизация по числу сложений. В [13] авторы использовали для этого метод динамического программирования. Рассмотрим согласно [13] пример построения исходные модули которого разбиты на пять частей

Рис. 5.2. Модуль

Рис. 5.3. Модуль

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

В данном примере использование вертикально-гнездового способа вычислений позволило на 10% уменьшить суммарное число арифметических операций. Не исключено, что в более сложных примерах существуют другие, отличающиеся от оптимальные варианты чередования областей, однако конкретные примеры в литературе не приведены.

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

Объем оперативной памяти для хранения промежуточных данных будет

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

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

меняться при переходе вычислений от блока к блоку где и станет максимальным после умножения на Далее, в процессе прохождения данных через блок матриц С объем требуемого ОЗУ будет уменьшаться в конечном счете до комплексных слов, отсюда максимальный объем ОЗУ равен комплексных слов или вещественных слов.