ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2013, том 53, № 12, с. 1970-1984
УДК 519.614
О БИЛИНЕЙНОЙ СЛОЖНОСТИ И ПРАКТИЧЕСКИХ АЛГОРИТМАХ
УМНОЖЕНИЯ МАТРИЦ
© 2013 г. А. В. Смирнов
(109028 Москва, Хохловский пер., 13, стр. 2., ФБУРФЦСЭ при Минюсте России)
e-mail: S.Alexey.V@rambler.ru Поступила в редакцию 19.03.2013 г.
Переработанный вариант 04.06.2013 г.
Предложен метод расчета билинейных алгоритмов умножения матриц. Получены новые оценки билинейной сложности для ряда задач точного и приближенного умножения прямоугольных матриц. В том числе улучшена оценка граничного ранга для умножения матриц 3 х 3 и предложен практический алгоритм точного умножения квадратных матриц размерности n с асимптотической арифметической сложностью O(n2'7743). Библ. 22. Табл. 6.
Ключевые слова: билинейная сложность, ранг задачи умножения матриц, граничный ранг, алгоритмы точного и приближенного умножения матриц, метод наименьших квадратов, целевая функция.
DOI: 10.7868/S0044466913120168
Прошло более 40 лет с того момента, как Фолькер Штрассен в 1969 г. своим неожиданным результатом (см. [1]) привлек внимание исследователей к задаче быстрого умножения больших матриц. Несмотря на усилия многих математиков и ряд заметных достижений, она доныне (2013 г.) не решена в общем виде. Не доказана и предполагаемая асимптотическая оценка сложности — O(n2 +£), где s > 0 — любое. В настоящее время лучшая теоретическая оценка показателя степени p = 2.373 получена на базе модификаций алгоритма (см. [2]), изначально давшего оценку p = = 2.376. Столь малый прогресс позволяет говорить о "барьере Копперсмита-Винограда" в теоретической оценке сложности. Существенно и то, что данный алгоритм непрактичен в силу астрономической константы в оценке сложности. В работах, посвященных программной реализации практических алгоритмов быстрого умножения, используются алгоритмы с большими показателями степени. В [3] используется алгоритм из [1] с p = 2.8074. В [4] используется предложенный в [5] алгоритм с p = 2.7760 и установлено, что этот алгоритм не дает преимущества в скорости перед алгоритмом на основе [1] вплоть до n = 4640. Поскольку мы рассматриваем и билинейные алгоритмы приближенного умножения матриц для задач с произведением размерностей не более 63, ориентиром для нас будет алгоритм приближенного умножения из [6] с p = 2.7713. В последние годы не отмечено существенного прогресса в исследованиях и заметен спад интереса математиков к этой непростой задаче. Вместе с тем в [7] "разработка алгоритмов умножения матриц с нижней возможной границей сложности" поставлена четвертой по важности задачей среди семи основных проблем вычислительной линейной алгебры. Подробный обзор работ до 1988 г. приведен в [8]. В этой работе незнакомый с проблемой читатель найдет определение билинейных алгоритмов, других используемых в статье терминов и доказательства некоторых свойств билинейных алгоритмов, кратко описанных ниже. Наиболее полный на сегодняшний день обзор литературы по теме можно найти в [9].
В данной статье автор приводит результаты своей попытки численного решения определяющей задачу системы нелинейных уравнений для малых размерностей матриц-сомножителей. Целью работы была оценка билинейных сложностей задач умножения, а также поиск более быстрых практических алгоритмов умножения матриц.
Под практическим алгоритмом далее понимается алгоритм быстрого умножения матриц, который может быть реализован на современных компьютерах, так что при умножении некоторых матриц число арифметических операций будет действительно меньше, чем при использовании классического метода. Так, определенная практичность отделяет класс рассматриваемых авто-
1970
ром алгоритмов от сугубо теоретических конструкций астрономических размерностей и является необходимым, но не достаточным условием практической полезности алгоритма. Реализация практически полезных алгоритмов во всех ее аспектах в данной работе не рассматривается.
Все расчеты проводились с точностью до 15 десятичных цифр на обычном персональном компьютере.
Рассмотрим задачу умножения матрицы размерности п1 х п2 на матрицу размерности п2 х п3. Минимальное число активных умножений в некоммутативном алгоритме, необходимое для перемножения матриц Я = Я(пь п2, п3), называется билинейной сложностью или рангом задачи умножения матриц. Известно, что если все три размерности больше 1, то Я < пхп2п3. Это наряду с тем, что алгоритм применим к любому некоммутативному кольцу элементов, включая матрицы, и позволяет строить алгоритмы быстрого умножения больших матриц (см. [1]).
Рассматриваемые в работе алгоритмы быстрого умножения больших матриц определяются алгоритмами умножения двух матриц малых конкретных размерностей G = АВ с малым числом активных умножений Т (Я < Т< п1п2п3). Эти алгоритмы задаются тремя соответствующими элементам матриц ^ А, В множествами коэффициентов-множителей
у , /1 = 1,2,..., П1, 12 = 1,2,..., Пз, % = 1,2,..., Т,
'¥2' I
"jlj2,
а,-/ = 1,2,..., П1, Л = 1,2,..., п2, % = 1,2,..., Т,
вкк2, к = 1,2,..., П2, к2 = 1,2, ..., Пз, % = 1,2, ..., Т, которые удовлетворяют системе уравнений (см. [10])
Т
(1)
X1
%=1
где
^/1'2/1/2к1к2 _ j2k)^^2k2, Н0,'# А
11, / = Л
Минимальное Т = Я, при котором система (1) имеет решение, является рангом задачи умножения матриц. Нетрудно показать, что функция Я = Я(пъ п2, п3) симметрична и, следовательно, оценки билинейной сложности умножения матриц можно указывать только для задач (иь п2, п3), в которых размерности упорядочены по неубыванию. Характеризуя решения задачи (1), помимо размерностей матриц будем указывать через точку с запятой число членов суммы в левой части (1), называемое длиной решения, не обязательно равное рангу. Далее билинейные алгоритмы умножения двух матриц конкретной размерности, исчерпывающим образом задаваемые корнями системы уравнений (1), в отличие от порождаемых ими алгоритмов умножения больших матриц будем называть решениями.
Известно, что билинейная сложность задачи (2, 2, 2) равна 7 (см. [11]), а задачи (2, 2, 3) равна 11 (см. [12]). Для умножения матриц 3 х 3 в [13], [14] предложены решения (3, 3, 3; 23) с числом ненулевых коэффициентов у, а/, , вкк2, в совокупности равным 153. Для матриц 4 х 4 известно решение (4, 4, 4; 49), которое строится из решения (2, 2, 2; 7). Для матриц 5 х 5 в [15] предложено решение (5, 5, 5; 100).
Для системы (1) возможна ситуация, когда сумма квадратов разностей правых и левых частей может принимать значения, сколь угодно близкие к 0, но решения не существует. Минимальное число слагаемых в (1) г = г(п1, п2, п3), при котором это возможно, называется билинейной сложностью задачи приближенного умножения матриц или граничным рангом. Функциональным решением задачи приближенного умножения матриц назовем такую совокупность функций у/ - (х), аЛЛ(х), вкк(х) действительного аргумента, для которой 51(х) = О(х).
В [16] показано, что г(2, 2, 3) < 10. В [6] приведено функциональное решение (3, 3, 3; 21) такое, что все функции являются одночленами рядов Лорана, и доказано, что г(4 ,4, 4) < 47.
Можно показать (см. [8]), что из любых билинейных решений (п1, п2, п3; г1) и (ть т2, т3; г2) строится билинейное решение с характеристиками (п1т1, п2т2, п3т3; г1 г2). Это решение назовем
композицией или произведением исходных решений. Из решения для умножения прямоугольных матриц нетрудно получить два родственных решения той же длины, циклически переставляя размерности. Если перемножить три таких решения, то из решения для прямоугольных матриц получим решение для квадратных матриц размерности п = пхп2п3. Такая процедура симметризации возможна и для разных прямоугольных решений, например (2, 2, 3; г1) и (3, 3, 2; г2).
Очевидно, что объединение решений (п1, п2, к; г1) и (п1, п2, т; г2), соответствующее объединению вторых сомножителей по столбцам в матрицу большей размерности, дает решение вида (п1, п2, к + т; г1 + г2), которое мы будем называть суммой решений. Пусть имеется решение (п1, 2, к; г1) для задачи частичного умножения матриц (см. [6]), в которой обнулен элемент Ь1к , и решение (п1, 2, т; г2) для задачи, в которой обнулен элемент Ь21. Нетрудно видеть, что эти решения можно просуммировать с наложением столбцов, включающих нулевые элементы, и получить решение (п1, 2, к + т — 1; г1 + г2) для задачи обычного умножения матриц. Такое сведение асимметричных задач к двум задачам меньшей размерности позволило в данной работе существенно улучшить оценки граничных рангов.
Билинейный алгоритм быстрого умножения матриц сводится к последовательному представлению больших матриц в виде матриц малой размерности из элементов-подматриц и рекурсивного использования для их умножения одного или нескольких решений небольшой размерности и малой длины.
Нетрудно видеть (см. [8]), что показатель степени в асимптотической оценке арифметической сложности 0(пр) такого алгоритма умножения квадратных матриц, построенного из одного решения для прямоугольных матриц, вычисляется по формуле
Р = З^^ (/!). (2)
Далее для изложения результатов нам будет достаточно отмеченных выше свойств решений и операций с ними.
Отметим, что число уравнений системы (1) не совпадает с числом ее неизвестных. Заменив парные индексы одинарными, запишем целевую функцию для этой системы уравнений в виде
щ щ2 щ г т л2
^ = ХХХ
I=1 ]=1 к=1 V I=1
(3)
где Щ = п1п3, Щ2 = п1п2, Щ3 = п2п3.
Для данной функции методом наименьших квадратов (МНК) (см. [17]) можно получить систему уравнений пятой степени. Эта система, как легко видеть, распадается на три линейные (матричные) подсистемы относительно каждой группы неизвестных коэффициентов. Решение каждой такой подсистемы является решением частной задачи минимизации целевой функции для соответствующей группы неизвестных при заданных двух других группах. Последовательное итеративное решение этих матричных подсистем является достаточно быстрым процессом, который не увеличивает целевую функцию и при определенных условиях сходится к некоторому решению.
Вычислительный эксперимент показывает, что локальные экстремумы и нижние грани целев
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.