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

3.2. Алгоритм Кука-Тоома

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

S (X) = g (X) d (X),

где deg d (х) = N - 1 и deg g (х) = L - 1. Степень многочлена S (х) равна N + L - 2, так что этот многочлен однозначно определяется своими значениями в N -\- L - 1 различных точках.

Пусть Ро, Pi.....Pl+.v-i - множество из L + N - 1 различных

вещественных чисел. Если нам известны Для k = О,

4 L - 1, то S (х) можно вычислить по интерполяционной формуле Лагранжа. Согласно теореме 2.7.10, многочлен

Ilzi n(x-Pj)

1=0 1Ф1

является единственным многочленом степени л - 1, принимающим значения s (Pt) при х = Рй для всех ft = О, п- 1. Идея алгоритма Кука - Тоома состоит в том, чтобы сначала вычислить величины s (Р/) для k = О.....п - 1, а затем воспользоваться интерполяцией Лагранжа.

Алгоритм Кука - Тоома приведен на рис. 3.3. Умножения даются равенствами

s(Pi.) = g-(POd(Pf.), ft = 0, L + Af-2. Всего имеется L N - 1 таких равенств, так что здесь мы имеем L -\- N - 1 умножений, и, если разумно выбирать точки о полное число умножений будет исчерпываться этими умножениями. Имеются еще и другие умножения, а именно те, которые . входят в вычисление величин d (Р) и g (Рь), и те, которые участвуют в интерполяционной формуле Лагранжа. Но эти умножения представляют собой умножения на малые константы, и мы не будем их учитывать при подсчете полного числа умножений хотя полностью их игнорировать нельзя.

) На самом даде не учитывать можно только умножения на О и ±1; во, как правило, за счет некоторых предварительных проделанных раз и навсегда вычислений удается свести рассматриваемые константы к трем указанным. - Прим. перев.

Выход

Рис. 3.3. Структура алгоритма Кука-Тоома.

Простейшим- примером является линейная {2х2)-свертка; d{x)=dxyd, g{x) = gxX + gQ и s{x) = d{x) g{x). К такому вычищению сводится прохождение двух отсчетов данных через КИО-фильтр с двумя отводами. Очевидный алгоритм выполнение такого вычисления содержит четыре умножения и одно сложение, но мы построим алгоритм с тремя умножениями, тремя сложениями. Может показаться, что эта задача слишком мала для каких-либо практических применений. Но на самом деле хороший алгоритм решения этой задачи является хорошим блоком, из которого можно строить тщательно проработанные алгоритмы. Таким образом, рассматр;ваемый пример представляет собой нечто большее, чем простую иллюстрацию алгоритма Кука - Тоома; он важен практически

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

1) Первым, еще до Тоома (1963) и Кука 0966), способ выполнения (2X2)-свертки с тремя умножениями и четырьм-: сложениями описал А. Карацуба [ДАН, 145 (1962), 293, 294]; его алгоритм- состоит в следующем: Sq = 4go, Sj = = igi. = ( + di) (go + gi), Sl = / - So - Eg. - Я/?ыж. перев.

степень многочлена s (х) равна двум, то надо выбрать три точки. Выберем их равными Ро = О, Pi = 1 и р = -1. Тогда

d (Ро) = do, g (Ро) = g ,

d (pi) = do + dl, g (Pi) = 0 + gi,

d(M=d,~-d g(M=go~g,

s (h) = g (Po) d (Po),

s (Pi) = g (Pi) d (Pi),

s (P.) = g (P.) d (PJ,

так что требуются три умножения.

Если КИО-фильтр задается фиксированным многочленом g {х), то константы g (р) не надо каждый раз вычислять заново; их можно вычислить заранее один раз и запомнить. Коэффициенты многочлена g {х) в запоминании не нуждаются.

Наконец, согласно интерполяционной формуле Лагранжа

s(x)=s (Ро) и () + S (Pi) Z-i (X) + s (PJ (X), где интерполяционные многочлены равны

L, (д:) = -х + !, Li (х) = (1/2) (г* + л:), {х) = (1/2) (д:= - х). Это завершает описание алгоритма Кука - Тоома для вычисления S {х). Но вычисления можно организовать в более компактной форме. Деления на 2 можно похоронить так, чтобы они не были видны. Для этого просто заменим константы g (Рд) новыми, поглощающими этот делитель. Пусть

Go = go, = (1/2) (go + G, = {\/2)(go-gi).

Так как в большинстве случаев многочлен g (х) фиксирован, то эти константы можно вычислить заранее, и ничто не мешает нам определить их таким образом. Тогда

Lo (х) = + 1, Li (х) = х + X, Lj {X) = X? - X.

Построенный алгоритм показан на рис. 3.4, айв компактной форме может быть записан в матрично-векторных обозначениях в виде

s = Cj[Bgl-[Ad],

где точкой обозначено покомпонентное умножение векторов Bg и Ad. Матричная запись дает удобную форму обозрения алгоритма, но вычисления, конечно, проводятся не посредством умножения матриц. Умножение на матрицы А и С выполняется как серия сложений. Возможная последовательность вычислений показана на рис. 3.4, Ь.

D, = rf - d,

s,i - So

>] - Sl - s,

1, = -s. . s, + s.

Phc. 3.4. Алгоритм Кука-Тоома вычисления линейной свертки 2-точечных векторов.

Алгоритм Кука Тоома можно рассматривать как факторизацию матрицы-ГЗ рассматриваемом примере свертка может быть записана в виде

go gi О

LS2 J

или, кратко, S = Td- На для этой свертки переписан

рис. 3.4с алгоритм Кука - Тоома с использованием диагональной матрицы, также обозначенной G и содержащей элементы вектора G. Алгоритм теперь имеет форму

S = CGAd,

что позволяет интерпретировать его как факторизацию матрицы Т = CGA, где А - матрица предсложений, С есть матрица постсложений, а G - диагональная матрица, ответственная за все умножения. Число умножений равно размерности матрицы О. Такое представление алгоритма очень полезно для обозрения его структуры.

В общем случае линейная свертка может быть выражена в виде

5 = Td,

где d - входной вектор длины Л, s - выходной вектор длины Л + Z. - 1 и Т представляет собой ({Л + L - 1) х Л)-матрицу, элементами которой являются компоненты вектора g. Алгоритм Кука - Тоома в такой форме представляет собой алгоритм факторизации матрицы

Т = CGA,

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

Алгоритм Кука - Тоома можно модифицировать к другому варианту, содержащему то же число умножений, но меньшее число сложений. Заметим, что = Sl-i-i- Для вычисле-

ния этого коэффициента необходимо одно умножение. Степень модифицированного многочлена

s(x)- Si .,xi+-2 = g (дг) d (X) - s ,x+-

равна L -f - 3, так что использующее идеи алгоритма Кука - Тоома вычисление этого многочлена требует L N - 2 умножений. Общее число умножений опять равно L -\- Ы - 1, но сложений теперь будет меньше.

Рассмотрим поведение этой модификации алгоритма Кука - Тоома при вычислении линейной (2х2)-свертки. Выберем Ро = О и Pi = -1. Тогда

d (Ро) = do, g (P.) = go,

d (Pi) = do~ di, g (Pi) =go-gi

nPo)=g(Po}d(Po}-gid,p

(() = g(Pi)d(?.)-gii,Pi. где t (x) = g (x) d (x) - gidx. Согласно интерполяционной формуле Лагранжа,

s {х) ~gx = t (Pi) ti (X) -f i (P ) Lo (x),

где Lo{x) = X + I и ii (x) = -x.

Объединение всех этих фрагментов дает искомый алгоритм

s(x) = gidix -f [-(do - di) (go - ffi) + g-idi + gAl * + godo-

Алгоритм содержит три сложения и три умножения. Его матричная форма выписана на рис. 3.5, который полезно сравнить с рис. 3.4.

Это приведенный на стр. 85 алгоритм А- Карацубы (1962), в котором не учтено в числе сложений вычисление go-ffi- - Прим. перев.

1 о

1 -1 О I

Рис. 3.5. Улучшенный алгоритм Кука-Тоома вычисления линейной (2X2)-свертки.

Алгоритм Кука - Тоома эффективен по числу умноженн но если объем задачи растет, то число необходимых сложений также начинает быстро расти. Это происходит потому, что хороший выбор чисел р, в виде О, 1 и -1 уже сделан, и с ростом задачи мы должны использовать также ±2, :t3 и другие малые целые числа. При этом матрицы А и С будут содержать эти числа. Конечно, умножения на них можно заменить соответствующим числом сложений, но это резонно делать только в случае, когда выбираемые числа малы. Поэтому алгоритм Кука - Тоома становится слишком громоздок при вычислении сверток, больших чем 3x4 или 4x4. Для больших задач надо пользоваться описываемыми в следующем разделе алгоритмами Винограда вычисления сверток или итерировать малые алгоритмы Кука - Тоома, используя изучаемые в гл. 7 гнездовые методы.

Имеется еще один подход к пониманию алгоритма Кука - Тоома, и эта альтернатива перекидывает мостик к следующему

Вход

Рис. 3.6. Другое описание алгоритма Кука-Тоома.