В линейной алгебре , то Strassen алгоритм , названный в честь Volker Strassen , является алгоритм умножения матриц . Он быстрее, чем стандартный алгоритм умножения матриц, и полезен на практике для больших матриц, но будет медленнее, чем самые быстрые известные алгоритмы для очень больших матриц.
Алгоритм Штрассена работает для любого кольца , такого как плюс / умножение, но не для всех полуколец , таких как мин-плюс или логическая алгебра , где наивный алгоритм все еще работает, и так называемое комбинаторное матричное умножение .
История
Фолькер Штрассен впервые опубликовал этот алгоритм в 1969 году и доказал, что общий алгоритм умножения матриц n 3 не является оптимальным. [1] алгоритм Strassen лишь немного лучше , чем это, но его публикация привела к гораздо больше исследований о умножении матриц , что привело к более быстрым подходам, такие как алгоритм Медник-Виноград .
Алгоритм
Пусть A , B - две квадратные матрицы над кольцом R , например матрицы, элементы которых являются целыми или действительными числами. Мы хотим вычислить матричное произведение C как
В следующем изложении алгоритма мы будем предполагать, что все эти матрицы имеют размеры, равные степени двойки (т. Е. ), но это необходимо только концептуально - если матрицы A , B не относятся к типу 2 n × 2 n, мы можем концептуально подумать о заполнении "недостающих" строк и столбцов нулями для получения матриц с размерами степеней двойки - - хотя реальные реализации алгоритма, конечно, не делают этого на практике.
Затем мы разбиваем A , B и C на блочные матрицы одинакового размера
с участием
- .
Наивный алгоритм был бы таким:
С помощью этой конструкции мы не уменьшили количество умножений. Нам все еще нужно 8 умножений матричных блоков, чтобы вычислить матриц, то же количество умножений, которое нам нужно при использовании стандартного умножения матриц.
Вместо этого алгоритм Штрассена определяет новые матрицы:
только используя 7 умножений (по одному на каждое ) вместо 8. Теперь мы можем выразить с точки зрения :
Мы рекурсивно повторяем этот процесс деления до тех пор, пока подматрицы не выродятся в числа (элементы кольца R ). Если, как упоминалось выше, исходная матрица имела размер, не равный степени 2, то в результирующем продукте будут нулевые строки и столбцы, такие же, как A и B , и они будут затем удалены в этот момент для получения (меньшего ) матрица C нам очень нужна.
Практические реализации алгоритма Штрассена переключаются на стандартные методы умножения матриц для достаточно малых подматриц, для которых эти алгоритмы более эффективны. Конкретная точка пересечения, для которой алгоритм Штрассена более эффективен, зависит от конкретной реализации и оборудования. Ранее авторы подсчитали, что алгоритм Штрассена быстрее для матриц с шириной от 32 до 128 для оптимизированных реализаций. [2] Однако было замечено, что эта точка пересечения увеличивалась в последние годы, и исследование 2010 года показало, что даже один шаг алгоритма Штрассена часто не приносит пользы для текущих архитектур по сравнению с высокооптимизированным традиционным умножением, пока размеры матрицы превышают 1000 или более, и даже для размеров матрицы в несколько тысяч выигрыш обычно в лучшем случае незначителен (около 10% или меньше). [3] В более недавнем исследовании (2016 г.) наблюдались преимущества для матриц размером от 512 до около 20%. [4]
Асимптотическая сложность
Схема приведенного выше алгоритма показала, что можно обойтись всего 7 вместо традиционных 8 умножений матрица-матрица для подблоков матрицы. С другой стороны, нужно выполнять сложение и вычитание блоков, хотя это не влияет на общую сложность: для сложения матриц размера N / 2 требуется всего ( N / 2) 2 операции, тогда как умножение значительно дороже (традиционно 2 ( N / 2) 3 ) операции сложения или умножения).
Тогда возникает вопрос, сколько операций требуется для алгоритмов Штрассена и как это соотносится со стандартным умножением матриц, которое требует приблизительно 2 N 3 (где N = 2 n ) арифметических операций, то есть асимптотическую сложность Θ ( N 3 ) .
Количество сложений и умножений, требуемых в алгоритме Штрассена, можно вычислить следующим образом: пусть f ( n ) будет количеством операций для матрицы 2 n × 2 n . Затем с помощью рекурсивного применения алгоритма Штрассены, мы видим , что п ( п ) = 7 п ( п - 1) + ℓ 4 п , для некоторых постоянная л , который зависит от количества добавок проводили при каждом применении алгоритма. Следовательно, f ( n ) = (7 + o (1)) n , т. Е. Асимптотическая сложность умножения матриц размера N = 2 n с использованием алгоритма Штрассена составляет
- .
Сокращение числа арифметических операций , однако идет по цене несколько уменьшенных численной устойчивости , [5] и алгоритм также требует значительно больше памяти по сравнению с наивным алгоритмом. Обе исходные матрицы должны иметь свои размеры, расширенные до следующей степени 2, что приводит к хранению в четыре раза большего количества элементов, а каждая из семи вспомогательных матриц содержит четверть элементов в расширенных.
Алгоритм Штрассена необходимо сравнить с «наивным» способом выполнения матричного умножения, который потребовал бы 8 вместо 7 умножений подблоков. Тогда это вызовет сложность, которую можно ожидать от стандартного подхода:
- .
Сравнение этих двух алгоритмов показывает, что асимптотически алгоритм Штрассена быстрее: существует порог размера N, так что матрицы большего размера более эффективно умножаются с помощью алгоритма Штрассена, чем «традиционный» способ. Однако из асимптотического утверждения не следует, что алгоритм Штрассена всегда быстрее даже для небольших матриц, и на практике это не так: для небольших матриц стоимость дополнительных добавлений матричных блоков перевешивает экономию на количестве умножения. Существуют также другие факторы, не отраженные в приведенном выше анализе, например, разница в стоимости современного оборудования между загрузкой данных из памяти на процессоры и стоимостью фактического выполнения операций с этими данными. Вследствие такого рода соображений алгоритм Штрассена обычно используется только для «больших» матриц. Этот вид эффекта еще более выражен с альтернативными алгоритмами, такими как алгоритм Копперсмита и Винограда : хотя асимптотически даже быстрее, пороговое значение точки пересечения N настолько велико, что алгоритм обычно не используется для матриц, с которыми можно столкнуться на практике.
Ранговая или билинейная сложность
Сложность билинейная или ранг из билинейной карты является важным понятием в асимптотической сложности умножения матриц. Ранг билинейного отображениянад полем F определяется как (что-то вроде злоупотребления обозначениями )
Другими словами, ранг билинейного отображения - это длина его кратчайшего билинейного вычисления. [6] Существование алгоритма Штрассена показывает, что ранг умножения матриц 2 × 2 не превышает семи. Чтобы убедиться в этом, представим этот алгоритм (наряду со стандартным алгоритмом) как такое билинейное вычисление. В случае матриц двойственные пространства A * и B * состоят из отображений в поле F, индуцированных скалярным произведением с двумя точками (т. Е. В данном случае суммой всех элементов произведения Адамара ).
Стандартный алгоритм | Алгоритм Штрассена | ||||||
я | f я ( а ) | г я ( б ) | w я | f я ( а ) | г я ( б ) | w я | |
1 | |||||||
2 | |||||||
3 | |||||||
4 | |||||||
5 | |||||||
6 | |||||||
7 | |||||||
8 | |||||||
Можно показать, что общее количество элементарных умножений L, необходимых для умножения матриц, строго асимптотически связано с рангом R , т. Е., или более конкретно, поскольку константы известны, Одним из полезных свойств ранга является то, что он является субмультипликативным для тензорных произведений , и это позволяет показать, что умножение матриц 2 n × 2 n × 2 n может быть выполнено не более чем с 7 n элементарными умножениями для любого n . (Это n- кратное тензорное произведение карты умножения матриц 2 × 2 × 2 на себя - n- я тензорная степень - реализуется рекурсивным шагом в показанном алгоритме.)
Поведение кеша
Алгоритм Штрассена не обращает внимания на кэш . Анализ алгоритма поведения кеша показал, что
промахи кеша во время его выполнения, предполагая, что идеализированный кеш размером M (т.е.линии длины б ). [7] : 13
Соображения по реализации
В приведенном выше описании указано, что матрицы квадратные, размер - степень двойки, и что при необходимости следует использовать заполнение. Это ограничение позволяет рекурсивно разделять матрицы пополам до тех пор, пока не будет достигнут предел скалярного умножения. Ограничение упрощает объяснение и анализ сложности, но на самом деле не является необходимым; [8], и фактически заполнение матрицы, как описано, увеличит время вычислений и может легко устранить довольно небольшую экономию времени, полученную при использовании этого метода в первую очередь.
В хорошей реализации будет соблюдаться следующее:
- Нет необходимости или нежелательно использовать алгоритм Штрассена до предела скаляров. По сравнению с обычным умножением матриц, алгоритм добавляет значительнуюнагрузка на сложение / вычитание; поэтому ниже определенного размера будет лучше использовать обычное умножение. Таким образом, например, 1600x1600 не нужно дополнять до 2048x2048, так как его можно разделить до матриц 25x25, и затем на этом уровне можно использовать обычное умножение.
- Этот метод действительно может быть применен к квадратным матрицам любой размерности. [3] Если размер четный, они делятся пополам, как описано. Если размер нечетный, сначала применяется нулевое заполнение одной строкой и одним столбцом. Такое заполнение может применяться "на лету" и "лениво", а лишние строки и столбцы отбрасываются по мере формирования результата. Например, предположим, что матрицы имеют размер 199x199. Их можно разделить так, чтобы верхняя левая часть имела размер 100x100, а нижняя правая - 99x99. Везде, где этого требуют операции, размеры 99 сначала дополняются нулями до 100. Обратите внимание, например, что продуктиспользуется только в нижней строке вывода, поэтому его высота должна составлять всего 99 строк; и, таким образом, левый факториспользуется для его создания, его высота должна составлять всего 99 строк; соответственно, нет необходимости дополнять эту сумму до 100 строк; нужно только набить до 100 столбцов для соответствия .
Кроме того, нет необходимости в том, чтобы матрицы были квадратными. Неквадратные матрицы можно разделить пополам с помощью тех же методов, в результате чего будут получены неквадратные матрицы меньшего размера. Если матрицы достаточно неквадратные, будет целесообразно сократить начальную операцию до большего количества квадратных произведений, используя простые методы, которые по сути, например:
- Продукт размером [2 N x N ] * [ N x 10 N ] может быть выполнен как 20 отдельных операций [ N x N ] * [ N x N ], упорядоченных для формирования результата;
- Продукт размером [ N x 10 N ] * [10 N x N ] может быть выполнен как 10 отдельных операций [ N x N ] * [ N x N ], суммированных для формирования результата.
Эти методы сделают реализацию более сложной по сравнению с простым заполнением до квадрата степени двойки; однако разумно предположить, что любой, кто реализует умножение Штрассена, а не обычное умножение, будет уделять больше внимания эффективности вычислений, чем простоте реализации.
На практике алгоритм Штрассена может быть реализован для достижения лучшей производительности, чем обычное умножение, даже для небольших матриц, для матриц, которые совсем не квадратные, и без необходимости рабочего пространства за пределами буферов, которые уже необходимы для высокопроизводительного обычного умножения. [4]
Смотрите также
- Вычислительная сложность математических операций
- Исключение Гаусса – Жордана
- Алгоритм Копперсмита – Винограда
- Матричное представление Z-порядка
- Алгоритм Карацубы , для умножения n- значных целых чисел в вместо в время
- Алгоритм Тоома-Кука , более быстрое обобщение алгоритма Карацубы, которое позволяет рекурсивное разложение по принципу разделяй и властвуй на более чем 2 блока за раз
- Алгоритм комплексного умножения Гаусса умножает два комплексных числа, используя 3 действительных умножения вместо 4
Рекомендации
- ^ Штрассен, Фолькер (1969). «Исключение по Гауссу не оптимально». Нумер. Математика . 13 (4): 354–356. DOI : 10.1007 / BF02165411 . S2CID 121656251 .
- ^ Скиена, Стивен С. (1998), «§8.2.3 Умножение матриц», Руководство по проектированию алгоритмов , Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-94860-7.
- ^ а б Д'Альберто, Паоло; Николау, Александру (2005). Использование рекурсии для повышения производительности ATLAS (PDF) . Шестой международный симпозиум. по высокопроизводительным вычислениям.
- ^ а б Хуанг, Цзяньюй; Смит, Тайлер; Генри, Грег; ван де Гейн, Роберт (2016). Перезагрузка алгоритма Штрассена . Международная конференция по высокопроизводительным вычислениям, сетям, хранению данных и анализу (SC'16).
- ^ Уэбб, Миллер (1975). «Вычислительная сложность и численная устойчивость». SIAM J. Comput . 4 (2): 97–107. DOI : 10.1137 / 0204009 .
- ^ Burgisser; Clausen; Шокроллахи (1997). Алгебраическая теория сложности . Springer-Verlag. ISBN 3-540-60582-7.
- ^ Frigo, M .; Лейзерсон, CE ; Прокоп, Х .; Рамачандран, С. (1999). Алгоритмы без учета кеширования (PDF) . Proc. IEEE Symp. по основам информатики (FOCS). С. 285–297.
- ^ Хайэм, Николас Дж. (1990). «Использование быстрого умножения матриц в BLAS уровня 3» (PDF) . Транзакции ACM на математическом ПО . 16 (4): 352–368. DOI : 10.1145 / 98267.98290 . ЛВП : 1813/6900 . S2CID 5715053 .
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Глава 28: Раздел 28.2: Алгоритм Штрассена для умножения матриц, стр. 735–741.
Внешние ссылки
- Вайсштейн, Эрик В. «Формулы Штрассена» . MathWorld .(также включает формулы для быстрого обращения матриц )
- Тайлер Дж. Эрнест, Алгоритм Штрассена на ядре широкополосной сотовой связи