Таким образом,

L0 о

0 -l]

1 4]

0 -1

1 о о 1

-1 о

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

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

Рис. 3.15 следовало бы дополнить характеристиками коротких сверток для поля комплексных чисел. Каждый алгоритм вычисления свертки в вещественном поле подходит в качестве алгоритма для комплексного поля. Но иногда многочлен х - 1 над полем комплексных чисел разлагается на большее число простых делителей, чем над полем вещественных чисел. Это в комплексном случае дает конструктору алгоритма дополнительные возможности.

Алгоритм Винограда можно рассматривать как метод разложения некоторых матриц. Пусть s, g и d - векторы длины п, компонентами которых являются соответственно коэффициенты многочленов s(x), g (х) и d(x). Циклическая свертка s (х) =

I I

= 1-1

0 -1

-1 о -1 -1

1111 1-1 1-1 1 1-1-1

10-10 0 10-1

Рис. 3.14. Алгоритм 4-точечной циклической свертки.

s{x)=g (х) d {х) (mod х - 1) deg g (л) = л - I deg d (х) = п - 1

Вещественные свертки

Рис. 3.15. Характеристики некоторых алгоритмов вычисления циклической свертки.

= g [х) d (х) (mod X - 1) может быть записана в виде матричного произведения

S = Td.

Алгоритм Винограда, записываемый равенством

s = C[(Bg).(Ad)], может быть записан также в виде

S = CGAd,

где А представляет собой матрицу размера М (п) X п, G является диагональной матрицей размера М (п) X М (п), а С является матрицей размера п X М (п). Таким образом, алгоритм Винограда можно рассматривать как алгоритм разложения матрицы

Т = CGA,

где G - диагональная матрица, а С и А - матрицы, элементами которых являются малые целые числа.

Так как в большинстве приложений многочлену g (х) соответствует фиксированный КИО-фильтр, или по крайней мере КИО-фильтр, коэффициенты которого меняются не слишком часто, то вычисление G = Bg приходится выполнять не слишком часто и при подсчете общей вычислительной нагрузки им можно пренебречь. Следовательно, сложность матрицы В особой роли не играет.

Роли матриц Л и В симметричны, так как их можно поменять местами путем простого переименования векторов d и g. Алгоритм Винограда вычисления свертки допускает построение матриц А и В, отличающихся только перестановкой строк, и, следовательно, имеющих одну и ту же сложность; но в общем случае более целесообразно одну из матриц строить более сложной и именно ей приписывать роль матрицы А. Удивительно то, что в алгоритме циклической свертки можно менять ролями даже матрицы С и А. Способ сделать это описывается следующей теоремой.

Теорема 3.6.1 (теорема об обмене матриц). Если теплицева матрица S допускает факторизацию вида

S = CDE,

то она может быть также записана в виде S = (Ё)D(C)

где матрица Е отличается от матрицы Е обращенным порядком столбцов, а матрица С отличается от матрицы С обращенным порядком строк.

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

= JSJ = (JC) D (ЕJ) = CDE. Операция транспонирования завершает доказательство. □

Применим эту теорему к умножению многочленов по модулю многочлена х - , где 5 - некоторая константа. Пусть надо вычислить

S (х) g (X) d (х) (modx -!),

где g (х) ш d (х) многочлены степени не более п - 1. Если = 1, то мы имеем задачу о циклической свертке. Случай = -1 (а в поле комплексных чисел и случаи = ±/) также очень важен. Запишем это произведение многочленов в матрично-векторном виде

£rf.-,... trf d, А Jd.-i d: d, d

d,] Is..

s = Tg,

где Т.- теплицева матрица. Алгоритм

s = C[(Bd)-(Ag)] можно перезаписать в виде

S = CDAg,

где D - диагональная матрица, диагональные элементы которой равны компонентам вектора Bd. Согласно теореме 3.6.1,

s = (A)-D(C)-g.

Применительно к задаче вычисления циклической свертки тео-. рема 3.6.1 означает, что наиболее сложную из трех матриц А, В и С можно выбрать множителем при векторе g и включить ее в матрицу G.

3.7. Свертки в общих полях и кольцах

Любой алгоритм свертки, такой как алгоритм Кука - Тоома или алгоритм Винограда, представляет собой некоторое тождество, опирающееся на свойства операций в данном поле, в частности на свойства ассоциативности, дистрибутивности и комму-

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

В частности, алгоритм свертки двух вещественных последовательностей можно без изменений использовать для свертки последовательностей комплексных чисел. Если обозначить через М и А соответственно числа вещественных умножений и сложений, необходимых для вычисления вещественной свертки, и если для вычисления комплексной свертки использовать тог же алгоритм с обычными комплексными умножениями и обычными комплексными сложениями, то в общей сложности получится Ш вещественных умножений и 2Л + 2Л1 вещественных сложений. Если вместо этого воспользоваться построенным в разд. 1.1 комплексным умножением и рассматривать одну часть свертки как отводы фиксированного фильтра, то потребуется только ЗМ вещественных умножений VL 2А + ЗМ вещественных сложений.

Если длина комплексной циклической свертки равна некоторой степени двойки, то можно построить даже еще лучший алгоритм. Для пояснения того, как это делается, рассмотрим свертку по модулю х -\- 1.

В кольце многочленов по модулю многочлена х + 1, i >. 1, имеется элемент, квадратный корень из которого равен минус единице. Действительно,

-1 = х (mod х + 1)

так что в рассматриваемом кольце У- 1 = х* . Воспользуемся этим элементом, чтобы выписать комплексную свертку через две вещественные свертки.

Для вычисления комплексной свертки

s(x) =g{x)d{x) (mod х + где \

e(x)gAx) + ]e,(x) и d{x)=-d(x) + )d,%.

можно вычислить по модулю х -f 1 четыре вещественных свертки gB(x)d (x), g,{x)d (x),g(x)d,(x)Ke,(x)d,{x) и записать

Sr (х) = gs (х) ds (х) - g, (х) d, (х),

S; (х) = gR (х) d, (х) + g, (х) dR (X). Лучшая процедура, содержащая вдвое меньше умножений, сводится к введению многочленов

а (X) = 4- (gH (X) - x-gy (X)) (dR (X) - x>-d, (X)) (mod x + \) b(x)=l- (gH (X) + x-g, (X)) {dn(X) + x-d, (X)) (mod x + l).

вычисление которых сводится к вычислению двух вещественных сверток. Выходной многочлен s (х) = g (х) d (х) (modx + !) дается при этом равенствами

SR(x) = a(x) + b(x),

S, (х) = х- (а (х) - * (х)) (mod х -f l).

Мы хотим воспользоваться этой процедурой для вычисления комплексной циклической свертки

S (х) = g (х) d (х) (modx -!), где п равно степени двойки. Запишем

x -I=(x-l)(x + l)(x2-f 1)(х< + 1) ... (x /2-f 1). Тогда задача сводится к коротким циклическим сверткам вид

sC) (х) = gC) (х) d( (X) (mod х + 1). Комплексные свертки по модулям х - 1 и х + 1 являются скалярами, и их произведение вычисляется как произведение комплексных чисел. Их вклад в общую сложность очень мал. Если остальные комплексные свертки вычислять через две вещественные свертки, то рассматриваемый способ вычисления комплексной свертки потребует примерно вдвое больше вычислений, чем вещественная свертка той же длины.

Этот метод конкурирует с методом разложения многочлена X - 1 в поле комплексных чисел:

х- - 1 = (X - 1) (X -f I) (X - /) (X + /) ... (х - /) (х / + / ).

Каждая из индивидуальных подзадач теперь меньше, но арифметика является комплексной.

3.8. Сложность алгоритмов свертки

Пусть задан алгоритм решения некоторой задачи; следует ли этим удовлетвориться или следует попытаться найти лучший алгоритм? На этот вопрос трудно ответить по нескольким причинам. Во-первых, трудно выбрать критерий, согласно которому можио утверждать, что алгоритм .является наилучшим. Далее, если даже такой критерий выбран, то трудно утверждать, что характеристики оптимального алгоритма соответствуют выбранному критерию.

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