§ 27. Добавление нулей

177

использовании простейшего алгоритма, основанного на определении произведения матриц):

Х_г = (А_и + А₂₂) (В_п + Ваг), *5 = (Ац + А₁₂)В₂₂, Х₂ = (А₂₁ + А₂₂)В_1Ъ Х₆ = (А₂₁ - А_п) (В_п + В₁₂),

Х₃ = А_П(В₁₂ -В₂₂), Х₇ = (А₁₂ - А₂₂)(В₂₁ + В₂₂),

Х₄=А₂₂(В₂₁-В_п), далее используются только аддитивные операции:

С_п=Х₁+Х₄-Х₅+Х₇, c₁₂ = x₃+x_s,

с₂₁ = х₂ + х₄, с₂₂ = х₁ + х₃-х₂ + х₆.

В правильности этого можно убедиться прямой проверкой.

Равенство п = 2^к создает возможность для рекурсивного примене­ния алгоритма. Алгоритм Штрассена будем обозначать начальными буквами St фамилии его автора.

В приведенных формулах использовано восемнадцать сложений матриц порядка Z. Сложение двух матриц порядка Z требует I² сло­жений чисел. В предположении, что n = 2^fc,fceN, имеем для общего числа операций—сложений и умножений чисел:

1, если п = 1,

Г_а(п) =

ГпЛ ГпЛ² (27.12)

7r_St(JJ+18(Jj , еслип>1.

Если п е N+ произвольно, то вначале к матрицам А и В добавля­ются нулевые строки и столбцы (см. (27.2)) так, чтобы порядки мат­риц стали равными 2^Г1о&п1, а затем применяется описанный рекур­сивный алгоритм. Рассматривая равенство (27.12) как систему двух неравенств со знаками ^ и ^ и применяя теоремы 27.1 и 27.2, полу­чаем следующий результат.

Сложность Г_а(п) по числу арифметических операций алгоритма Штрассена перемножения двух числовых матриц порядка п допускает оценку r_st(n) = e(n^l0&⁷), в то время как алгоритм, непосредственно следующий из определения произведения матриц, имеет сложность в(п³) (при этом log₂ 7 = 2,81...).

Что касается булевых матриц, то алгоритм Штрассена не может быть непосредственно применен для их умножения по той, напри­мер, причине, что этим алгоритмом используется вычитание, для ко­торого нет аналога в булевой арифметике. Но матрицы А и В по­рядка п, состоящие из нулей и единиц, можно перемножить как

178 Глава 6. Рекуррентные соотношения и сложность алгоритмов

O(n^1о&⁷),-смысл

целочисленные. Каждый элемент такого произведения не превосхо­дит n, он равен нулю, если и только если соответствующий эле­мент произведения булевых матриц равен нулю. Для того, чтобы в процессе применения алгоритма Штрассена к целочисленным мат­рицам не возникало больших промежуточных значений, здесь мож­но все вычисления проводить по модулю n + 1, т. е. проводить вы­числения не в кольце Z, а в кольце Z_n+1. Если M{n)—некото­рая верхняя граница для числа битовых операций, затрачиваемых при выполнении одной операции сложения, вычитания или умноже­ния в Z_n+1, то сложность модифицированного таким способом ал­горитма Штрассена будет допускать оценку O{n^ъ^⁷M{n)). Наивное умножение в Z_n+1 дает M(n) = O(log² n). Таким образом, M{n) рас­тет очень медленно в сравнении с остальными затратами. Так как log₂ 7 = 2,81..., мы можем использовать для сложности алгоритма Штрассена, модифицированного на булев случай, например, оценку O(n²'⁸²) или оценку O(n^1о&⁷), —смысл «O мягкого» объяснялся в кон­це § 22.

Применение алгоритма Штрассена и арифметики по модулю n + 1 дает алгоритм умножения двух булевых матриц порядка n, битовая сложность которого допускает оценки O{n^ъ^⁷) и O(n²'⁸²).

Мы ограничились рассмотрением применения стратегии «разде­ляй и властвуй» для случая, когда в результате этапа разделения воз­никают две задачи, и каждый из размеров входа примерно вдвое меньше изначального размера. Иногда разделение приводит к трем и более задачам.

В 1963 г. А.Л.Тоом обобщил идею умножения Карацубы¹. Пусть s — большее единицы целое. Предполагая, что битовая длина m каж­дого из сомножителей имеет вид s^k, k е N, последовательность дво­ичных цифр каждого из сомножителей можно разбить на s групп по s^k-1 цифр. Тоом показал, что умножение исходных чисел сводится к 2s - 1 умножениям чисел битовой длины s^k-1 (в умножении Кара­цубы s = 2, 2s - 1 = 3), остальные затраты—сложения, сдвиги—будут ограничены функцией cm, где c — зависящая от выбора s константа. Здесь этап разделения приводит к 2s - 1 задачам. Для умножения То-ома (TM) неравенство

1, если m = 1,

(2s - 1)T^ ( — ) + cm, если m > 1,

T^(m)^ _sГmЛ (²⁷.¹³)

См. [36], [4].