Cтраница 1
Алгоритм Штрассена работает с квадратными матрицами. На самом деле он настолько эффективен, что иногда разумно расширить матрицы до квадратных, и при этом он все равно дает выигрыш, превышающий расходы на введение дополнительных элементов. [1]
Приведем здесь алгоритм Штрассена, поскольку он является основой многих последующих результатов. [2]
На практике алгоритм Штрассена применяется редко: его использование требует аккуратного отслеживания рекурсии. Важность его состоит в том, что это первый алгоритм, умножение матриц с помощью которого требует менее, чем О ( ЛГ3) операций. Работа над повышением эффективности матричного умножения и поиском возможных нижних оценок его сложности продолжается. [3]
Нетрудно видеть, что алгоритм Штрассена для умножения двух матриц порядка 2 является билинейным. Очевидное обобщение конструкции Штрассена приводит к следующей теореме. [4]
Для умножения 2 х 2-матриц алгоритм Штрассена использует семь формул. Эти формулы чрезвычайно неестественны и, к сожалению, в оригинальной статье Штрассена не объясняется, как он пришел к ним. Замечательно, что как сами формулы, так и их использование не требуют, чтобы умножение элементов матриц было коммутативным. [5]
Для достаточно больших значений п применение алгоритма Штрассена приводит к методу, имеющему меньшее число операций. Он требует порядка п2 - сложений и умножений. В настоящее время проводится теоретическое изучение и экспериментирование по вопросу о том, насколько выгоден этот новый алгоритм на практике. [6]
Отметим также, что для умножения матриц может быть применен алгоритм Штрассена или Купершмидта и Винограда. [7]
OA ( log7) - Использование же 18 сложений в алгоритме Штрассена не влияет на асимптотику. На первом уровне рекурсии для алгоритма Штрассена 7 умножений ( ( и / 2) X ( л / 2)) - матриц по мере роста п становятся гораздо сложнее, чем 18 ( или любое другое число) сложений и вычитаний матриц того же размера. [8]
Но для того, чтобы выяснить, для каких значений п алгоритм Штрассена работает быстрее обычного алгоритма, надо найти соответствующую мультипликативную постоянную. Однако если п не является степенью числа 2, то простое вложение каждой исходной матрицы в матрицу, порядок которой равен степени числа 2, ближайшей к п сверху, даст слишком большую постоянную. [9]
Можно ли находить кратчайшие пути меньше, чем за 0 ( п3) шагов. Алгоритм Штрассена неприменим к замкнутым полукольцам, состоящим из неотрицательных вещественных чисел и оо, но, может быть, удастся свести операции в этом замкнутом полукольце к операциям в некотором кольце, как это было сделано для булевых матриц. [10]
OA ( log7) - Использование же 18 сложений в алгоритме Штрассена не влияет на асимптотику. На первом уровне рекурсии для алгоритма Штрассена 7 умножений ( ( и / 2) X ( л / 2)) - матриц по мере роста п становятся гораздо сложнее, чем 18 ( или любое другое число) сложений и вычитаний матриц того же размера. [11]
Матрица Р - [ вычисляется легко, а для вычисления U - l и L - l можно использовать алгоритм Штрассена, который в этом случае работает корректно. Было показано, что если задача об умножении матриц порядка п имеет сложность 0 ( па), где а 2, то для задачи построения НВП-разложения для матрицы порядка п существует арифметический алгоритм со сложностью 0 ( па), в котором во всех операциях деления делитель отличен от 0, если исходная матрица невырожденна. [12]
При умножении двух 2 х 2-матриц алгоритм выполняет 7 умножений и 18 сложений. Экономия не видна: мы получили 14 сложений в обмен на одно умножение в стандартных алгоритмах. При умножении двух 16 х 16-матриц алгоритм Штрассена экономит 1677 умножений за счет дополнительных 9138 сложений. [13]
Хопкрофт, Керр [1971] показали, что для вычисления произведения ( 2 X 2) - матриц над произвольным кольцом необходимы семь умножений. Однако рекурсивный алгоритм может быть основан на умножении матриц какого-нибудь другого небольшого размера. Например, можно было бы улучшить порядок алгоритма Штрассена, если суметь перемножать ( 3 X 3) - матрицы за 21 умножение или ( 4 X 4) - матрицы за 48 умножений. [14]