Гипотеза Штрассена

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

Точная формулировка

Для сколь угодно малого \varepsilon > 0 существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера n \times n за {\rm O}(n^{2+\varepsilon}) операций.

История

Задача перемножения двух больших квадратных матриц часто встречается на практике — этим объясняется практическая ценность гипотезы. Поскольку умножение чисел есть операция более трудоёмкая, чем сложение, то при оценке сложности алгоритма перемножения матриц учитывают только количество умножений. Очевидно, что две матрицы размера n \times n можно перемножить за n3 умножений и n2(n-1) сложений; очевидно также, что нельзя сделать степень n меньше 2 (т.к. в таких матрицах n2 значений, и все их надо обработать). Однако хотелось бы сократить количество производимых умножений (возможно, за счёт увеличения количества сложений). В 1969 году немецкий учёный Штрассен предложил более быстрый алгоритм, который требовал {\rm O}(n^{\log_2 7}) \approx {\rm O}(n^{2,807}) умножений. В 1982 году было доказано, что достаточно O(n2,376) операций (алгоритм Копперсмита—Винограда), хотя предложенный ими алгоритм редко используется на практике и имеет скорее теоретическое значение.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home