Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 22
Текст из файла (страница 22)
(Мы вновь прибегаем к вычислению индексов для размещения результатов сложения матриц в юрректных позициях матрицы С с накладными расходами сз(1) для кюкдого элемента.) Общее время вычисления в рекуррентном случае, таким образом, равно сумме времени разделения, времен всех рекуррентных вызовов и времени сложения матриц, получающихся после рекуррентных вызовов: Т(п) = б1(1) + 8Т(п/2) + О(пг) = 8Т(п/2) + О(пг) (4.16) О (1), если и = 1, 8Т(п/2) + ез(пг), если и > 1 .
(4.17) Как мы увидим из основного метода из раздела 4.5, рекуррентное соотношение (4.17) имеет решение Т(п) = О(пз). Таким образом, этот простой подход "разделяй и властвуй" оказывается ничуть не быстрее прямолинейной процедуры 81111Аке-МАтк1х-Мгл.т!Реу. Перед тем как продолжить изучение алгоритма Штрассена, давайте рассмотрим происхождение юмпонентов уравнения (4.16). Разбиение каждой матрицы и х и с помощью вычисления индексов требует времени 1В(1), но у нас разбиваются две матрицы.
Хотя можно сказать, что разбиение двух матриц требует времени О(2), юнстанта 2 поглощается О-обозначением. Сложение двух матриц со, скажем, /с элементами занимает время 6()е). Посюльку суммируемые нашим алгоритмом матрицы имеют по пг/4 элементов, можно утверждать, что суммирование каждой пары выполняется за время 9(пг/4). Однако 1В-обозначения вновь поглощают постоянный множитель 1/4, и мы говорим, что сложение двух матриц размером и/2 х и/2 выполняется за время ез(пг). У нас есть четыре таких сложения, и вновь вместо того, чтобы записать время их выполнения как 9(4пг), мы говорим, что они выполняются за время ез(пг).
(Конечно, вы можете заметить, что об этих четырех сложениях можно сказать, что они выполняются за время О(4пг/4) н что 4п /4 = пг, но главное в том, что 9-обозначение поглощает постоянные множители, какими бы они ни были.) Таким образом, в конечном итоге у нас имеются два члена О(п ), которые мы можем объединить в один. Однако, когда мы учитываем восемь рекурсивных вызовов, мы не можем просто поглотить постоянный множитель 8.
Другими словами, мы должны говорить, что вместе они требуют времени 8Т(п/2), а не просто Т(п/2). Вы можете прочувствовать эту разницу, взглянув на дерево рекурсии на рис. 2.5 для рекуррентного соотношения (2.1) (которое идентично рекуррентному соотношению (4.7)), в котором рекурсивный случай имеет вид Т(п) = 2Т(п/2) + ез(п).
Множитель 2 Заметим, что если мы реализуем разбиение с применением копирования, стоимость которого составляет 1В(пг), рекуррентное соотношение не изменится, а следовательно, общее время работы просто увеличится на постоянный множитель. Объединяя уравнения (4.15) и (4.16), мы получим рекуррентное соотношение для времени работы процедуры 80иАке-МАтк1Х-М1л.т1геу-Кес11кз1че: 104 Часть А Основы определяет, сколько дочерних узлов имеет каждый узел дерева, что, в свою очередь, определяет количество членов, вносящих вклад в общую сумму на каждом уровне дерева.
Если бы мы проигнорировали множитель 8 в уравнении (4.16) или множитель 2 в рекуррентном соотношении (4.1), то дерево рекурсии было бы линейным, а не "кустистым", и каждый уровень добавлял бы в сумму только один член. Таким образом, следует помнить, что хотя асимптотическая запись поглощает константные мультипликативные множители, рекурсивная запись, такая как Т(п/2), этого не делает. Метод Штрассена Ключевым моментом метода Штрассена является некоторое уменьшение "кустистости" дерева рекурсии, т.е. вместо восьми рекурсивных умножений матриц и/2 х п/2 он выполняет только семь.
Цена устранения одного умножения матриц — несколько дополнительных сложений матриц размером и/2 х п/2, но количество сложений при этом остается константой. Как и ранее, постоянное количество сложений матриц поглощается при записи рекуррентного уравнения для времени работы алгоритма В-обозначением. Метод Штрассена не так очевиден. (Наверное, это наибольшее преуменьшение, сделанное в данной книге.) Он состоит из четырех шагов. 1. Разделить входные матрицы А и В и выходную матрицу С на подматрицы размером п/2 х п/2, как в (4.9).
Этот шаг выполняется за время В(1) с помощью вычисления индексов, как и в процедуре 80УАке-МАтк1х-М~л.тпчл- КЕСОК$1ЧЕ. 2. Создать 10 матриц 51, Яз,..., Яю, каждая из которых имеет размер и/2 х и/2 и представляет собой сумму или разность двух матриц, созданных на шаге 1. Все 10 матриц можно создать за время Й(п~). 3. Используя подматрицы, созданные на шаге 1, и 10 матриц, созданных на шаге 2, рекурсивно вычислить семь матричных произведений Ры Рз,..., Рт. Каждая матрица Р, имеет размер и/2 х п/2.
4. Вычислить подматрицы Сы, Сзз, Сзз, Сзз результирующей матрицы С путем сложения и вычитания различных комбинаций матриц Р,. Все четыре подматрицы можно вычислить за время В(и~). Детально шаги 2-4 будут рассмотрены ниже, но у нас уже имеется достаточно информации для написания рекуррентного соотношения для времени работы метода Штрассена. Будем считать, что, когда размер матрицы п снижается до 1, мы выполняем простое скалярное умножение, как в строке 4 процедуры 800АкеМАтк1х-М~л.т1еьх-Кесцке1че.
Прн и > 1 шаги 1, 2 и 4 выполняются за общее время, равное 0(и ), а шаг 3 требует выполнения семи перемножений матриц размером п/2 х п/2. Следовательно, мы получаем следующее рекуррентное со- гвава 4. Разделай и ввавтвуй 105 отношение для времени работы Т(п) алгоритма Штрассена: (4.18) Мы обменяли одно матричное умножение на фиксированное количество сложений матриц. Когда мы научимся работать с рекуррентными соотношениями и получать нх решения, мы увидим, что это ведет к меньшему асимптотическому времени работы. Согласно основному методу из раздела 4.5, рекуррентное соотношение (4.18) имеет решение Т(п) = 9(п187).
Теперь рассмотрим метод Штрассена более подробно. На шаге 2 мы создаем следующие 10 матриц. Поскольку мы должны 10 раз складывать или вычитать матрицы размером и/2 х п/2, этот шаг выполняется за время 9(пг). На шаге 3 мы рекурсивно перемножаем и/2 х и/2-матрицы семь раз и вычисляем следующие семь матриц размером и/2 х и/2, кал4дая нз которых представляет собой сумму или разность произведений подматриц А и В. Заметим, что необходимо выполнять толью те умножения, которые приведены в среднем столбце представленных выше уравнений; правый столбец просто по- казывает, чему равны получающиеся произведения в терминах исходных подмат- риц, созданных на шаге 1.
Р1 —— Р2 = Рз = Рв 15 = Ра = Р7= 9 ( ), если и = 1, 7Т(п/2) + 9(пг), если и > 1 . 51 = В1г — Вгг Яг = Ап+ Ага Вз = Аш + Агг 54 = Вш — Вп Вз = Ап+ Ага 58 = Вп + Вгг о7 = .412 422 Ва = В21 + В22 Яд = Ап — А21 В„= Вп+ Вгг Ап 51 = Ап Вгг — Ап Вгг Яг Вгг = Ап Вяз+Ага Вгг Яз Вп =Ам Вп+Агг Вп 4гг В4 = -4гг Вгг — .4гг Вп 58 Яа = Ап Вп+Ап Вгг+ Ага Вп+Агг Вгг В7 Ба = Ащ Вш + Ащ Вгг — Агг Вш — Агг Вгг Яд 510 = Ап Вп + Ап .
Вгг — А21 ' Вп А21 Вгг Часть 4 Основы Шаг 4 суммирует и вычитает матрицы Ро созданные на шаге 3, и строит четыре подматрицы размером и/2 х и/2 окончательного произведения С. Мы начинаем с Сп =Рз+Р4 — Рг+Рь. Раскрывая правую часть и расписывая каждую подматрицу Р; в отдельной строке, размещая при этом сокращающиеся члены один под другим, мы видим, чему в конечном итоге равна подматрица Сп Ап Вп+Ап Вгг+Агг Вп+Агг Вгг -Агг Вп +Агг Вщ -Ап Вгг — Агг Вгг — Агг Вгг-Агг Вгз+Азг Вгг+Агг Вгз ' Ап Вп +Ага Вгз что соответствует уравнению 14.11). Аналогично мы присваиваем Сгг = Р1+Рг, так что Сзг равна Ап ' Вгг — Ап ' Вгг + Ап Вгг+ Агг Вгг +Ага Вгг Ап Вгг что соответствует уравнению (4.12). Установка Сгз = Рз + Р4 делает Сгз равной Аг1 В11+Агг В11 — Агг Вп + Ага.
Вгз +Агг Вщ Ащ Вп в соответствии с уравнением (4.13). Наконец мы присваиваем Сгг = Рз + Р1 — Рз — Рт, так что Сгг равна Ап Вы+Ам Вгг+Агг "Вы+Ад Вгг — А В +А °  — Агг. Вп — Аг1 Вп — Ап Вгг+Агз Вп+Агз Взг -Ап Вп +Агз ° Взг Агг Вгг 1ог Глава к Разделяй и властвуй в соответствии с уравнением (4.14). Всего на шаге 4 мы суммируем или вычитаем п/2 х и/2-матрицы восемь раз, что требует времени 9(пз). Таким образом, мы видим, что алгоритм Штрассена, состоящий из шагов 1-4, возвращает корректное матричное произведение и что рекуррентное соотношение (4.18) описывает время его работы. Поскольку, как мы узнаем из раздела 4.5, это рекуррентное соотношение имеет решение Т(п) = 9(п|ат), метод Штрассена асимптотически быстрее прямолинейной процедуры 30илкнМхтК1Х-М1Л.типу.
В заключительных замечаниях в конце зтой главы рассматриваются некоторые практические аспекты алгоритма Штрассена. упражнении Примечание: хотя в упр. 4.2.3-4.2.5 описаны варианты алгоритма Штрассена, прежде чем приступить к их решению, следует прочесть раздел 4.5. 4,2П Воспользуйтесь алгоритмом Штрассена для вычисления произведения матриц 7 5 4 2 Покажите, как вы зто делаете.
42.2 Запишите псевдокод алгоритма Штрассена. 4.2.З Как модифицировать алгоритм Штрассена для перемножения матриц размером и х п, где и не является точной степенью 2? Покажите, что получающийся в результате алгоритм выполняется за время 9(п'аз). 4.2.4 Чему равно наибольшее )с, такое, что если вы можете перемножить 3 х 3-матрицы с помощью Й умножений (не предполагая коммутативности умножения), то вы можете перемножить матрицы размером и х и за время о(о~к )? Каким должно быть время работы такого алгоритма? 4.2.5 В.
Пан (Ъ'. Рап) открыл способ перемножения матриц размером 68 х 68 с использованием только 132 464 умножений, способ перемножения матриц размером 70 х 70 с использованием 143 640 умножений и способ перемножения матриц размером 72 х 72 с использованием 155424 умножений. Какой нз методов дает нам лучшее асимптотическое время работы при его использовании в алгоритме "разделяй н властвуй" для перемножения матриц? Проведите сравнение с алгоритмом Штрассена. Часть С Основы 108 4.2.6 Насколько быстро вы сумеете умножить матрицу размером йп х и на матрицу размером п х йп, применяя алгоритм Штрассена в качестве подпрограммы? Ответьте на тот же вопрос для ситуации, когда мы меняем входные матрицы местами. 4.2. 7 Покажите, как перемножить комплексные числа а+ Ы и с + й, используя только три умножения действительных чисел. Алгоритм должен получать а, 6, с и с( в качестве входных данных и возвращать действительную (ас — Ы) и мнимую (ад + бс) части произведения по отдельности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
