О математике. ВУЗ

Исследователи определили, что ключом к ускорению является уменьшение количества шагов умножения, максимально снизив этот показатель с n^3 (для стандартного метода). Минимально возможное значение, n^2, в основном равно тому времени, которое требуется "механической" записи результата вычисления. Ученые называют этот показатель ω, где n^ω - это наименьшее количество возможных шагов, необходимых для успешного умножения двух матриц n на n. Первый алгоритм Штрассена дал ω = 2,81

Штрассен использовал ту же идею, чтобы показать, что все большие n на n матрицы также могут быть умножены менее чем за n^3 шага. Ключевым элементом этой стратегии является процедура, называемая декомпозицией — разбиение большой матрицы на последовательно меньшие подматрицы, которые в конечном итоге могут быть размером 2 на 2 или даже 1 на 1. По словам Вирджинии Василевски Уильямс, специалиста по информатике из Массачусетского технологического института и соавтора одной из новых статей, обоснование разделения гигантского массива на крошечные части довольно простое. “Человеку трудно смотреть на большую матрицу (скажем, порядка 100 на 100) и думать о наилучшем возможном алгоритме”, - сказала Василевска Уильямс. Даже матрицы 3 на 3 еще не исследованы полностью. Тем не менее, можно использовать быстрый алгоритм, который уже разработан для небольших матриц, чтобы также получить быстрый алгоритм для больших матриц”.