Метод декомпозиции (Метод «разделяй и властвуй»), страница 2

Метод декомпозиции

Количество сравнений ключей, выполняемых сортировкой слиянием, в худшем случае весьма близко к теоретическому минимуму количества сравнений для любого алгоритма сортировки, основанного на сравнениях. Основной недостаток сортировки слиянием – необходимость дополнительной памяти, количество которой линейно пропорционально размеру входных данных. Сортировка слиянием возможна и без привлечения дополнительной памяти, но такая экономия памяти существенно ее усложняет и дает в результате значительно больший постоянный множитель в формуле для времени работы.

Метод декомпозиции

Алгоритм Штрассена (1969 год) для умножения матриц. Основная идея, лежащая в основе этого алгоритма, заключается в открытии, что произведение C двух матриц A и B размером 2*2 можно вычислить с помощью только 7, а не 8 умножений, которые необходимы при использовании алгоритма грубой силы. Этого можно достичь, используя следующие формулы: с00 с01 a00 a01 b00 b01 = * = с10 с11 a10 a11 b10 b11

Метод декомпозиции

m1 + m4 – m5 + m7 m3 + m5 = m3 + m4 m1 + m3 + m2 – m6 где m1 = (a00 + a11) * (b00 + b11) m2 = (a10 + a11) * b00 m3 = a00 * (b01 – b11) m4 = a11 * (b10 – b00) m5 = (a00 –a01) * b11 m6 = (a10 – a00) * (b00 – b01) m7 = (a01 – a11) * (b10 + b11)

Метод декомпозиции

Таким образом, для умножения двух матриц 2*2 алгоритм Штрассена выполняет семь умножений и 18 сложений/вычитаний, в то время как алгоритм на основе грубой силы требует восьми умножений и четырех сложений. Пусть A и B – две матрицы размером n*n, где n – степень двойки. (Если n не является степенью двойки, можно добавить к матрицам необходимое количество строк и столбцов, заполненных нулями). Матрицы A и B и их произведение C можно разделить на четыре подматрицы размером n/2 * n/2 каждую. Алгоритм Штрассена состоит в том, что требуемые семь произведений подматриц вычисляются рекурсивно с использованием описанного метода.

Метод декомпозиции

Давайте определим асимптотическую эффективность данного метода. Если M(n) – количество умножений, выполняемых алгоритмом Штрассена для умножения двух матриц размером n*n (где n – степень двойки), то мы получим следующее рекуррентное соотношение для M(n): M(n) = 7*M(n/2) при n>1, M(1) = 1. Поскольку n = 2↑k, то M(2↑k) = 7↑k. Поставляя k = log2n, получаем M(n) = 7↑(log2n) = n↑(log27) = n↑2.807, что меньше, чем n³, необходимые для алгоритма на основе грубой силы.

Метод декомпозиции

Поскольку экономия количества умножений достигается ценой большого количества сложений, следует рассмотреть количество сложений A(n), выполняемых алгоритмом Штрассена. Для умножения двух матриц порядка n>1 алгоритму требуется семь умножений и 18 сложений матриц размером n/2*n/2; при n=1 сложений вообще не требуется, поскольку в этом случае задача вырождается в перемножение двух чисел. Все это приводит к следующему рекуррентному уравнению: A(n) = 7*A(n/2) + 18*(n/2)² при n>1, A(1) =0.

Метод декомпозиции

Хотя можно получить точное решение этого уравнения, в настоящий момент нас интересует порядок роста решения этого соотношения. Согласно Основной теореме, приведенной в начале, A(n) Є Θ(n↑(log27)). Другими словами, количество сложений имеет тот же порядок роста, что и количество умножений. Таким образом, можно сделать вывод о том, что эффективность алгоритма Штрассена – Θ(n↑(log27)), что лучше, чем эффективность алгоритма на основе грубой силы Θ(n³). После Штрассена открыт ряд других алгоритмов для перемножения матриц размером n*n. Наиболее быстрый был предложен Куперсмитом и Виноградом – его эффективность Θ(n↑2.376).

Метод декомпозиции

Значение показателя уменьшается за счет увеличения сложности алгоритмом. Из-за большой величины постоянного множителя в формуле времени работы алгоритма все предложенные алгоритмы умножения матриц не имеют практической ценности, но представляют большой теоретический интерес. С одно стороны, новые алгоритмы приближаются к теоретическому пределу, который равен n² умножений, но точная величина «зазора» между теоретическим пределом и наилучшим из возможных алгоритмом остается неизвестна. С другой стороны умножение матриц важно для решения систем линейных уравнений.

Метод декомпозиции