2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Об алгоритмах умножения матриц
Сообщение02.08.2014, 23:10 
Заслуженный участник


09/02/06
4351
Москва
Мне кажется все нормально. Дело в том, что здесь
$\phi(x,z)=\frac{1}{m}\sum_{i=1}^m f(x,\omega^{-i})g(\omega^i,z)$
только на вид $n^3$ операций. На самом деле это совпадает с действительной частью
одного члена умножения из $Q(\omega)[x,z]$.
Я не специалист в этих делах. Хотелось узнать, были ли такие попытки.
Если нет то, попробую аккуратно расписать.

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


06/10/08
6313
Руст в сообщении #892862 писал(а):
Я не специалист в этих делах. Хотелось узнать, были ли такие попытки.
Если нет то, попробую аккуратно расписать.
Распишите. Пока я могу сказать, что для вычисления $n$ значений $\varphi(x_1, z),\dots,\varphi(x_n, z)$ необходимо $n^2$ умножений. Как можно склеивать эти вычисления для разных $z$, я не вижу.

Попытки какие-то похожие наверняка были, в частности, несколько людей рассматривали матрицы как многочлены от двух матриц $X, Y$, но там несколько другие проблемы, там некоммутативность $X$ и $Y$ вылезает.

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


14/03/10
867
Xaositect, спасибо за подробный ответ! Я из Вашего поста и посмотрев указанные работы сделал три вывода.
(1) Многие из самых серьезных экспертов скептически относятся к последним результатам про $\omega$.
(2) Работы Стотерса, Ждановича и Вассилевски-Уильямс не содержат особенно много новых идей - в них просто постепенно улучшается решение некоторой задачи оптимизации, возникающей из работы Копперсмита-Винограда.
(3) Работы, представляемые на STOC, могут содержать серьезные ошибки.

 Профиль  
                  
 
 Re: Об алгоритмах умножения матриц
Сообщение20.08.2014, 01:42 
Модератор
Аватара пользователя


20/03/14
10801
 i  Оффтоп отделен в «Цитата: было или приписано?»

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


09/02/06
4351
Москва
Сегодня я на семинаре кафедры (теоритической информатики мех-мата МГУ) делал обзорный доклад по быстрым умножениям.
Когда приступил к своему алгоритму с $O(n^{2+\epsilon})$ и сказал, что он основывается на умножении цветных многочленов (цветных алгебр)
меня остановили и время семинара уже закончилась. В следующий вторник в 16-45 ауд. 13-10 расскажу о своем алгоритме.

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


08/11/11
5909
Нашел текст, очень похожий на вышеописанное (возможно, это указанный результат и есть)

http://shamolin2.imec.msu.ru/art-211-2.pdf

Я только не понял -- в итоге умножаются матрицы за $O(n^{2+\varepsilon})$ или нет? Там как-то мутно это описано, да и журнал странный, у половины статей один соавтор.

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


09/02/06
4351
Москва
Нет, это неправильная статья. Подход, сводящий к умножению квазикоммутативных многочленов правильный, однако не сводится ни к какой свертке.
Я тогда забыл, что передал Шамолину черновой вариант и узнал об этом, когда уже неправильная черновая работа пошла в печать.
На самом деле все вычисляется по хитрее. Решил опубликовать только после работающей программы.

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


06/10/08
6313
Руст, это ведь Ваше умножение тут: http://sitito.cs.msu.ru/index.php/SITIT ... e/view/513 ?
Опять совершенно непонятно, какой у Вас получился алгоритм с $N \log N$. Для $2 \times 2$ вижу Штрассена, а дальше рекурся для того, чтобы вычислять $f^{i_1 \dots i_k}$ и непонятно, как дальше их использовать. Можете привести частный случай Вашего алгоритма для матриц $4 \times 4$?

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

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



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

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


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

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