Главная ->  Вычислительные алгоритмы 

1 2 3 4 5 6 7 8 9 10 11 12 13 [ 14 ] 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

разделу. Вместо того чтобы выбирать множество различных чисел {Ро, Pi, Pl+.v-s), выберем множество многочленов {д: - р X - Pi, X - Р£.+лг г). Тогда можно, как на рис. 3.6, записать

й (Ы = Л.-в, [g (х)\, d ф ) = [d (х)].

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

3.3. Алгоритмы Винограда

вычисления коротких сверток

Предположим, что требуется вычислить

S (х) = g (х) d (х) (mod ш (х)),

где т (х) - фиксированный многочлен степени п над полем F, а g{x) d (х) - многочлены над этим же полем, причем их степени меньше п. Задача вычисления линейной свертки s (х) = g (х) d {х) может быть вложена в эту задачу, если в качестве п выбрать целое число, большее степени многочлена s (дг), а в качестве m (х) - произвольный многочлен этой степени га. Тогда задача

s(x) = g (х) d (х) (mod m (д;))

становится тривиальной переформулировкой задачи вычисления линейной свертки, так как приведение по модулю т ix) не меняет S (х), коль скоро степень т (х) больше степени s (х). Это позволяет включить задачу о линейной свертке в общую задачу, рассматриваемую в данном разделе. Выбирая т {х) равным х - \, мы \ включаем сюда также задачу вычисления циклической свертки,

s(x)=g (х) d (х) (mod x - 1).

Мы хотим заменить задачу вычисления

s(x) = g (х) d (х) (mod т (х))

некоторым множеством задач с меньшим числом вычислений. Чтобы разбить задачу на подзадачи, разложим многочлен т {х)

на взаимно простые над некоторым подполем поля F многочлены:

т(х) = т<1)(х)т1>(л:) mi=-4 ()-Обычно если F - поле вещественных или комплексных чисел, то в качестве подполя разложения выбирается поле рациональных чисел, и мы будем ссылаться на такой выбор, хотя теория допускает и другие подполя. (Если свертка вычисляется в конечном поле GF (р ), то в качестве подполя разложения обычно выбирается простое подполе GF (р)). Процедура ставит своей целью минимизацию числа умножений в поле F, не пытаясь минимизировать число умножений в подполе. В большинстве практических случаев этими умножениями в подполе оказываются умножения на малые целые числа, обычно на -1, О или 1, которые тривиальны. Начиная с данногОМомента, мы не будем учитывать умножения на рациональные числа в полном числе умножений, хотя практически всегда надо проверять, являются ли эти рациональные числа на самом деле малыми целыми числами. Быстрые алгоритмы свертки основаны на вычетах

s ( ) = /? ( , Is ()1. * = 0.....-1.

Согласно китайской теореме для многочленов, многочлен s {х) можно вычислить по системе остатков в соответствии с формулой s(x) = am(x)sm{x)-----ha - (x)si-4x) (modm(x)),

где a > (д;)..... a - (x) - соответствующие многочлены с рациональными коэффициентами. Разобьем это вычисление на три шага. Сначала вычисляются-остатки (х) = ? ) Id (х)] и g ( ) = Ig МП ДЛЯ всех А = О, ...,/< -I. Эти

вычисления не содерж/т умножений. Затем вычисляются вели-

,s< () = g(-)/(- ) (modmm()) =

= Kmw[Km [g RrrW w I Wl 1 = = lg ()d< (x)l-

Наконец, вычисляется многочлен

s {X) = a<o) 5(0) -----\aK-\) () 5(/c-i) () (mod m {x)).

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

Структура алгоритма Винограда для вычисления свертки показана на рис. 3.7. Умножения возникают только на втором шаге при вычислении коротких сверток, задаваемых произведениями многочленов, g* {х) о! (х); так как число коэффициентов у многочленов g {х) и d* {х) равно степени много-



= с/(л) (mod m

= g(x) (mod m

A = 0,

. . .K - 1

= d>*Hx)g ix)

(mod m (,v))

A: = 0 A - 1

(mod m{x))

Рис. 3.7. Структура алгоритма Винограда для коротких сверток.

члена т* (х), то полное число умножений, необходимых для стандартного способа вычисления этих произведений,

равно [deg/nf*(х) р. Эго дает существенное уменьщение о

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

На рис. 3.8 дается поучительное сравнение алгоритма Винограда вычисления свертки и алгоритма, основанного на дискретном преобразовании Фурье. Для того чтобы сделать это сравнение более наглядным, алгоритм Винограда выписан в приведенных выше матричных обозначениях. После группировки членов и перехода к матричным обозначениям этот алгоритм записывается в виде равенства

s = C[Bgl-[Adl, где точка обозначает покомпонентное произведение векторов Bg и Ad. Из этого сравнения видно, что алгоритм Винограда является обобщением метода вычисления сверток с помощью преобразования Фурье.

В качестве примера рассмотрим вычисление свертки 3-точечного вектора с 2-точечным вектором. Пусть

g W = giX + go.

d (x) = dx + diX + d,.

Вход

Обёртка в частотной области

Вход

обёртка Винограда

D = Wd С = Wg,

г(?г W = [ oj *J-матрица размера пхп

D - Ad G = Be,

где матрицы А иВ размеров М{п) п содержат малш целые иисла

0, . .

. , п - 1

S, . G.D,

* = 0, .

Обратное преобразование Фурье

S CS,

где матрица С размера п содетит малые целые иисла

Выход / обёртка (mod зг~ 1)

выжод

свёртка (mod mC J)

Рис. 3.8. СраЕненне двух способбв вычисления сверток.

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

Степень линейной свертки s (х) = g (х) d (х) равна трем. Выберем

m (X) = X (X - 1) (х2 -f 1) = mC (х) m (х) ml (х).

.Чножители взаимно просты; возможно и другое разложение многочлена т (х), но для иллюстрации метода мы остановимся



на выбранном разложении. Вычеты равны g (х) = go, d< (х) = do,

g< W = gi + go. d(iW = d2 + di + do. g> (X) = glX + go, d<2> (X) = dx + (do - d,).

Следовательно,

s( )(r) = g do,

s (r) = (gi + go)(d2 + 4 + do),

s (X) = (gix + go) (diJc + (do - dj) (mod + 1). При вычислении s > (л:) требуется одно умножение, при вычислении s<) (х) требуется одно умножение и, как мы увидим, при вычислении s (х) требуются три умножения.

Вычисление s> (л:) сводится к вычислению двух величин

4 = gW-gW, sr = gi>d! + gSdS>

(которые случайно имеют структуру произведения комплексных чисел). Алгоритм этой части вычислений дается равенством

1 О -1 1 1 О

(gP-gD

1 1 1 О О 1

и содержит три умножения.

Последний шаг состоит в вычислении s (;:) по формуле

s(A:) = a 4(x)s< l(;t) + a<l(x)si4(x)-ba(2l(x)s<>() (modх<-x+J-), где а* (х), а (х) и а (д;) вычисляются по китайской теореме об остатках следующим образом. Воспользуемся соотношением

<*1 (д:) m(*i (лг) + ЛГ(1 (х) М№1 (х) = 1 и построим следующую таблицу:

0 X

+ л - 1

1 * - 1

;(> + X

- i U + Jf 2)

2 х * \

х -X

- iU - 2)

i (t - 1)

Тогда a< ) (x) = /Vi*>(x) ( >(- ) Следовательно, /

s(x) = - (x= - -f X - 1) s(°i (X) + 4 ( + x)s< (X) -f

+ -i- (x3 - 2x= -f X) si2l (x) (mod x< - x -f x - x).

Последнее равенство может быть перезаписано в виде матричного равенства

10 0 0

1111

10-20

-1 1 1-1

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

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

определение

10 0 0

0 10 0

о о 11 f

о о i о о о ip

10 0 0 0 10 0 0 0 11 0 0 10 0 0 0 1.

.0 1

1 1 1 -1

0 -1

1 Qj

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



1 2 3 4 5 6 7 8 9 10 11 12 13 [ 14 ] 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73