Главная Промышленная автоматика.

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

Например, в гл. 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

ас - bd

b а.

be + ad

Здесь 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, и указывать транспонирование верхним индексом Т.





0 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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 [156] 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.004