4.2. Основная идея алгоритма

Краеугольным камнем алгоритма Винограда является теорема [4.4], дающая решение, казалось бы, отвлеченной задачи: для заданных полиномов определить минимальное число умножений, необходимых для вычисления,

где заданный монический полином. С ДПФ эту задачу связывают два обстоятельства. Во-первых, можно показать, что матрица ДПФ родственна другому специальному преобразованию, матрица которого является лево-циркулянтной (точное определение приведено ниже). Во-вторых, можно показать, что вычисление этого преобразования идентично вычислению (4.5). Поэтому минимизация числа умножений в (4.5) приводит к минимизации числа умножений при вычислении ДПФ.

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

Здесь будем рассматривать матрицу, которая является частным случаем матрицы Ханкеля, а именно, матрицу Ханкеля (порядка с индексами, лежащими в диапазоне ), у которой

т. е. последний столбец является тривиальной перестановкой элементов первой строки. Следовательно, такая матрица полностью определяется своей первой строкой. Вторая строка получается из первой циклическим сдвигом влево (элемент, выдвинутый за пределы строки влево, появляется справа), третья строка порождается таким же способом из второй и т. д. Назовем такую матрицу лево-циркулянтной, или -матрицей. Подобным образом линейное преобразование, задаваемое такой матрицей, будем называть лево-циркулярным преобразованием

В общем виде третьего порядка записывается выражением

Заметим, что (4.7) можно рассматривать как соотношение для получения последовательности из последовательностей . С этой точки зрения часто называют циклической корреляцией последовательностей . С другой стороны, инвертированную последовательность рассматривают как циклическую свертку последовательностей

В большинство последующих математических преобразовании входят матрицы, которые не будучи сами ЛЦ-матрицами, содержат

ЛЦ-подматрицы. Будем называть такие матрицы квазилево-циркулянтными матрицами (КЛЦ).

Обратимся к связи между ЛЦП и ДПФ. Как станет очевидным позже, нам нужно рассматривать некоторую тривиальную модификацию ДПФ:

где — произвольная комплексная константа. Когда то (4.9) превращается в стандартное ДПФ.

Пусть — порядок ДПФ — удовлетворяет — простое, — целое),

— нечетное),

Покажем теперь, что для таких может быть представлено в виде КЛЦ-матрицы. Переход к этому виду, приведенный в [4.5], основывается на теоретико-числовом понятии примитивного корня. Примитивным корнем для числа удовлетворяющего (4.10), является целое число, целые степени которого, взятые по порождают все целые числа из интервала за исключением чисел, кратных

Количество чисел, лежащих в упомянутом интервале и кратных

поэтому количество целых чисел, порождаемых корнем

и можно сказать, что последовательность

является перестановкой тех целых чисел из интервала которые не кратны

Используем теперь эти идеи для переобозначения индексов в Все индексы, не кратные будут представлены в виде (4.13). А именно, обозначая

определим

Теперь с помощью индексов, кратных определим

Введение заключенного в скобки индекса заслуживает некоторого пояснения. То, что здесь рассматривается, представляет собой некоторое перемешивание (перенумерацию) величин, обозначенных Из предыдущего следует, что членов, образующих множество можно разбить на два подмножества: -элементное множество, в котором выражается через (4.14), и оставшееся множество элементов, в котором кратно Используя определение (4.15), можно обозначить элементы первого подмножества Подобным образом можно было бы определить — целое, в результате чего получили бы удобную нумерацию элементов второго подмножества Однако делать это нет необходимости, и такой подход вызвал бы трудности в разд. 4.6, где множество должно быть разбито на при подмножества. Выбранный здесь подход основывается на том факте, что индексация элементов второго подмножества может быть совершенно произвольной, лишь бы она обеспечивала надежное опознавание множества, на которое мы ссылаемся. Из (4.16) явно видно, что для индексации элементов второго подмножества выбрано простое копирование индексов соответствующих членов Индексные скобки в являются просто признаком того, что этот член является элементом второго подмножества. Заметим, что нулевой индекс появляется в обоих подмножествах. При этом

Введя необходимые понятия, перейдем к исключению из (4.9). Для этого разделим сумму (4.9) на две части. В первой части — целое), т. е. Во второй части . В результате получим

где

Зависимость показателя степени в (4.21) от показывает, что (4.21) является преобразованием Ханкеля. Это значит, что если записать (4.21) в матричной форме, используя и а в качестве индексов строки и столбца соответственно, то матрица, преобразующая в В, является матрицей Ханкеля. Более того, она является тем частным случаем матриц Ханкеля, которые определены как лево-циркулянтные. Чтобы показать это, заметим, что по условиям (4.6) наша матрица Ханкеля будет лево-циркулянтной, если

Но поскольку примитивный корень всегда удовлетворяет

очевидно, что (4.22) действительно справедливо и (4.21) является ЛЦП. Итак, перестановки (4.14) — (4.16) преобразуют любую матрицу ДПФ порядка удовлетворяет (4.10)] в матрицу КЛЦ, ЛЦ-часть которой имеет порядок .

Особый интерес представляет частный случай, когда — простое число, т. е. так что (4.12) дает

а последовательность (4.13) является результатом перестановки целых чисел . В этом случае (4.18)-(4.20) упрощаются следующим образом:

Чтобы проиллюстрировать эти идеи, рассмотрим случай Наименьшим положительным примитивным корнем 7 является -3 [4.6]. Непосредственное вычисление дает

Применяя (4.14) — (4.16), приходим к следующему виду:

ЛЦ-структура здесь совершенно очевидна.

Итак, установлена первая связь с задачей (4.5) для удовлетворяющих (4.10). Это ограничение на далее будет ослаблено. Обратимся теперь к второй связи, а именно, к демонстрации того, что вычисление ЛЦП эквивалентно вычислению (4.5). Мы намереваемся установить эту эквивалентность для того, чтобы опираясь на нее, построить алгоритмы некоторых ЛЦ-преобразований общего вида малых порядков. Следует заметить, что ЛЦ-матрица, с которой мы имеем дело, является матрицей, полученной перестановкой подматрицы ДПФ и, будучи таковой, останется функцией одной переменной тогда как ЛЦ-матрица общего вида порядка является функцией переменных. Это обстоятельство предполагает дальнейшие упрощения, которые и будут реализованы позже.

Рассматриваемое умножение матриц показано в следующем выражении, где явно просматривается ЛЦ-структура:

Введем теперь вспомогательные полиномы (индексы полиномов указывают на их степень).

Рассмотрим произведение полиномов

Легко увидеть, что коэффициенты этого полинома можно получить перемножением матриц (4.34).

Сравнивая (4.34) с (4.29), видим, что перестановка двух отмеченных треугольных секций преобразует матрицу (4.34) в тривиальное расширение матрицы (4.29). Этот факт можно отобразить следующими соотношениями между полиномами

где оказывается полиномом степени Следовательно,

Заметим, что в стоящей справа дроби степень числителя меньше степени знаменателя. Это означает, что является остатком отделения на Другими словами,

Здесь используется тот факт, что порядок ЛЦ-матрицы в (4.29)

Равенство (4.38) показывает, что ЛЦП из (4.29) можно выполнить путем перемножения полиномов, идентичного перемножению в (4.5). Это определяетвторую связь.

Теперь рассмотрим число умножений, необходимых для вычисления (4.29). Прямое умножение матриц требует скалярных умножений. Значительно меньшее значение следует из теоремы Винограда [4.4]. В более узкой трактовке применительно к данному случаю теорема устанавливает, что, если представим в виде

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

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

где — целые числа и не содержит никаких рациональных умножений. В соответствии с теоремой Винограда полиномы потребуют в общей сложности умножений и дополнительные рациональные умножения, появившиеся в (4.41), не учитываются. Чтобы увидеть, что же включается в число умножений, поясним дробь в (4.41). Пусть К — наименьший общий знаменатель и

Тогда

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

Таким образом, вместо (4.38) теперь имеем

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

Стоит отметить, что, хотя с чисто теоретической точки зрения все верно, практически следует учитывать затраты в виде дополнительных сложений, вводимых для исключения рациональных; умножений. Очевидно, что, когда эти затраты превышают затраты на умножения, которые они заменили, лучше оставить умножения. Такая ситуация действительно возникает при больших Поэтому алгоритм, использующий достоинства теоремы Винограда, должен быть сконструирован так, чтобы ДПФ большого порядка разбивалось на ЛЦ-преобразования малых порядков. Фактически все-порядки ДПФ, появляющиеся в табл. реализуются посредством трех ЛЦ-преобразований порядков 2, 4, 6.

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

Таблица 4.1

Рациональная факторизация