Pull to refresh

Comments 42

Черт, вы правы! Всегда этих 0.003 мешались под ногами и тормозило всё из-за них…
То есть у Вас есть реализация алгоритма Копперсмита-Винограда? =)
Ага, каждое утро для разминки пишу её… 15 приседаний, 10 отжиманий и дважды — реализацию алгоритма Копперсмита-Винограда.
Вы, наверное, считаете этот ваш комментарий очень остроумным.

Но, чтобы читатели чуть поглубже поняли о чём речь, я поясню, почему эти 0.003, натурально, огромный прогресс. Результатов по этому вопросу не было 20 лет. Сама задача оценки экспоненты матричного умножения по уровню вовлечённости напоминает теорему Ферма. Все верят, что в итоге в качестве оценки будет получена константа 2. Жаль, пока никто не может этого доказать.

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

Сама же экспонента матричного умножения по уровню значимости — мировая константа. А задача по её получению — одна из центральных задач вычислительной алгебры.

Вот уже около полувека (с тех пор, как эта проблема встала) идёт нешуточная борьба за эту оценку. И когда по этой проблеме после такого большого перерыва получили новый результат — это очень и очень значительная новость!
Шутка не всегда означает сарказм. Иногда это просто добрый юмор. :-)
Конечно не всегда, но я подозреваю, что в этом конкретном случае добрая часть уважаемых посетителей хабрахабра в силу того, что они не специалисты в этой области, не понимают значения этих 0.003.

Поспешил разъяснить.
Да-да-да! Это подобно тому, что соотношение массы гравитационной к Массе инерционной придвинули бы к 1 еще на один разряд. Или степень радиуса расстояния между зарядами в знаменателе закона Кулона придвинули бы к 2 еще на один разряд.
И здорово, что разъяснили, да. Мне бы самому стоило.

Кстати, по поводу математиков, положивших жизнь. Есть репорт Джеймса Ива. Он два года назад опубликовал свои промежуточные результаты с оценкой n^{2+o(1)}. И вскоре после этого умер. В самом репорте есть комментарий Дональда Кнута, который пишет, что в каком-то месте не понял.
Вы тоже слишком переоцениваете данное событие. На практике даже алгоритм Копперсмита-Винограда не используется (используют алгоритм Штрассена). А знаете почему? Потому что он не практичен! Я даже не смог найти ссылки на реализацию етого алгоритма и это при том что про него знают уже 33 года.
24, а не 33, ниже я приводил верную дату.

Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.

С точки зрения практика вы, безусловно, правы. Впрочем, эта точка зрения подходит также для литературоведа или доярки. Я к тому, что то, что именно вам не полезен этот результат, совершенно не значит, что он не значителен.

С точки зрения теоретической математики (которая чаще всего со временем даёт практическую пользу) это серьезный прорыв.

Из чисто банальных соображений, это показало математикам, что проблема сдвинута с мёртвой точки. В науке так часто бывает, что такая вот сдвижка с мёртвой точки провоцирует серию результатов самых разных учёных.
Насколько я помню, алгоритма Копершмита-Винограда как такового не существует. Ими теоретически, без предъявления алгоритма в явном виде, показана их оценка.
Нет, здесь вы неправы, они привели явный алгоритм в оригинальной публикации. Он непрактичен, да, но существует.
Возможно, вы правы. Я очень давно и очень по диагонали просматривал эту публикацию. И тогда у меня сложилось мнение, не исключено, что поверхностное, что извлечь алгоритм в явном виде не удастся.
А я не говорил что результат не полезен. Только что вы его переоцениваете. Я сам закончил вычислительную математику, сейчас работаю с вычислительной геометрии. Плохо быть чистым теоретиком или практиком, толковий математик должен сочетать качества обоих.
И да не вся теоретическая математика со временем дает пользу (только малая часть). В большинстве случаев теория строится для предоставления аппарата способного решать практические (востребованные) задачи.
При умножении двух матриц что вас интересует кроме сложности (и даже больше)? Точность результата! Стандартний метод (N^3) и метод Штрассена имеют очень хорошую численную устойчивость, они используют только умножение, вычитание и добавление элементов матрицы. Как только вы начинаете вычислять статистики, делить (возможно на маленькие числа) и делать более сложные операции вы теряете численную устойчивость. Кроме того большим плюсом алгоритма Штрассена является возможность паралельного вичисления субматриц.
На самом деле ни грамма не сомневаюсь в значимости этого события для науки.
И шутка не в том, что открытие бесполезно, а в том, каким оно кажется обычному человеку
Казалось бы, этот вопрос должен быть решен уже давно…

Правда, не очень понятно, насколько выгодно его использовать из-за константы впереди. Судя по формулам, она должна быть не маленькой.
А почему Вам так кажется?

Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
мне кажется все его используют, потому что в таком виде он входит в основные библиотеки для линейки. :)
Да не только контанта имеет значение. Если умножать матрицы методом Штрассена или обычно (за N^3) вам не нужно вычислять какие то статистики, собственние значения матрицы и тому подобное. И если вам важна точность (как в примере с Боинг), то ви не будете использовать чисельно нестабильные алгоритми.
А почему Вам так кажется?

Да, известно, что эти улучшенные алгоритмы становится осмысленным использовать лишь на огромных матрицах. Говорят, что Боинг использует алгоритм Штрассена.
Я шокирован! Думал, этого ещё долго произойдёт, всё-таки 20 лет без прогресса.

Я проглядел мельком её статью. Выходит, результат достигнут не с помощью подхода Кона и Уманса с вложением операции умножения матриц в операцию умножения групповой алгебры, а с помощью тензорного подхода.

Не знаете, результат уже проверили специалисты? Может быть там всё-таки ошибка…

P.S. Занимаетесь этой задачей?
Нет, я не занимаюсь. =)

Как я понимаю, результат пока не опубликован. Насколько он проверен, не знаю. Но знаю, что Вирджи фигню не стала бы выкладывать. Наверное, Раян прочитал всё-таки. =)
полученную Копперсмитом и Виноградом в 1978 году

Всё-таки в 1987, а не в 1978 году
Вот за это я люблю математику :3
Топикстартеру маленькое замечание: поверьте, «ω» и «≤» — не настолько редко встречающиеся в шрифтах символы, чтобы вставлять их при помощи картинок.
Я полагаю, топикстартер просто логично предпочитает набирать все формулы в LaTeX, потому что его рендерер — идеальный. Статья на Хабре не должна быть тому исключением.
Мне казалось, что в идеальном рендерере нижняя черта должна быть не горизонтальной, а параллельна средней, примерно как вот в этом символе ⋜, если его перевернуть.
Я понимаю, когда в неспециализированном тексте по техническим ограничениям некоторые элементы выглядят не совсем так как положено в математике. Но в латехе-то должно быть.
Символ с нижней чертой, параллельной средней, — это традиция русской математической школы.
Символ с горизонтальной нижней чертой — это традиция западной математической школы.
Очевидно, онлайн-рендерер LaTeX`а использует дефолтные настройки и рендерит по западной традиции. Чтобы переключить его на русские настройки, можно, например, использовать russcorr. Или что-нибудь другое.

Как пример других значимых отличий русской и западной систем записи — нижний/верхний частичный предел. У нас он записывается как lim с чертой снизу/сверху, а во всем мире — как «lim inf»/«lim sup».
Да, я люблю латех. Меня всё же не хватило на то, чтобы, например, и n делать картинкой, но всё же. =)
один из немногих случаев на хабре, когда заходишь под кат ради прочтения комментов :)
по-моему крайне распространенный случай
UFO landed and left these words here
image
И это все сделала женщина? Мое глубочайшее уважение.
Поверьте, то что вы привели сделала какая-нибудь система компьютерной алгебры.
И эту картинку сумел вставить в пост человек с ником на букву «L»? Я поражен до глубины души!
Всего лишь два тролля?! Мне показалось, что на мой неаккуратно написанный коммент их найдется куда больше.
На сколько % быстрее станет перемножение матрица 5000x5000?
На 2.588%, если коэффициент одинаковый.
Sign up to leave a comment.

Articles