Об алгоритмах умножения матриц

[Xaositect]

Linkey в сообщении #892297 писал(а):

А числа целые, рациональные или действительные?

В данном случае неважно, оба этих факта верны над любым кольцом.

[patzer2097]

Xaositect в сообщении #892287 писал(а):

Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.

Интересные результаты, сама по себе задача интересна, конечно
Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8

Кстати, чтобы задача про минимизацию числа умножений стала осмысленной, нужно ставить вопрос уже над не обязательно коммутативным кольцом, - иначе как решение может помочь строить быстрые алгоритмы?

[Munin]

patzer2097 в сообщении #892395 писал(а):

не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8

Почему бы и нет?

[Xaositect]

patzer2097 в сообщении #892395 писал(а):

Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8

Ну это да. Но вот уже для комплексных матриц 2x2 умножение действительно дороже сложения и можно попробовать Штрассена.

UPD. Хотя нет, все равно получается дороже в простой модели с одинаковой ценой сложения и умножения действительных чисел.
Но суть понятна, мало ли что там у нас в матрице может быть, может там многочлены какие или длинные числа.

-- Пт авг 01, 2014 20:12:48 --

patzer2097 в сообщении #892395 писал(а):

Кстати, чтобы задача про минимизацию числа умножений стала осмысленной, нужно ставить вопрос уже над не обязательно коммутативным кольцом, - иначе как решение может помочь строить быстрые алгоритмы?

Да. Для этого случая, кстати, алгоритма со сложностью 22 для 3x3 неизвестно, только 23. А чтобы получить улучшение по сравнению со Штрассеном, надо 21.

[patzer2097]

Xaositect в сообщении #892403 писал(а):

А чтобы получить улучшение по сравнению со Штрассеном, надо 21.

Я тоже об этом подумал, - получается, пока $3\times3$ матрицы люди умеют умножать довольно плохо А не дадите ссылку на какой-нибудь обзор с такого типа результатами?

Xaositect в сообщении #892403 писал(а):

Но суть понятна, мало ли что там у нас в матрице может быть, может там многочлены какие или длинные числа.

...или матрицы порядка $10^6$
кстати, несмотря на обратные примеры - где умножение дороже сложения - задачу об минимизации числа сложений обычно не рассматривают (хотя тут я наверняка неправ; впрочем, в любом случае внимания этой задаче уделяют меньше)

[Xaositect]

patzer2097 в сообщении #892419 писал(а):

Я тоже об этом подумал, - получается, пока $3\times3$ матрицы люди умеют умножать довольно плохо А не дадите ссылку на какой-нибудь обзор с такого типа результатами?

По алгоритмам умножения малых матриц - http://www.sciencedirect.com/science/ar ... 7510007036
По нижним оценкам обзор не припомню, можно посмотреть http://www.sciencedirect.com/science/ar ... 4X02000079 , http://arxiv.org/abs/1211.6320 - текущие лучшие оценки.

По асимптотическим верхним оценкам - http://theoryofcomputing.org/articles/gs005/
По недавним результатам об улучшении алгоритма Копперсмита-Винограда - http://arxiv.org/abs/1401.7714

[patzer2097]

Спасибо!!

[Xaositect]

patzer2097 в сообщении #892419 писал(а):

кстати, несмотря на обратные примеры - где умножение дороже сложения - задачу об минимизации числа сложений обычно не рассматривают (хотя тут я наверняка неправ; впрочем, в любом случае внимания этой задаче уделяют меньше)

Эта задача значительно более сложная, там нет какой-то хорошей алгебры.
Для 2x2 известно, что 15 сложений минимально для 7 умножений, но там множество всех алгоритмов имеет очень хорошую алгебраическую структуру - если матрицы 2x2 рассматривать, как линейные операторы, то все алгоритмы ранга 7 получаются из алгоритма Штрассена заменой базисов в трех рассматриваемых двумерных пространствах.

[Boss03]

К сожалению, в вещественной области для больших перемножаемых матриц хотя и можно достичь впечатляющих результатов на практике в части скорости перемножения, но при этом также впечатляюще будет падать и точность расчетов. Здесь важны разумные компромиссы между скоростью расчета и требуемой точностью. Хочу отметить, что алгоритм Штрассена замечательно вписывается в парадигму современной архитектуры процессоров в части эффективного использования его кэша, что приводит в совокупности к увеличению скорости расчетов для больших матриц в десятки и сотни раз по сравнению с наколенными алгоритмаими перемножения матриц.

[Boss03]

В связи с замечанием о падении точности при использовании быстрых алгоритмов умножения больших матриц наблюдается следующий парадокс: скорость алгоритмов типа Штрассена с четверной точностью для получения двойной точности превышает скорость лучших оптимизированных алгоритмов двойной точности.

[patzer2097]

Xaositect, спасибо за ссылки! Я хотел еще вот чем поинтересоваться: видели ли Вы вот эту работу? Автор утверждает, что умеет умножать матрицы с экспонентой, меньшей $2.3730$, причем его оценки в конце работы кажутся довольно грубыми и выглядят так, что он решил "зафиксировать преимущество" в $0.003$ перед Копперсмитом-Виноградом и точнее свой метод, чем до тысячных, анализировать не стал. Впрочем, его результат и так с запасом выигрывает и у результата Стотерса, который Википедия считает лучшим на тот момент.

1. Видел ли эту работу вообще кто-нибудь из специалистов и почему ее абсолютно никто не цитирует?
2. С работой что-то не так? (Ну, помимо уровня журнала, в котором она появилась)
3. И другой вопрос - почему упомянутая Вами работа Ле Галла с $\omega<2.3728639$ считается лучшей на данный момент, ведь еще в 2012 году (причем на конференции топ-уровня) была представлена работа с $\omega<2.3727$?

Буду благодарен, если хотя бы на один из вопросов у Вас найдется ответ

[Xaositect]

patzer2097 в сообщении #892779 писал(а):

1. Видел ли эту работу вообще кто-нибудь из специалистов и почему ее абсолютно никто не цитирует?

Я точно помню, что цитировал, и действительно: http://scholar.google.com/scholar?q=lin ... us/fpm1404 :) Странно, что названия у русской и английской статьи так отличаются. Не знаю, знает ли о ней кто-то из зарубежных специалистов.
Сам я узнал об этой работе вскоре после результата Вассилевской-Вильямс, Д.В.Жданович делал доклад на нашем семинаре. Насколько я знаю, до публикации Вассилевской-Вильямс работа не считалась таким уж серьезным прорывом, потому что идея та же самая, что и у Копперсмита-Винограда, только за счет прогресса в скорости вычислений удалось провести анализ 4 и 8 степени тензора вместо второй. Примерно то же самое говорит Блезер по поводу работы Стотерса: http://www.scottaaronson.com/blog/?p=839#comment-34668 .

patzer2097 в сообщении #892779 писал(а):

2. С работой что-то не так? (Ну, помимо уровня журнала, в котором она появилась)

Жданович, на мой взгляд, немного переборщил с новой терминологией. Некоторые понятия, которые он вводит, уже рассматривались и как-то называются (емкость тензора - value или $\tau$-value, константные отношение - tight subsets of $\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}$, ссылок на известную книгу Algebraic Complexity Theory или на поздние статьи Штрассена, где рассматриваются сводимости отношений, нет). А так там все хорошо, теорема 4.1 у Ждановича - это то же самое, что теорема 4.1 у Ле Галла (но Ле Галла значительно проще понять), а после этой теоремы просто идет формулировка и решение задачи оптимизации.

patzer2097 в сообщении #892779 писал(а):

3. И другой вопрос - почему упомянутая Вами работа Ле Галла с $\omega<2.3728639$ считается лучшей на данный момент, ведь еще в 2012 году (причем на конференции топ-уровня) была представлена работа с $\omega<2.3727$?

На сайте Вассилевской-Вильямс лежит послений вариант статьи http://theory.stanford.edu/~virgi/matrixmult-f.pdf , там написано, что 2.3727 - это ошибка ПО для оптимизации и фигурирует оценка 2.372873.

[Boss03]

patzer2097 в сообщении #892642 писал(а):

Xaositect в сообщении #892287 писал(а):

Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.

Интересные результаты, сама по себе задача интересна, конечно
Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8

Не совсем понятно, что вас интересует: решение задачи в практической или теоретической плоскости.

[Руст]

Как понял, здесь еще нет аналога умножения через преобразование Фурье.
Здесь есть специалист Xaositect, надеюсь он отзовется.
Мне пришла такая идея умножения.
Матрице $A=(a_{ij})$ порядка $n*m$ сопоставим многочлен от двух переменных
$f(x,y)=\sum_{i,j} a_{ij}x^iy^j$.
Аналогично матрице $B=(b_{jk})$ порядка $m*r$ сопоставим многочлен
$g(y,z)=\sum_{jk}b_{jk}y^jz^k$. Тогда произведению матриц $C=A*B$ соответствует многочлен
$\phi(x,z)=\frac{1}{m}\sum_{i=1}^m f(x,\omega^{-i})g(\omega^i,z)$, где $\omega$ корень m-ой степени от 1.
Вычисляя значение $\phi(x,z)$ в $n*r$ точках, узнаем многочлен, т.е. определим произведение матриц.
По аналогии умножения больших чисел (или многочленов) количество операций для умножения двух квадратных матриц
сведется к $O(n^2\ln n)$ операций.

[Xaositect]

Руст в сообщении #892836 писал(а):

По аналогии умножения больших чисел (или многочленов) количество операций для умножения двух квадратных матриц сведется к $O(n^2\ln n)$ операций.

Тут получается $n^3 \log n$. Для вычисления одного значения $\varphi(x, z)$ по формуле используется $O(n)$ операций.

Вообще у меня большие сомнения, что хороший алгоритм можно получить с помощью вложения одного матричного умножения в коммутативную алгебру (у Вас по сути используется алгебра $\mathbb{C}[x, y, z]/(y^m - 1)\cong \mathbb{C}^m[x,z]$). Вроде бы были даже формальные результаты такого типа после статьи Коэна-Уманса по групповому подходу.