Комментарии 11
Спасибо, что выбираете для своего блога качественный контент, а не кликбейт!
К счастью, на каждую страницу в интернете ведут совсем немного входящих ссылок — не миллиард и даже не миллион. На популярную статью в Википедии могут ссылаться десятки тысяч страниц, на эту статью на Хабре — хорошо если десятки. Иными словами, почти все коэффициенты в системе уравнений интернета — нули. Каждый ненулевой коэффициент подвергнется O(N) умножениям при подстановке содержащего его уравнения во все остальные.
Значит ли это, что в предельном случае (нереально огромного числа ссылок на ресурс) случайно наткнуться на него в Интернете будет быстрее, чем его нагуглить??
Предельный случай это если на каждой странице в интернете будет ссылка. Но тогда вероятность будет d*1/L(p), где d это вероятность того, что юзер кликнет по ссылке, L(p) это количество ссылок на странице p. То есть сильно меньше единицы.
Стопроцентная вероятность будет только если каждая страница в интернете будет содержать только одну ссылку, и это будет ссылка на страницу р. При этом должна отсутствовать возможность закрыть браузер или набрать другой адрес.
Важность алгоритма Вемпалы и Пенга совсем не в практической применимости, а в доказательстве того, что сложность решения систем уравнений не ограничена сложностью умножения матриц
С чего такой вывод? В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
Но ни новый алгоритм, ни другие математические достижения последнего полувека никак не повлияли на практически применимые способы решения систем уравнений: Google и все остальные так и продолжат пользоваться простым, быстрым и неточным итеративным способом.
Мое сугубо субъективное мнение: вы написали статью по теме, в которой не понимаете почти ничего. «Простой, быстрый и неточный итеративный способ» изучен в математике не меньше, чем алгоритмы умножения матриц. Да даже хотя бы в аннотации к статье, которую вы пересказываете, заявлено, что используется блочный метод Крылова, который, не поверите, основывается на итеративном методе. Полагать, что гугл никак не улучшил у себя метод простой итерации было бы довольно наивно.
Все мы учили в школе алгоритм исключения неизвестных по однойЭто между прочим именной метод
У вас ссылка на метод решения системы неравенств. Если говорить, про уравнения, то это метод Гаусса
В статье улучшение только частного случая (в абстракте более точно указана привязка количества ненулевых элементов к числу обусловленности).
В посте ровно это и написано: «Для системы уравнений с
их алгоритм находит точное решение за 
операций, опережая степень асимптотической сложности умножения матриц на 0.04.»Это между прочим именной метод
У нас в школе, когда его учат, точно не упоминают ни Гаусса, ни Фурье, ни Моцкина.
Может быть, в англоязычных школах кого-то из них упоминают, но сомневаюсь.
Может анализируют не весь кластер целиком, а разбивают на сегменты? Можно предположить например, что русскоязычный контент и скажем, хинди, вряд-ли имеют много пересечений. Да и с точки зрения пользовательского опыта у них не стоит задачи сделать абсолютный рейтинг, а всего-лишь отсортировать выдачу.
Почему важно, что системы линейных уравнений решаются быстрее, чем множатся матрицы