Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 42
Ну наконец-то!
Черт, вы правы! Всегда этих 0.003 мешались под ногами и тормозило всё из-за них…
То есть у Вас есть реализация алгоритма Копперсмита-Винограда? =)
Теперь заживём!
Вы, наверное, считаете этот ваш комментарий очень остроумным.
Но, чтобы читатели чуть поглубже поняли о чём речь, я поясню, почему эти 0.003, натурально, огромный прогресс. Результатов по этому вопросу не было 20 лет. Сама задача оценки экспоненты матричного умножения по уровню вовлечённости напоминает теорему Ферма. Все верят, что в итоге в качестве оценки будет получена константа 2. Жаль, пока никто не может этого доказать.
Наверное каждый третий математик, который имеет отношение к вычислительной алгебре, когда-то брался за эту задачу. Есть математики, которые положили жизнь на решение этой задачи, и не смогли получить новой оценки.
Сама же экспонента матричного умножения по уровню значимости — мировая константа. А задача по её получению — одна из центральных задач вычислительной алгебры.
Вот уже около полувека (с тех пор, как эта проблема встала) идёт нешуточная борьба за эту оценку. И когда по этой проблеме после такого большого перерыва получили новый результат — это очень и очень значительная новость!
Но, чтобы читатели чуть поглубже поняли о чём речь, я поясню, почему эти 0.003, натурально, огромный прогресс. Результатов по этому вопросу не было 20 лет. Сама задача оценки экспоненты матричного умножения по уровню вовлечённости напоминает теорему Ферма. Все верят, что в итоге в качестве оценки будет получена константа 2. Жаль, пока никто не может этого доказать.
Наверное каждый третий математик, который имеет отношение к вычислительной алгебре, когда-то брался за эту задачу. Есть математики, которые положили жизнь на решение этой задачи, и не смогли получить новой оценки.
Сама же экспонента матричного умножения по уровню значимости — мировая константа. А задача по её получению — одна из центральных задач вычислительной алгебры.
Вот уже около полувека (с тех пор, как эта проблема встала) идёт нешуточная борьба за эту оценку. И когда по этой проблеме после такого большого перерыва получили новый результат — это очень и очень значительная новость!
Шутка не всегда означает сарказм. Иногда это просто добрый юмор. :-)
Конечно не всегда, но я подозреваю, что в этом конкретном случае добрая часть уважаемых посетителей хабрахабра в силу того, что они не специалисты в этой области, не понимают значения этих 0.003.
Поспешил разъяснить.
Поспешил разъяснить.
Да-да-да! Это подобно тому, что соотношение массы гравитационной к Массе инерционной придвинули бы к 1 еще на один разряд. Или степень радиуса расстояния между зарядами в знаменателе закона Кулона придвинули бы к 2 еще на один разряд.
И здорово, что разъяснили, да. Мне бы самому стоило.
Кстати, по поводу математиков, положивших жизнь. Есть репорт Джеймса Ива. Он два года назад опубликовал свои промежуточные результаты с оценкой n^{2+o(1)}. И вскоре после этого умер. В самом репорте есть комментарий Дональда Кнута, который пишет, что в каком-то месте не понял.
Кстати, по поводу математиков, положивших жизнь. Есть репорт Джеймса Ива. Он два года назад опубликовал свои промежуточные результаты с оценкой n^{2+o(1)}. И вскоре после этого умер. В самом репорте есть комментарий Дональда Кнута, который пишет, что в каком-то месте не понял.
Вы тоже слишком переоцениваете данное событие. На практике даже алгоритм Копперсмита-Винограда не используется (используют алгоритм Штрассена). А знаете почему? Потому что он не практичен! Я даже не смог найти ссылки на реализацию етого алгоритма и это при том что про него знают уже 33 года.
24, а не 33, ниже я приводил верную дату.
Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.
С точки зрения практика вы, безусловно, правы. Впрочем, эта точка зрения подходит также для литературоведа или доярки. Я к тому, что то, что именно вам не полезен этот результат, совершенно не значит, что он не значителен.
С точки зрения теоретической математики (которая чаще всего со временем даёт практическую пользу) это серьезный прорыв.
Из чисто банальных соображений, это показало математикам, что проблема сдвинута с мёртвой точки. В науке так часто бывает, что такая вот сдвижка с мёртвой точки провоцирует серию результатов самых разных учёных.
Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.
С точки зрения практика вы, безусловно, правы. Впрочем, эта точка зрения подходит также для литературоведа или доярки. Я к тому, что то, что именно вам не полезен этот результат, совершенно не значит, что он не значителен.
С точки зрения теоретической математики (которая чаще всего со временем даёт практическую пользу) это серьезный прорыв.
Из чисто банальных соображений, это показало математикам, что проблема сдвинута с мёртвой точки. В науке так часто бывает, что такая вот сдвижка с мёртвой точки провоцирует серию результатов самых разных учёных.
Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.Нет, здесь вы неправы, они привели явный алгоритм в оригинальной публикации. Он непрактичен, да, но существует.
А я не говорил что результат не полезен. Только что вы его переоцениваете. Я сам закончил вычислительную математику, сейчас работаю с вычислительной геометрии. Плохо быть чистым теоретиком или практиком, толковий математик должен сочетать качества обоих.
И да не вся теоретическая математика со временем дает пользу (только малая часть). В большинстве случаев теория строится для предоставления аппарата способного решать практические (востребованные) задачи.
При умножении двух матриц что вас интересует кроме сложности (и даже больше)? Точность результата! Стандартний метод (N^3) и метод Штрассена имеют очень хорошую численную устойчивость, они используют только умножение, вычитание и добавление элементов матрицы. Как только вы начинаете вычислять статистики, делить (возможно на маленькие числа) и делать более сложные операции вы теряете численную устойчивость. Кроме того большим плюсом алгоритма Штрассена является возможность паралельного вичисления субматриц.
И да не вся теоретическая математика со временем дает пользу (только малая часть). В большинстве случаев теория строится для предоставления аппарата способного решать практические (востребованные) задачи.
При умножении двух матриц что вас интересует кроме сложности (и даже больше)? Точность результата! Стандартний метод (N^3) и метод Штрассена имеют очень хорошую численную устойчивость, они используют только умножение, вычитание и добавление элементов матрицы. Как только вы начинаете вычислять статистики, делить (возможно на маленькие числа) и делать более сложные операции вы теряете численную устойчивость. Кроме того большим плюсом алгоритма Штрассена является возможность паралельного вичисления субматриц.
На самом деле ни грамма не сомневаюсь в значимости этого события для науки.
И шутка не в том, что открытие бесполезно, а в том, каким оно кажется обычному человеку
И шутка не в том, что открытие бесполезно, а в том, каким оно кажется обычному человеку
Казалось бы, этот вопрос должен быть решен уже давно…
Правда, не очень понятно, насколько выгодно его использовать из-за константы впереди. Судя по формулам, она должна быть не маленькой.
Правда, не очень понятно, насколько выгодно его использовать из-за константы впереди. Судя по формулам, она должна быть не маленькой.
А почему Вам так кажется?
Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
Да не только контанта имеет значение. Если умножать матрицы методом Штрассена или обычно (за N^3) вам не нужно вычислять какие то статистики, собственние значения матрицы и тому подобное. И если вам важна точность (как в примере с Боинг), то ви не будете использовать чисельно нестабильные алгоритми.
А почему Вам так кажется?
Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
Я шокирован! Думал, этого ещё долго произойдёт, всё-таки 20 лет без прогресса.
Я проглядел мельком её статью. Выходит, результат достигнут не с помощью подхода Кона и Уманса с вложением операции умножения матриц в операцию умножения групповой алгебры, а с помощью тензорного подхода.
Не знаете, результат уже проверили специалисты? Может быть там всё-таки ошибка…
P.S. Занимаетесь этой задачей?
Я проглядел мельком её статью. Выходит, результат достигнут не с помощью подхода Кона и Уманса с вложением операции умножения матриц в операцию умножения групповой алгебры, а с помощью тензорного подхода.
Не знаете, результат уже проверили специалисты? Может быть там всё-таки ошибка…
P.S. Занимаетесь этой задачей?
полученную Копперсмитом и Виноградом в 1978 году
Всё-таки в 1987, а не в 1978 году
Вот за это я люблю математику :3
Топикстартеру маленькое замечание: поверьте, «ω» и «≤» — не настолько редко встречающиеся в шрифтах символы, чтобы вставлять их при помощи картинок.
Топикстартеру маленькое замечание: поверьте, «ω» и «≤» — не настолько редко встречающиеся в шрифтах символы, чтобы вставлять их при помощи картинок.
Я полагаю, топикстартер просто логично предпочитает набирать все формулы в LaTeX, потому что его рендерер — идеальный. Статья на Хабре не должна быть тому исключением.
Мне казалось, что в идеальном рендерере нижняя черта должна быть не горизонтальной, а параллельна средней, примерно как вот в этом символе ⋜, если его перевернуть.
Я понимаю, когда в неспециализированном тексте по техническим ограничениям некоторые элементы выглядят не совсем так как положено в математике. Но в латехе-то должно быть.
Я понимаю, когда в неспециализированном тексте по техническим ограничениям некоторые элементы выглядят не совсем так как положено в математике. Но в латехе-то должно быть.
Символ с нижней чертой, параллельной средней, — это традиция русской математической школы.
Символ с горизонтальной нижней чертой — это традиция западной математической школы.
Очевидно, онлайн-рендерер LaTeX`а использует дефолтные настройки и рендерит по западной традиции. Чтобы переключить его на русские настройки, можно, например, использовать russcorr. Или что-нибудь другое.
Как пример других значимых отличий русской и западной систем записи — нижний/верхний частичный предел. У нас он записывается как lim с чертой снизу/сверху, а во всем мире — как «lim inf»/«lim sup».
Символ с горизонтальной нижней чертой — это традиция западной математической школы.
Очевидно, онлайн-рендерер LaTeX`а использует дефолтные настройки и рендерит по западной традиции. Чтобы переключить его на русские настройки, можно, например, использовать russcorr. Или что-нибудь другое.
Как пример других значимых отличий русской и западной систем записи — нижний/верхний частичный предел. У нас он записывается как lim с чертой снизу/сверху, а во всем мире — как «lim inf»/«lim sup».
Да, я люблю латех. Меня всё же не хватило на то, чтобы, например, и n делать картинкой, но всё же. =)
один из немногих случаев на хабре, когда заходишь под кат ради прочтения комментов :)
И это все сделала женщина? Мое глубочайшее уважение.
На сколько % быстрее станет перемножение матрица 5000x5000?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Уменьшена экспонента умножения матриц