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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

В отличие от традиционного алгоритма умножения матриц (по формуле ), работающего за время , алгоритм Штрассена умножает матрицы за время , что даёт выигрыш на больших плотных матрицах.

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

Описание алгоритма[править | править код]

Для умножения (2x2)-матриц используются произведения сумм и разностей элементов. На иллюстрации каждое такое произведение взято в отдельную цветную рамку, а способ их компоновки в финальную матрицу обозначен исходящими лучами.

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

Пусть – матрицы размера . Их можно представить как блочные матрицы размера из –матриц:

По принципу блочного умножения, матрица выражается через их произведение

где в правой части происходит восемь умножений матриц размера . Поскольку матрицы образуют кольцо, то для вычисления правой части годится любой алгоритм умножения -матриц, использующий лишь сложения, вычитания и умножения. Штрассен предложил такой алгоритм с семью умножениями:

Каждое умножение можно совершать рекурсивно по той же процедуре, а сложение – тривиально, складывая элементов. Тогда время работы алгоритма оценивается через рекуррентное соотношение:

Пример реализации[править | править код]

Ниже приведён пример реализации алгоритма на языке Python с использованием библиотеки NumPy для быстрого взятия подматриц. Основная функция – strassen_mul. Предполагается, что все матрицы квадратны, представлены типом numpy.array и их размер является степенью 2.

При небольших размерах матрицы прямое умножение оказывается быстрее алгоритма Штрассена из-за большого числа сложений в последнем. Граница таких размеров зависит от соотношения времени сложения и умножения элементов и поэтому может варьироваться в зависимости от аппаратной среды. В коде за её назначение отвечает константа TRIVIAL_MULTIPLICATION_BOUND.

from itertools import product
import numpy as np

def split_to_2x2_blocks(matrix):
	return list(map(
		lambda row: np.hsplit(row, 2),
		np.vsplit(matrix, 2)
	))

def strassen_mul_2x2(lb, rb):
	d = strassen_mul(lb[0][0] + lb[1][1], rb[0][0] + rb[1][1])
	d_1 = strassen_mul(lb[0][1] - lb[1][1], rb[1][0] + rb[1][1])
	d_2 = strassen_mul(lb[1][0] - lb[0][0], rb[0][0] + rb[0][1])

	left = strassen_mul(lb[1][1], rb[1][0] - rb[0][0])
	right = strassen_mul(lb[0][0], rb[0][1] - rb[1][1])
	top = strassen_mul(lb[0][0] + lb[0][1], rb[1][1])
	bottom = strassen_mul(lb[1][0] + lb[1][1], rb[0][0])

	return [[d + d_1 + left - top, right + top],
			[left + bottom, d + d_2 + right - bottom]]

def trivial_mul(left, right):
	height, mid_size = left.shape
	mid_size, right = right.shape

	result = np.zeros((height, width))
	for row, col, mid in product(*map(range, [height, width, mid_size])):
		result[row][col] += left[row][mid] * right[mid][col]

	return result

TRIVIAL_MULTIPLICATION_BOUND = 8

def strassen_mul(left, right):
	assert(left.shape == right.shape)
	assert(left.shape[0] == left.shape[1])

	if left.shape[0] <= TRIVIAL_MULTIPLICATION_BOUND:
		return trivial_mul(left, right)

	assert(left.shape[0] % 2 == 0)
	return np.block(
		strassen_mul_2x2(*map(split_to_2x2_blocks, [left, right]))
	)

Дальнейшее развитие[править | править код]

Штрассен был первым, кто показал возможность умножения матриц более эффективным способом, чем стандартный. После публикации его работы в 1969 начались активные поиски более быстрого алгоритма. Самым асимптотически быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за операций[1], предложенный в 1987 году и усовершенствованный в 2011 году до уровня [1]. Этот алгоритм не представляет практического интереса в силу астрономически большой константы в оценке арифметической сложности. Вопрос о предельной в асимптотике скорости перемножения матриц не решен. Существует гипотеза Штрассена о том, что для достаточно больших существует алгоритм перемножения двух матриц размера за операций, где сколь угодно малое наперед заданное положительное число. Эта гипотеза имеет сугубо теоретический интерес, так как размер матриц, для которых действительно мало, по всей видимости очень велик.

Вопрос о построении наиболее быстрого и устойчивого практического алгоритма умножения больших матриц также остается нерешённым.

Алгоритм Винограда — Штрассена[править | править код]

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

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

Вычисляются промежуточные элементы

Элементы матрицы вычисляются следующим образом:

Примечания[править | править код]

  1. 1 2 Математики преодолели барьер Копперсмита-Винограда. lenta.ru (12 декабря 2011). Дата обращения: 12 декабря 2011.

Литература[править | править код]