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

Например, в гл. 6 мы видели, что умножение двух (2х2)-матриц за 7 арифметических умножений дает алгоритм умножения произвольных матриц за время 0а(л°8). Использование же 18 сложений в алгоритме Штрассена не влияет на асимптотику. На первом уровне рекурсии для алгоритма Штрассена 7 умножений {(п/2) х {п/2))-матриц по мере роста п становятся гораздо сложнее, чем 18 (или любое другое число) сложений и вычитаний матриц того же размера.

На самом деле если бы можно было умножать две (2х2)-матрицы с помощью только шести умножений в некоммутативном кольце, то у нас мог бы быть алгоритм умножения матриц со сложностью 0а(л°8)=0а(л*) независимо от того, сколько тратится на умножение (2х2)-матриц сложений и вычитаний. (Можно, однако, показать, что для того, чтобы такой алгоритм работал для произвольного кольца, для умножения (2х2)-матриц необходимы 7 умножений; см. Хопкрофт, Керр [1971].)

Вот другой пример. В разд. 2.6 мы видели, что можно умножить два л-разрядных двоичных целых числа за OБ(л*) шагов, потому что достаточно трех умножений, чтобы вычислить выражения ас, bd и ad+bc. Если бы можно было вычислять эти выражения с помощью только двух умножений, то было бы М {п)2М (п/2)-\-сп для некоторой постоянной с. Такое вычисление, примененное рекурсивно, привело бы к алгоритму умножения целых чисел со сложностью Об(« log п), который был бы лучше всех известных. К сожалению, как мы покажем, для вычисления этих выражений в любом поле требуется не менее трех умножений.

12.3. МАТРИЧНАЯ ФОРМУЛИРОВКА ЗАДАЧ

Многие задачи можно сформулировать в терминах вычисления произведения матрицы на вектор-столбец. Элементы матрицы берутся из f [fli, . . . , а„], где F - поле и uf, . . . , а„ - формальные переменные. Компонентами вектора-столбца служат формальные переменные, отличные от «х, . . . , а„.

Пример 12.4. Задачу умножения двух комплексных чисел a+ib и c+id можно записать так:

Здесь F - поле вещественных чисел, а элементы матрицы взяты из F[a, b\. Вектор состоит из формальных переменных cad. □

[1, X, х\..., X"]

Здесь F - поле вещественных чисел, а элементы (1 Х(/г+1))-мат-рицы принадлежат F[x\. □

12.4. НИЖНЯЯ ГРАНИЦА ДЛЯ ЧИСЛА УМНОЖЕНИИ, СВЯЗАННАЯ С РАНГОМ ПО СТРОКАМ

Определение. Пусть F - поле и Oi, . . . , а„ - формальные переменные. Обозначим через floi, ... , а„] /и-мерное пространство векторов с компонентами из F[ai, . . . , а„], а f"» пусть будет т-мерным пространством векторов с компонентами из F. Множество векторов {vi, . . . , Vj} из Oi, . . . , а„] называется линейно независимым по модулю fесли для любых Ui, . . . , ииз F соотноше-k

ние UiVi б f" влечет за собой, что все ut равны нулю. Если векторы

Vi не являются линейно независимыми по модулю fто их называют зависимыми по модулю f

Линейную независимость по модулю F" можно трактовать иначе, рассмотрев факторпространство F"lai, . . . , UnVF" классов эквивалентности векторов из f»[ai, . . . , а„]. (Векторы Vi и Уг из f "[oi, ... , а„] эквивалентны тогда и только тогда, когда разность Vl-Vj принадлежит fЛинейная независимость по модулю F" означает линейную независимость классов эквивалентности из »[а„ . . . , aJ/F-.

Пример 12.6. Пусть F - поле вещественных чисел, а а н b - формальные переменные. Тогда три вектора

"1

г-а -1

2а АЬ

2а-2Ь

из Р[а, Ь] зависимы по модулю Р, поскольку

г- яП

а J

TVi + Vj -V3 =

принадлежит

Пример 12.5. Вычисление значений полинома i-* можно выразить как

с другой стороны, векторы

лпнейно независимы по модулю F. В самом деле, пусть 2 "jV; g F*.

Тогда Uib+UiuF. Поскольку ни а, ни b не принадлежит F, то «1=«2=0. Кроме того, соотношение Uia+UsbF влечет за собой "i=«3=0. Следовательно, Vi, Va и Vs линейно независимы по модулю Я. □

Пусть М обозначает (гХр)-матрицу с элементами из F. Число линейно независимых строк в матрице М равно числу ее линейно независимых столбцов. Но если элементы матрицы М принадлежат F [ui, . . . , йп], то число линейно независимых строк по модулю FP, вообще говоря, не равно числу линейно независимых столбцов в М по модулю f. Например, в (1хЗ)-матрице lai «а из] одна строка линейно независима по модулю F и три столбца линейно независимы по модулю F. Рангом по строкам матрицы М по модулю Fp называется число строк в М, линейно независимых по модулю Fp. Ранг по столбцам матрицы М по модулю F определяется аналогично.

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

1) F - поле,

2) {fli, ... , On} и {xi.....Хр} - непересекающиеся множества формальных переменных,

3) М есть (гХр)-матрица с элементами из F[ai.....an],

4) X - вектор-столбец [xi, . . . , xV

Теорема 12.1. Пусть М -матрица с элементами из Flui, . . . ... , а„] U X - вектор-столбец Ixi, . . . , xV. Предположим, что ранг по строкам матрицы М равен г. Тогда любое вычисление произведения М\ требует не менее г умножений.

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

Допустим, что в данном вычислении произведения Мх необходимы S умножений. Пусть ei.....е - выражения, вычисляемые

Так как неудобно записывать векторы-столбцы в виде столбцов, мы будем часто записывать их в виде строк, как в гл. 7, и указывать транспонирование верхним индексом Т.