2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:29 
Заслуженный участник
Аватара пользователя


06/10/08
6362
Linkey в сообщении #892297 писал(а):
А числа целые, рациональные или действительные?
В данном случае неважно, оба этих факта верны над любым кольцом.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 18:51 
Заслуженный участник


14/03/10
867
Xaositect в сообщении #892287 писал(а):
Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.
Интересные результаты, сама по себе задача интересна, конечно :-)
Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8 :-)

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 19:04 
Заслуженный участник
Аватара пользователя


30/01/06
72408
patzer2097 в сообщении #892395 писал(а):
не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 19:05 
Заслуженный участник
Аватара пользователя


06/10/08
6362
patzer2097 в сообщении #892395 писал(а):
Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8 :-)
Ну это да. Но вот уже для комплексных матриц 2x2 умножение действительно дороже сложения и можно попробовать Штрассена.

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

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

patzer2097 в сообщении #892395 писал(а):
Кстати, чтобы задача про минимизацию числа умножений стала осмысленной, нужно ставить вопрос уже над не обязательно коммутативным кольцом, - иначе как решение может помочь строить быстрые алгоритмы? :-)
Да. Для этого случая, кстати, алгоритма со сложностью 22 для 3x3 неизвестно, только 23. А чтобы получить улучшение по сравнению со Штрассеном, надо 21.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 19:43 
Заслуженный участник


14/03/10
867
Xaositect в сообщении #892403 писал(а):
А чтобы получить улучшение по сравнению со Штрассеном, надо 21.
Я тоже об этом подумал, - получается, пока $3\times3$ матрицы люди умеют умножать довольно плохо :-) А не дадите ссылку на какой-нибудь обзор с такого типа результатами? :-)

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 20:10 
Заслуженный участник
Аватара пользователя


06/10/08
6362
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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 20:13 
Заслуженный участник


14/03/10
867
Спасибо!!

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 20:14 
Заслуженный участник
Аватара пользователя


06/10/08
6362
patzer2097 в сообщении #892419 писал(а):
кстати, несмотря на обратные примеры - где умножение дороже сложения - задачу об минимизации числа сложений обычно не рассматривают :-) (хотя тут я наверняка неправ; впрочем, в любом случае внимания этой задаче уделяют меньше)
Эта задача значительно более сложная, там нет какой-то хорошей алгебры.
Для 2x2 известно, что 15 сложений минимально для 7 умножений, но там множество всех алгоритмов имеет очень хорошую алгебраическую структуру - если матрицы 2x2 рассматривать, как линейные операторы, то все алгоритмы ранга 7 получаются из алгоритма Штрассена заменой базисов в трех рассматриваемых двумерных пространствах.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение02.08.2014, 03:50 
Заблокирован


02/08/14

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

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 11:45 
Заблокирован


02/08/14

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

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 18:38 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 19:27 
Заслуженный участник
Аватара пользователя


06/10/08
6362
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.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение02.08.2014, 19:40 
Заблокирован


02/08/14

56
patzer2097 в сообщении #892642 писал(а):
Xaositect в сообщении #892287 писал(а):
Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.
Интересные результаты, сама по себе задача интересна, конечно :-)
Я имел в виду, что оптимизация вычислений при малых $n$ вряд ли осмысленна - тут наивный метод вне конкуренции, не будет же никто вычислять произведение 2x2 матриц по методу Штрассена, пусть даже там 7 умножений, а не 8 :-)

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

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 21:40 
Заслуженный участник


09/02/06
4361
Москва
Как понял, здесь еще нет аналога умножения через преобразование Фурье.
Здесь есть специалист 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)$ операций.

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 22:35 
Заслуженный участник
Аватара пользователя


06/10/08
6362
Руст в сообщении #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]$). Вроде бы были даже формальные результаты такого типа после статьи Коэна-Уманса по групповому подходу.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: NeVZleTeam


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group