ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 4, с. 550-554
УДК 519.612
БИЛИНЕЙНЫЙ АЛГОРИТМ ДЛИНЫ 22 ДЛЯ ПРИБЛИЖЕННОГО УМНОЖЕНИЯ МАТРИЦ РАЗМЕРОВ 2 х 7 И 7 х 2
© 2015 г. А. В. Смирнов
(109028Москва, Хохловский пер., 13, стр. 2, ФБУ РФЦСЭ) e-mail: S. Alexey.V@rambler.ru Поступила в редакцию 16.06.2014 г. Переработанный вариант 26.08.2014 г.
Представлен билинейный алгоритм приближенного умножения матриц размеров 2 х 7 и 7 х 2 билинейной сложности 22. Дана оценка сверху билинейной сложности задач приближенного умножения матриц 2 х 2 и 2 х n, n > 1. Библ. 16.
Ключевые слова: умножение матриц, быстрый алгоритм умножения матриц, билинейный алгоритм, приближенный билинейный алгоритм, билинейная сложность, длина алгоритма.
Б01: 10.7868/80044466915040171
ВВЕДЕНИЕ
С 60-х годов прошлого века поиск асимптотически быстрых алгоритмов для арифметических и алгебраических операций стал одной из важных задач в математике. И если для умножения чисел задачу удалось решить почти до конца, то с умножением матриц ситуация оказалась намного сложнее.
Пусть обозначает матрицу размера т х п над некоторым полем. Задача умножения мат-
рицы \\а^\тхп на матрицу состоит, по определению, в вычислении тр билинейных форм ви-
ХП
ауЬц. Если вычислять эти формы непосредственно по указанным формулам, то необходимо сделать тпр умножений и почти столько же сложений. При т = п = р всего операций больше, чем п3. В 1969 г. Штрассен (см. [1]) показал, что существуют более быстрые по порядку алгоритмы умножения матриц, построив алгоритм с числом операций над элементами поля
0(п1о827). К 1986 г. эта оценка трудами многих авторов была понижена до 0(п2'38) (см. [2], обзор [3]), однако с тех пор эта оценка существенно не улучшена, несмотря на большой интерес к задаче.
Алгоритм Штрассена из [1] для умножения матриц порядка п со сложностью 0(п1082 7) основан на найденном им алгоритме умножения двух квадратных матриц порядка 2 с семью умножениями вместо восьми в обычном алгоритме. Затем этот алгоритм рекурсивно использовался для умножения матриц порядка 2к с числом умножений 7к. Для того чтобы можно было применять рекурсию, Штрассен построил специального вида алгоритм умножения матриц порядка 2, а именно так называемый билинейный алгоритм.
Определение 1. Пусть ¥ — некоторое кольцо, и пусть имеется 2 множества переменных А = = {аь а2, аг} и В = {Ь1, Ь2, ..., Ь} Билинейными алгоритмами над А, В и кольцом ¥ называются
алгоритмы, в которых сначала вычисляются произведения ^ = ^ а\а{. х вЬ) некоторых
линейных форм (с коэффициентами из ¥) от первого множества переменных на некоторые линейные формы (с коэффициентами из ¥) от второго множества переменных, где I = 1, 2, ..., ё, а на втором этапе вычисляются некоторые линейные комбинации этих произведений
Ск = ^^ 1 ук^. При этом число умножений ё называется билинейной сложностью или длиной алгоритма.
Определение 2. Будем говорить, что билинейный алгоритм над кольцом F вычисляет систему билинейных форм Ck = i ^ . iе^щ bj, k = 1, ..., h, где ск — произвольные константы из F, если
каждая из этих билинейных форм оказывается вычисленной на втором этапе алгоритма. Билинейной сложностью задачи вычисления системы билинейных форм над кольцом Fназывается минимальная билинейная сложность алгоритмов над F, вычисляющих данную систему билинейных форм.
Требование билинейности при изучении сложности умножения матриц связано с тем, что при рекурсии вместо переменных подставляются матрицы, которые могут не коммутировать.
Кроме обычных (точных) билинейных алгоритмов, определенных выше, рассматривают также приближенные билинейные алгоритмы. Интерес к ним связан как с возможностью практического использования, так и с тем фактом, что, имея быстрый приближенный билинейный алгоритм для умножения матриц, можно получать асимптотически быстрый точный алгоритм для умножения матриц (см. [4], [3]).
Напомним, что лорановскими многочленами от переменной x называют выражения, отличающиеся от обычных многочленов тем, что в них разрешаются также целые отрицательные степени x.
Определение 3. Приближенным билинейным алгоритмом над двумя множествами переменных A, B и кольцом F называется любой билинейный алгоритм над теми же множествами переменных, в котором в качестве коэффициентов вместо кольца F используется кольцо лоранов-ских многочленов от x с коэффициентами из F. При этом число умножений линейных форм d также называется билинейной сложностью приближенного алгоритма.
Определение 4. Пусть зафиксированы множества переменных A и B и кольцо F. Будем говорить, что приближенный билинейный алгоритм приближенно вычисляет систему билинейных форм Ck над F, k = 1, ..., h, если на втором этапе этот билинейный алгоритм строит выражения вида Ck + O(x) для всех k = 1, ..., h, где O(x) — многочлены, содержащие только положительные степени x.
Определение 5. Приближенной билинейной сложностью задачи вычисления системы билинейных форм над кольцом F называется минимальная билинейная сложность приближенных билинейных алгоритмов над F, приближенно вычисляющих данную систему билинейных форм.
Из определения видно, что если мы работаем, например, в поле действительных или комплексных чисел, то, выбирая конкретное сколь угодно близкое к 0 число x, мы можем из приближенного билинейного алгоритма получить обычный билинейный алгоритм той же сложности, сколь угодно точно вычисляющий заданную систему билинейных форм. При этом выбор x = 0 может оказаться запрещенным из-за наличия в коэффициентах отрицательных степеней x.
Выше отмечено, что уже более 20 лет не удается существенно улучшить результат O(n2'38) Коп-персмита и Винограда для сложности умножения матриц порядка n. В связи с этим возникает необходимость рассмотрения различных подходов к разработке быстрых алгоритмов умножения матриц. В частности, интересно исследовать (для последующих обобщений), как устроены алгоритмы умножения матриц малых размеров с малой сложностью и как их можно строить. Отметим, что полученный в работе результат позволяет лучше понять ситуацию в данной области, но не дает непосредственно улучшений в сложности умножения больших матриц.
Несмотря на простоту постановки, задача определения билинейной сложности умножения двух матриц оказывается тяжелой даже при малых размерах матриц. Так, Виноград (см. [5]) показал, что билинейная сложность задачи умножения двух матриц порядка 2 равна 7. А про билинейную сложность задачи умножения двух матриц порядка 3 над любым полем известно только, что она не больше 23 (см. [6]) и не меньше 19 (см. [7]). Имеются также некоторые общие нижние и верхние оценки для билинейной сложности умножения двух матриц порядка n и некоторые верхние оценки для точной и приближенной билинейной сложности умножения матриц конкретных порядков. В [8] построен приближенный билинейный алгоритм для умножения двух матриц порядка 3 (над произвольным полем) с билинейной сложностью 21 (см. также [3]), а в [9] — алгоритм с приближенной билинейной сложностью 20.
Поскольку билинейный алгоритм является частным случаем приближенного билинейного алгоритма, то для любой задачи приближенная билинейная сложность не больше, чем билинейная сложность. Известно, что приближенная билинейная сложность может быть меньше, чем билинейная сложность (см. [10]—[12], [3]).
Если необходимо умножить матрицу размера 2 х 2 на матрицу размера 2 х n, то можно разбить вторую матрицу на блоки размера 2 х 2; при n нечетном последний блок будет иметь размер 2 х 1.
Тогда умножение исходных матриц сведется к \_п/2 J умножениям матриц порядка 2 и (при п нечетном) к умножению матрицы размера 2 х 2 на матрицу размера 1 х 2 (и некоторым сложениям). Из результата Штрассена легко вытекает, что для этого достаточно [7п/2"| умножений, т.е. мы получаем билинейный алгоритм с билинейной сложностью [7п/ 2~|. Хопкрофт и Керр (см. [13]) показали, что эту оценку нельзя понизить для задачи умножения таких матриц над полем из 2 элементов. Для произвольных полей и произвольных п неизвестно, является ли эта оценка неулучшаемой.
Отметим, что все результаты допускают обобщение с использованием двойственности. Задачу умножения матрицы размера т х п на матрицу размера п х р можно задать тройкой чисел т, п, р. Теорема о двойственности (см. [14], [3]) утверждает, что билинейная сложность и приближенная билинейная сложность не изменяются при любых перестановках чисел т, п, р. При перестановке размерностей задачи билинейный алгоритм ее решения строится перестановками и транспонированием матриц коэффициентов исходного билинейного алгоритма. Далее, характеризуя билинейный алгоритм четверкой чисел (т, п, р; г), где г — билинейная сложность или длина алгоритма, будем иметь в виду все три алгоритма, порождаемых перестановками размерностей.
Известно также, что задачу построения билинейного алгоритма можно сформулировать в трилинейной форме и свести к решению нелинейной системы уравнений Брента (см. [15]) относительно коэффициентов алгоритма. В [9] предложен численный, частично эвристический метод подбора решений этой системы с рациональными корнями и большим количеством нулей как для точного, так и для приближенного случая. Найдены несколько новых точных и приближенных билинейных алгоритмов малой длины для задач умножения прямоугольных матриц, и выдвинуты гипотезы о существовании ряда приближенных алгоритмов, в частности (2, 2, 6; 19) и (2, 2, 7; 22). В [16] численным методом найден приближенный алгоритм (2, 2, 6; 19). В данной работе представлен приближенный алгоритм (2, 2, 7; 22).
АЛГОРИТМ
Рассмотрим задачу умножения матрицы А = ||а;у|| 2х4 на матрицу В = ||аи|| 4х2 с обнуленным элементом а11 в первом сомножителе. Нетрудно видеть, что если имеется билинейный алгоритм Z1 для решения этой задачи, то его можно преобразовать в билинейный алгоритм Z2 той же длины для умножения тех же матриц, но с обнуленным элементом а24. Для этого надо перенумеровать коэффициенты алгоритма в соответствии с перестановкой в А строк и первого, и четвертого столбца, а в В — столбцов и первой, и четвертой строки.
Разрежем мат
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.