вещественных умножений М(п)

Число Число

Число вещесвенньх веществени

вещественных умножений слота ний

сложений на точку на точку

А(п) М(п)/п А (п)/п

2 II

840 1008 1260 2520

950 1280 1056 2280 3200 3648 7680 10032 12160 29184

1120 1450 2100 30% 5470 7958 10176 14748 20420 26304 52788 71265 95744 241680

5.28 6.10 4.40 6.33 7.М 7.24 9.14 9.95 9.65 11.58

m 22 И 50 11.3.1 13.9 14.03 18.75 18 67 20 14 25 00 25 80 30 39 37 90 42.40 40.97 48.62 52.19 62,84 70,70 75,99 95 90

Рис. 7.4. Характеристики алгоритма Агарвала-Кули вычисления свертки.

Двойное суммирование по k и k эквивалентно одинарному суммированию по k, так как затрагивает одни и те же члены. Определим двумерные переменные, которые назовем также d, g и s, задавая их равенствами

п--1 n--\

l, r = 2j S g((r-ft)). (( -ft ))** , k=0 k=u

где первые и вторые индексы вычисляются соответственно по модулю л и л . Теперь это двумерная циклическая свертка. Тем не менее, мы пока не получили никакого уменьшения сложности вычислений. Для каждой пары индексов (i, Г) каждое число di-.t- на что-то умножается, так что пока полное число умножений равно (лл ).

Для того, чтобы сделать алгоритм эффективным, надо воспользоваться развитыми в предыдущем разделе методами быстрого

вычисления двумерной свертки. Алгоритм Агарвала-Кули вычисления свертки состоит в переходе от одномерных , векторов к двумерным таблицам, в применении быстрых алгоритмов двумерной свертки и в обратном переходе от двумерной таблицы к одномерному выходному вектору.

Характеристики п-точечного алгоритма Агарвала-Кули подытожены в таблице на рис. 7.4. Полное число сложений и умножений определяется гнездовым методом построения алгоритмов двумерной циклической свертки из эффективных одномерных алгоритмов составляющих длин л и л по формулам

А (л) = пА (л ) + М (л ) А (л),

М{п) = М (л) М (л ).

Из этих формул видно, что число умножений в малых алгоритмах играет существенно более важную роль, чем число сложений. Например, предположим, что алгоритм 504-точечной циклической свертки строится из 7-, 9- и 8-точечных циклических сверток с

М (7) = 16, А (7) = 70,

М (9) = 19, А (9) = 74,

м (8) = 14, /1 (8) = 46 или М (8) = 12, А (8) = 72.

Может показаться, что алгоритм 8-точечной циклической свертки с 14 умножениями лучше, так как он содержит всего на два умножения больше, но зато на 26 сложений меньше. Однако включение его в алгоритм 504-точечной свертки приводит к удивительным результатам;

М (504) = 4256, М (504) = 3648,

А (504) = 28 240 А (504) = 26 304.

Таким образом, использование в 504-точечном алгоритме 8-точечного алгоритма с 12 умножениями приводит к уменьшению и числа умножений, и числа сложений.

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

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

S = CGAd.

Есть еще одна последняя деталь, о которой надо позаботиться: компоненты векторов s и d выписаны не в своем естественном порядке. Сначала они выписывались в двумерную матрицу вдоль главной диагонали, а затем в виде стека столбцов (или строк). Для того, чтобы вернуть компоненты на их естественное место, надо переставить столбцы матрицы А и строки матрицы С.

В качестве примера построим алгоритм 12-точечной циклической свертки. Воспользуемся следующим 3-точечным алгоритмом циклической свертки:

с-с; о;

0 -1

1 -1

1 -1

1-1 о

-1 -1 1

1 -1

-1 -1

-1 о

о -1

Сначала выпишем 12 коэффициентов фильтра в виде двумерной (3x4)-таблицы, располагая их вдоль главной диагонали, и вытягивая затем их в стек по столбцам:

Тогда диагональная (20х20)-матрица G в терминах кронекеровского произведения записывается равенством

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

S = ((С X С) (G X О ) (А X А )) d.

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

S = ((С X С) (С X G )(A X A-d,

и следующим алгоритмом 4-точечной циклической свертки

Ту же самую конструкцию надо применить к 12 компонентам входного вектора данных; выпишем кронекеровскую матрицу А ХА полностью:

о -(i

Наконец, перестановка столбцов дает

о -о -

о -

о -i -1

0-1 о

о Р -1 0-1-1

Это полностью определяет вычисление D = Ad. Аналогичные рассуждения приводят к построению матрицы С, и, в итоге к стандартной матричной форме s = CGAd алгоритма вычисления 12-точечнои циклической свертки. В такой форме алгоритма все операции перестановки компонент скрыты в матрицах пред. сложений и постсложений.

7.3. Алгоритмы разложения

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

S (X, у)= g (х,) d (X, у) (mod X - - 1) (mod у - 1) мы объединяли алгоритмы для вычислений

s(x)=g (х) d (х) (mod х - 1) и s ((/) = g {у) d (у) (mod у - I).

В более общей формулировке, для построения алгоритма вычисления

S (X, у) = g (х, у) d (х, у) (mod р (х)) (mod q (у)),

где р {х) и q (у) представляют собой многочлены степеней п и п соответственно, мы комбинировали алгоритмы для решения двух простых одномерных задач

S (х) = g (х) d (х) (mod р (х)) и s (у) = g (у) d (у) (mod q (</)).

Ести каждый из подалгоритмов содержит соответственно М (п) и М (я ) умножений, то полученный таким методом алгоритм решения двумерной задачи содержит М (я) М (я ) умножений.

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

р(х)=р (х)р >(х), где многочлены р (х) и р< (х) взаимно просты. Вычисление произведения многочленов

(х, у) = g (х, у) d (х, у) (mod р (х)) (mod q (у)) можно разбить на вычисления произведений

s°4x. y) = g°4x, yjdHx. У) (modp°>(x))(modq(y))

s (x, ) = g >( l/)d 4x. у) (modp (x)) (mod<?(s,)). Китайская теорема об остатках позволяет восстановить произведение из этих фрагментов. Если q (у) = q< (у) q (у), то можно произвести факторизацию и по переменной у. Обе эти возможности позволяют разбить задачу на следующие фрагменты:

s°°(x, y).= g< x, j,)d°°(. У) (modp (x)) (mod 9°(</)), .>U. ,лл(о.>),. ,л (modp°> (х)) (mod (у)).