Информационный центр "Центральный Дом Знаний"

ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

cendomzn@yandex.ru

Наш опрос
Как Вы планируете отдохнуть летом? Поеду на море Поеду за границу У бабушки, в деревне... Домашняя я, невыездная:)) Результаты \| Архив опросов Всего ответов: 924

Онлайн всего: 1

Гостей: 1

Пользователей: 0

Форма входа

Алгоритм Штрассена

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы.

В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) = Θ(nlog2 8), А.Ш. умножает матрицы за время Θ(nlog2 7) = Θ(n2.81), что даёт заметный выигрыш на больших плотных матрицах (начиная, примерно, от 64×64).

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

Пусть A, B — две квадратные матрицы над кольцом R. Матрица C получается по формуле:

$\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in R^{2^n \times 2^n}$

Если размер умножаемых матриц n не является натуральной степенью двойки, мы дополняем исходные матрицы дополнительными нулевыми строками и столбцами. При этом мы получаем удобные для рекурсивного умножения размеры, но теряем в эффективности за счёт дополнительных ненужных умножений.

Разделим матрицы A, B и C на равные по размеру блочные матрицы

$\mathbf{A} =\begin{bmatrix}\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\\mathbf{A}_{2,1} & \mathbf{A}_{2,2}\end{bmatrix}\mbox { , }\mathbf{B} =\begin{bmatrix}\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\\mathbf{B}_{2,1} & \mathbf{B}_{2,2}\end{bmatrix}\mbox { , }\mathbf{C} =\begin{bmatrix}\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\\mathbf{C}_{2,1} & \mathbf{C}_{2,2}\end{bmatrix}$

где

$\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in R^{2^{n-1} \times 2^{n-1}}$

тогда

$\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}$

$\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}$

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

Теперь определим новые элементы

$\mathbf{P}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})$

$\mathbf{P}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}$

$\mathbf{P}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})$

$\mathbf{P}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})$

$\mathbf{P}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}$

$\mathbf{P}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})$

$\mathbf{P}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$

которые затем используются для выражения Ci, j. Таким образом, нам нужно всего 7 умножений на каждом этапе рекурсии. Элементы матрицы C выражаются из Pk по формулам

$\mathbf{C}_{1,1} = \mathbf{P}_{1} + \mathbf{P}_{4} - \mathbf{P}_{5} + \mathbf{P}_{7}$

$\mathbf{C}_{1,2} = \mathbf{P}_{3} + \mathbf{P}_{5}$

$\mathbf{C}_{2,1} = \mathbf{P}_{2} + \mathbf{P}_{4}$

$\mathbf{C}_{2,2} = \mathbf{P}_{1} - \mathbf{P}_{2} + \mathbf{P}_{3} + \mathbf{P}_{6}$

Итерационный процесс продолжается n раз, до тех пор пока матрицы Ci, j не выродятся в числа (элементы кольца R). На практике итерации останавливают при размере матриц от 32 до 128 и далее используют обычный метод умножения матриц. Это делают из-за того, что А.Ш. теряет эффективность по сравнению с обычным на малых матрицах из-за дополнительных копирований массивов.

Приведён пример реализации А.Ш. на Фортране. Предполагается, что все матрицы квадратные, их размер является степенью 2.

MODULE STRASSEN_MUL

CONTAINS

! X = A * B

! V - dimension of matrices

RECURSIVE SUBROUTINE MUL(A, B, V, C)

INTEGER, INTENT(IN) :: V

DOUBLE PRECISION, INTENT(IN) :: A( : , : ), B( : , : )

INTEGER :: H ! H = V/2 (see below)

DOUBLE PRECISION, INTENT(OUT) :: C(V, V)

DOUBLE PRECISION, DIMENSION(:,:), ALLOCATABLE :: P1, P2, P3, P4, P5, P6, P7

DOUBLE PRECISION, DIMENSION(:,:), ALLOCATABLE :: A11, A12, A21, A22, B11, B12, B21, B22

IF (V <= 64) THEN ! if dimension equals 64 use MUL2

CALL MUL2 (A, B, V, C)

RETURN

ENDIF

H = V/2

ALLOCATE (P1(H,H), P2(H,H), P3(H,H), P4(H,H), P5(H,H), P6(H,H), P7(H,H))

ALLOCATE (A11(H,H), A12(H,H), A21(H,H), A22(H,H), B11(H,H), B12(H,H), B21(H,H), B22(H,H))

A11 (1:H, 1:H) = A (1:H, 1:H)

A12 (1:H, 1:H) = A (1:H, H+1:V)

A21 (1:H, 1:H) = A (H+1:V, 1:H)

A22 (1:H, 1:H) = A (H+1:V, H+1:V)

B11 (1:H, 1:H) = B (1:H, 1:H)

B12 (1:H, 1:H) = B (1:H, H+1:V)

B21 (1:H, 1:H) = B (H+1:V, 1:H)

B22 (1:H, 1:H) = B (H+1:V, H+1:V)

!$OMP PARALLEL

CALL MUL(A11 + A22, B11 + B22, H, P1) ! P1 = (A11 + A22) * (B11 + B22)

CALL MUL(A21 + A22, B11, H, P2) ! etc. ...

CALL MUL(A11, B12 - B22, H, P3)

CALL MUL(A22, B21 - B11, H, P4)

CALL MUL(A11 + A12, B22, H, P5)

CALL MUL(A21 - A11, B11 + B12, H, P6)

CALL MUL(A12 - A22, B21 + B22, H, P7)

!$OMP END PARALLEL

DEALLOCATE (B11, B12, B21, B22)

DEALLOCATE (A11, A12, A21, A22)

C (1:H, 1:H) = P1 + P4 + P7 - P5

C (1:H, H+1:V) = P3 + P5

C (H+1:V, 1:H) = P2 + P4

C (H+1:V, H+1:V) = P1 - P2 + P3 + P6

DEALLOCATE (P1, P2, P3, P4, P5, P6, P7)

RETURN

END SUBROUTINE MUL

! X = A * B using standard method

SUBROUTINE MUL2 (A, B, V, X)

IMPLICIT NONE

INTEGER, INTENT(IN) :: V

DOUBLE PRECISION, INTENT(IN) :: A( : , : ), B( : , : )

DOUBLE PRECISION, INTENT(OUT), DIMENSION (:,:) :: X

INTEGER :: I, J, K

DO I = 1, V

DO J = 1, V

X (I, J) = 0

DO K = 1, V

X (I, J) = X (I, J) + A (I, K) * B (K, J)

ENDDO

RETURN

END SUBROUTINE MUL2

END MODULE STRASSEN_MUL

Вычисления промежуточных матриц P1 — P7 можно проводить параллельно при использовании таких библиотек как OpenMP или MPI, что позволяет значительно повысить скорость работы алгоритма на многопроцессорных машинах.

Штрассен был первым, кто показал возможность умножения матриц более эффективным способом, чем стандартный. После публикации его работы в 1969 начались активные поиски более быстрого алгоритма. Самым быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за O(n2.375) операций. Существует гипотеза Штрассена о том, что для больших n существует алгоритм перемножение двух матриц размера $n \times n$ за O(n2 + ε) операций.

Существует модификация А.Ш., для которой требуется 7 умножений и 15 сложений (вместо 18 для обычного А.Ш.).

Матрицы A, B и C делятся на блочные подматрицы как показано выше.

Вычисляются промежуточные матрицы S1 — S8, P1 — P7, T1 — T2

$\mathbf{S}_{1} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2})$

$\mathbf{S}_{2} := (\mathbf{S}_{1} - \mathbf{A}_{1,1})$

$\mathbf{S}_{3} := (\mathbf{A}_{1,1} - \mathbf{A}_{2,1})$

$\mathbf{S}_{4} := (\mathbf{A}_{1,2} - \mathbf{S}_{2})$

$\mathbf{S}_{5} := (\mathbf{B}_{1,2} - \mathbf{B}_{1,1})$

$\mathbf{S}_{6} := (\mathbf{B}_{2,2} - \mathbf{S}_{5})$

$\mathbf{S}_{7} := (\mathbf{B}_{2,2} - \mathbf{B}_{1,2})$

$\mathbf{S}_{8} := (\mathbf{S}_{6} - \mathbf{B}_{2,1})$

$\mathbf{P}_{1} := \mathbf{S}_{2} \mathbf{S}_{6}$

$\mathbf{P}_{2} := \mathbf{A}_{1,1} \mathbf{B}_{1,1}$

$\mathbf{P}_{3} := \mathbf{A}_{1,2} \mathbf{B}_{2,1}$

$\mathbf{P}_{4} := \mathbf{S}_{3} \mathbf{S}_{7}$

$\mathbf{P}_{5} := \mathbf{S}_{1} \mathbf{S}_{5}$

$\mathbf{P}_{6} := \mathbf{S}_{4} \mathbf{B}_{2,2}$

$\mathbf{P}_{7} := \mathbf{A}_{2,2} \mathbf{S}_{8}$

$\mathbf{T}_{1} := \mathbf{P}_{1} + \mathbf{P}_{2}$

$\mathbf{T}_{2} := \mathbf{T}_{1} + \mathbf{P}_{4}$

Элементы матрицы C вычисляются по формулам

$\mathbf{C}_{1,1} := \mathbf{P}_{2} + \mathbf{P}_{3}$

$\mathbf{C}_{1,2} := \mathbf{T}_{1} + \mathbf{P}_{5} + \mathbf{P}_{6}$

$\mathbf{C}_{2,1} := \mathbf{T}_{2} - \mathbf{P}_{7}$

$\mathbf{C}_{2,2} := \mathbf{T}_{2} + \mathbf{P}_{5}$

Литература:

Ананий В. Левитин Глава 4. Метод декомпозиции: Умножение больших целых чисел и алгоритм умножения матриц Штрассена // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms — М.: «Вильямс», 2006. — С. 189-195. — ISBN 0-201-74395-7.

Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд Глава 28. Работа с матрицами // Алгоритмы: построение и анализ = Introduction to Algorithms — 2-e издание. — М.: «Вильямс», 2005. — С. 833 - 839. — ISBN 5-8459-0857-4.

Календарь

Архив записей
2010 Август 2010 Сентябрь 2010 Октябрь 2010 Ноябрь 2010 Декабрь 2011 Январь 2011 Февраль 2011 Март 2011 Апрель 2011 Май 2011 Июнь 2011 Июль 2011 Август 2011 Сентябрь 2011 Октябрь 2011 Ноябрь 2011 Декабрь 2012 Январь 2012 Февраль 2012 Ноябрь

Друзья сайта
Заказать курсовую работу! Выполнение любых чертежей Новый фриланс 24

Информационный центр "Центральный Дом Знаний"

Наш опрос

Форма входа

Алгоритм Штрассена

Календарь

Архив записей

Друзья сайта