Умножение матриц – алгоритм Штрассена Решаемая задача – вычисление произведения матриц A B при больших A и B. Предполагаем, что обе матрицы – квадратные, - презентация

1 Умножение матриц – алгоритм Штрассена Решаемая задача – вычисление произведения матриц A B при больших A и B. Предполагаем, что обе матрицы – квадратные, размера n n. Предположим, что n – степень двойки. Тогда можно воспользоваться следующим рекурсивным алгоритмом: Эффективность (число умножений) T(n) этого алгоритма можно вычислить: T(1) = 1; T(n) = 8T(n/2), откуда получаем T(n) = n 3 = n log 8. Формулы для приведенного выше алгоритма: P 1 = A 1 B 1 ; P 2 = A 2 B 2 ; P 3 = A 3 B 3 ; P 4 = A 4 B 4 ; P 5 = A 5 B 5 ; P 6 = A 6 B 6 ; P 7 = A 7 B 7 ; P 8 = A 8 B 8 ; r = P 1 + P 2 ; s = P 3 + P 4 ; t = P 5 + P 6 ; u = P 7 + P 8 ; Всего 8 матричных умножений и 4 матричных сложения. Алгоритм Штрассена позволяет уменьшить асимптотическую оценку до T(n) = n log 7 С помощью уменьшения количества необходимых промежуточных матриц P i.

2 Умножение матриц – алгоритм Штрассена (продолжение) iAiAi BiBi P i = A i B i 1ag hag ah 2a + bhah + bh 3c + dece + de 4df edf de 5a + de + hae + ah + de + dh 6b df + hbf + bh df dh 7a ce + gae + ag ce cg r = P4 P2 + P5 + P6 = ae + bf s = P1 + P2 = ag + bh t = P3 + P4 = ce + df u = P1 + P5 P3 P7 = cg + dh В этом алгоритме потребовалось 7 матричных умножений и 18 сложений

3 Умножение матриц – алгоритм Штрассена (обсуждение) 1.Как модифицировать алгоритм для случая, когда n не является степенью двойки? Ответ: дополняем исходные матрицы до нужной размерности и обрезаем результат. 2.Что лучше: 8 умножений и 4 сложения или 7 умножений и 18 сложений? Ответ: асимптотически лучше алгоритм Штрассена, но для матриц небольшого размера лучше использовать традиционное умножение. 3.Когда следует на практике применять алгоритм Штрассена? Ответ: для перемножения больших плотных (не разреженных) матриц размерности не меньше 64.