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

В данном разделе мы будем исследовать характернстикн оптимального (в смысле минимального числа умножений) алгоритма свертки. Для этого надо уточнить понятие умножения, и мы сделаем это так, чтобы можно было ответить на интересующие нас вопросы. А именно, мы хотим определить умножение таким специальным образом, чтобы под произведением d-g понималось произведение произвольных вещественных чисел, но туда бы не входило произведение 2g, так как его можно интерпретировать как g g. Такое различие легко принять, но как быть с произведением 3g или (5/7) g? Мы выберем определение, которое приводит к полезным результатам. Вычисление d-g будем считать умножением только тогда, когда оба сомножителя -принимают произвольные вещественные значения, и не будем считать умножением, если произвольные вещественные значения допустимы только для одного из них, а другой должен быть рациональным. Мы увидим, что это определение, хотя интуитивно и кажется несколько ущербным, приводит к осмыслейным результатам. Выбранный нами критерий может также вызвать подозрение потому, что возникающие в приложениях числа всегда записываются словом конечной длины, так что все возникающие в приложениях числа являются рациональными. Тем не менее если в Прцнципе переменные принимают вещественные значения, то указанное вычисление будет называться произведением. ,

В указанном смысле алгоритм Винограда вычисления коротких циклических сверток Являются оптимальными. Ни один алгоритм вычисления я-точечной циклической свертки не содержит умножений меньше, чем алгоритм Винограда. Доказательство этого факта составляет одну из сложных задач данного раздела. Мы докажем следующие результаты:

1. Никакой алгоритм вычисления линейной свертки двух последовательностей длин L и iV не может содержать меньшее число умножений, чем i -(- Л - 1.

2. Если число простых делителей многочлена х - 1 равно /, то никакой алгоритм вычисления п-точечной циклической свертки не может содержать меньшее число умножений, чем 2п - t.

3. Если число простых делителей многочлена р (х) равно t, то никакой алгоритм вычисления произведения многочленов g (х) d (х) по модулю р (х) НС может содержать меньшее число умножений, чем 2п - t.

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

Рассматриваемые идеи не зависят от поля. Пусть F - некоторое поле, которое мы назовем полем вычислений, а £ ;- его подполе, называемое полем констант нли основным полем. Элементы

ИЗ Е называются скалярами. Пусть d = (do, dn i) и g = = (go, gr.i) - произвольные векторы фиксированных длин л иге компонентами из поля F. Компоненты векторов d и g будем называть неопределенными переменными или просто переменными. Эти п -\- г переменных величин независимы: их не связывают никакие соотношения. Алгоритмом называется правило

вычисления последовательности элементов /i.....f, из F, таких

что каждый элемент последовательности равен одной из Следующих величин: (1) или компоненте вектора d, или компоненте вектора g, или сумме, разности или произведению двух таких компонент; (2) сумме, разности или произведению компонент вектора d или вектора g на элемент fj последовательности с номером /, меньшим номера i; (3) сумме, разности или произведению двух элементов fj и /(, последовательности, номера / и k которых меньше номера i; (4) элементу поля Е.

Скажем, что алгоритм вычисляет выходной вектор s, если компоненты вектора s содержатся в последовательности fi, /j. Необходимо подчеркнуть, что являющиеся компонентами вектора S переменные величины связаны некоторыми функциональными соотношениями с переменными, являющимися компонентами векторов d и g. Алгоритм, вычисляющий вектор s, представляет собой фиксированную процедуру правильного вычисления S для любых возможных значений входящих в d и g переменных.

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

Данное определение алгоритма можно проиллюстрировать примером комплексного умножения. Сначала запишем его в виде

Тогда равенства

f = са, f, = db, f, = f,- f f, = da, h = cb, f.

дают описание алгоритма в виде последовательности правил вычисления.

Вычисление произведения комплексных чисел можно также записать в виде

о И [

(с - d) О 0 О (с -1- rf) о . О О d

1 б

1 -1

Тогда равенства

fi = а - Ь, f c - d, f, с -\-d, 4 = kd,

h = hb. h = dh, U = h+ h. h = h+ f,

дают описание последнего алгоритма в виде последовательности правил вычисления.

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

Теперь можно формализовать определение задачи вычислений. Будем рассматривать только задачи вида

s = Hd,

где d - входной вектор данных длины к, а s - выходной вектор длины п. Элементы матрицы Н представляют собой линейные комбинации г неопределенных переменных go, ...,gr-i- Втипичных случаях г меньше числа элементов матрицы Н и каждая переменная может присутствовать в матрице Н более одного раза. Такая структура включает в себя все рассмотренные задачи вычисления свертки.

Под элементами матрицы Н будем понимать не элементы поля, а линейные комбинации неопределенных переменных вида

где a,js являются скалярами. Две такие линейные формы можно складывать, любую линейную форму можно умножать на скаляр. Множество таких линейных форм нал&яём Е образует векторное пространство, которое мы обозначим Е lgo> gr-i 1- Таким образом, Н является матрицей над множеством линейных форм. Для матрицы Н не выполняются многие известные свойства матриц, поскольку она является матрицей не над полем (и даже не над кольцо.м), а над множеством Ё [g, gr-i\- В частности , ранг по столбцам не обязательно равен рангу по строкам. Как мы увидим, ранг по строкам и ранг по столбцам каждый дают нижнюю границу для числа умножений в задаче s = Hd. Возможность менять ролями векторы g и d дает два пути применения этих двух границ.

Ранг по строкам определяется следующим образом (аналогично определяется ранг по столбцам). Каждая строка матрицы Н представляет собой вектор длины к с компонентами из множества)

) Это множество образует векторное пространство, но мы предпочитаем называть его множеством, так как не рискуем говорить вектор векторов .

Е Igo, ....grj)- Линейная комбинация строк матрицы Н также является вектором длины к с компонентами из того же множества

вида £ Pjhi, где элементы Pi принадлежат полю Е для всех

i = I, п. Рангом по строкам матрицы Н называется мощность наибольшего множества линейно независимых строк, т. е. такого наибольшего множества строк, что никакая ненулевая их линейная комбинация не равна нулю.

Например, над полем рациональных (вещественных) чисел ранг по столбцам матрицы

2gi-2s s

равен двум, так как

но никакая линейная комбинация двух столбцов не равна тождественно нулю.

Теорема 3.8.1 (теорема о ранге по строкам). Для произвольного алгоритма вычисления s = Hd число умнозкений по меньшей мере равно рангу по строкам матрицы Н.

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

= Md .

Идея доказательства сводится к построению подходящей матрицы А над полем Е, для которой выполняются известные свойства матриц.

Предположим, что в алгоритме, задаваемом последовательностью fx.....fjf, имеется / шагов умножения, задаваемых соответственно ; членами последовательности е. е,. Тогда первые р компонент вектора s должны быть линейньши комбинациями

ЭТИХ членов-Произведений, линейных членов и элементов основного поля. Таким образом,

где элементы матрицы А принадлежат основному полю Е, а компоненты вектора b являются линейными комбинациями неопределенных переменных и элементов основного поля.

Предположим теперь, что р больше, чем I. Тогда матрица А содержит строк больше, чем столбцов, и, следовательно, строки матрицы А линейно зависимы, т. е. существует такой вектор с над полем £, что сА = С. Следовательно,

с- (Md) = с (Ае + Ь),

и так как сА = С, то это приводится к виду

(сМ) d = сЬ.

В этом равенстве правая часть не содержит произведений неопределенных переменных, так как с содержит только элементы поля £, а в Ь не входят произведения неопределенных переменных; следовательно, и левая часть не содержит произведений неопределенных переменных. Так как компонентами вектора d являются неопределенные переменные, то отсюда следует, что сЖ не содержит неопределенных переменных. Но сМ является вектором, компоненты которого равнь! линейным комбинациям неопределенных переменных. Следовательно, 6в-равен нулю и строки матрицы Л1 линейно зависимы. Полученное противоречие означает, что 1 больше, чем р, и число умножений по меньшей мере равно рангу по строкам матрицы Н. □

Теорема 3.8.2 (теорема о ранге по столбцам). Для произвольного алгоритма вычисления s = Hd число умножений по меньшей мере равно рангу по столбцам матрицы Н. ,

Доказательство. Доказательство проведем индукцией. Если ранг по столбцам равен единице, то любой алгоритм должен содержать по меньшей мере одно умножение. Пусть при ранге по столбцам, равном / - 1, теорема верна. То есть если ранг по столбцам матрицы Н равен ; - 1, то любой алгоритм вычисления S = Hd содержит по меньшей мере / - 1 умножение. Щаг индукции состоит в доказательстве соответствующего утверждения для случая, когда ранг по столбцам равен /.

Предположим, что задан алгоритм вычисления s = Hd,

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

&го означает, что для некоторого множества скаляров а, сумма Л a,di является множителем в некотором умножении,

причем а, ф 0. Так как на скаляры не наложено никаких ограничений, то можно полагать а, равным 1, так что член d, +

+ Jj <i<ii является множителем в некотором члене-произведении.

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

s = Hd

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

Чтобы это сделать, заменим в исходной задаче переменную d,

на - S ajdj. Тогда последний член-произведение, содержащий /-I

множителем сумму dj + I] a,d будет представлять собой

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

s = Hd,

где d представляет собой вектор длины ;-1, формируемый из вектора d удалением последней компоненты, а матрица Н получается из матрицы Н заменой /-го столбца hj на столбец hj - oLjhi. Таким образом.