2014 dxdy logo

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

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




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


06/10/08
6322
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
6322
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
6322
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
6322
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
6322
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
4351
Москва
Как понял, здесь еще нет аналога умножения через преобразование Фурье.
Здесь есть специалист 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
6322
Руст в сообщении #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  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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