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

b с а b

требует трех умножений.

12.6. Обобщите упр. 12.5, показав, что для умножения тёплицевой (пхп)-матрицы на вектор необходимо 2п-1 умножений. Как близко к этой границе вы можете подойти при п=3?

*12.7. Можно обобщить алгоритм умножения из разд. 2.6, разбивая каждый из сомножителей на три части и затем вычисляя произведение матрицы на вектор

а О 0" b а О Г d с Ь а е О с b \f О О cJ

за минимально возможное число умножений. Сколько умножений требуется для решения этой задачи? Приводит ли этот подход к улучшению алгоритма из разд. 2.6?

**12.8. Пусть F - поле и Oj, . . . , а„ и х,, . . . , Хр- непересекающиеся множества формальных переменных. Пусть \=[хи . . . . . ., XpV, а М - (гхр)-матрица с элементами из Fla,, . . . , а„], у которой q столбцов линейно независимы по модулю fПокажите, что при предварительной обработке вектора х, т. е. когда не учитываются произведения, включающие только Xi, . . . , Хр, вычисление произведения Мх все же требует q/2 умножений.

**12.9. Пусть ровно k выражений из множества Р, никакая нетривиальная линейная комбинация элементов которого не рарна постоянной, представляют собой одиночные умножения (например, они имеют вид а*Ь, где а и 6 - формальные переменные); допустим, что q умножений достаточно, чтобы вычислить все выражения из Р. Покажите, что существует вычисление для Р с q умножениями, k из которых совпадают с теми выражениями из Р, которые можно вычислить с помощью одного умножения.

*12.10. Покажите, что для вычисления выражений ас и bc+ad требуется не менее трех умножений. Указание: Воспользуйтесь упр. 12.9.

*12.11. Покажите, что для вычисления множества из 2k выражений UiCi и biCi+Uidi, l<i<A, требуется не менее 3k умножений.

12.5. Покажите, что умножение тёплицевой (2х2)-матрицы (см. упражнения к гл. 6) на вектор, т. е.



которые входят в один л-членный кортеж, содержащий а,у. Пусть

л п С=1 /=1

Рассмотрите изменение / по мере выполнения шагов вычисления.

**12.21. Наложим следующее ограничение на вид шагов вычисления : в а -<-bQc операция 6 состоит в выборе п/2 формальных переменных из циклического сдвига л-членного кортежа b и л/2 формальных переменных из дополнительных позиций в с. Найдите вычисление для множества л-членных кортежей из упр. 12.20, состоящее из 0(п log л) шагов.

**12.22. Пусть G - ориентированный ациклический граф с л выделенными истоками (узлами, в которые не входят никакие ребра) и п выделенными выходами (узлами, из которых не выходят никакие ребра). Пусть X я Y - подмножества истоков и выходов соответственно, а G(X, Y) - подграф, состоящий из всех ориентированных ребер, лежащих на путях из узлов множества X в узлы множества Y. Пропускной способностью графа G{X, У) называется наименьшее число узлов, удаление которых (вместе с входящими и выходящими ребрами) отделяет каждый узел из X от каждого узла из Y. Допустим, что для любых X и Y граф G{X, Y) обладает пропускной способностью MIN (Х, F). Покажите, что для каждого л существует такой граф G с сп log л ребрами, где с - некоторая постоянная.

**12.23. Сдвигаюией схемой называется такой ориентированный граф с п истоками, занумерованными числами от О до л-1, и л выходами, занумерованными числами от О до л-1, что для каждого S, 0<5<л-1, найдется множество путей, непересекающихся по узлам, которое для каждого i содержит путь из истока / в выход (i+s) по модулю л.

(а) Покажите, что для каждого л существует сдвигающая схема с 2л log л ребрами.

(б) Покажите, что для сдвигающей схемы асимптотически требуется л log л ребер.

(в) Покажите, что с помощью сдвигающей схемы можно вычислить транспонированную матрицу.

Определение. Пусть F - поле и .....формальные переменные. Линейным вычислением называются последовательность шагов вида а -tr-kJ}-\-k, где а - переменная, 6 и с - переменные или формальные переменные, а и - элементы из F (называемые постоянными).

**12.24. Пусть F - поле комплексных чисел, А - матрица с элементами из f и х=[л:1, . . . , XjiV. Покажите, что любое линейное вычисление для А \ требует log ldet(i4)]/log(2c) шагов, где с - наи-



(б) Покажите, что существует вычисление, минимальное по числу умножений, в котором каждое умножение производится между линейной функцией от а,, а, . . . и линейной функцией от fti, bi, . . . . (Заметьте, что это утверждение не верно, если ограничиться случаем, когда основное кольцо коммутативно.)

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

**12.18. Пусть R - некоммутативное кольцо и а, Ь, х- векторы-столбцы из формальных переменных [а,, . . . , а,, [bi.....bnV,

[хи . . . , XpV соответственно. Пусть X - матрица, элементами которой служат линейные суммы из лгь . . . , х. Из упр. 12.17 следует, что вычисление множества билинейных форм (аХ) можно представить в виде

M{Pa-Qx),

где М, Р н Q - матрицы с элементами из F. Определим левое двойственное множество выражений для (аХ) как {\уХУ и определим вычисление, Р-двойственное к вычислению M(Pa-Q\), как P(Mb -Qx). Докажите, что вычисление, Р-двойственное к любому вычислению для {аТХу, вычисляет левое двойственное множество выражений для (аТХу.

*12.19. Докажите, что минимальное число умножений, необходимое для умножения (т X п)-матрицы на (п X р)-матрицу над некоммутативным кольцом, то же, что и для умножения (пХт)-матрицы на (/пХр)-матрицу. Указание: Воспользуйтесь упр. 12.18.

До сих пор в упражнениях содержался материал, относящийся к нижним границам для числа арифметических операций. В последующих упражнениях содержится материал более общего характера. Упр. 12.20 - 12.23 касаются транспонирования матриц. Для 1. jtt пусть Oij - формальные переменные. Рассмотрим модель вычислений, в которой каждая переменная представляет собой п-членный кортеж формальных переменных. Шаг а ч- 66с такого вычисления присваивает п-членному кортежу а формальные переменные, выбранные из b или с. Эти п-членные кортежи 6 и с не меняются.

*12.20. Докажите, что любое вычисление множества «-членных кортежей

{(1,-.....«„,)! l<t<«}

по множеству входов {{оц, . . . , а(„)1<1<п} требует не менее п log п шагов. Указание: Для каждых i и / пусть Sij обозначает максимальное число формальных переменных с нижним индексом /,





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.0037