Zametki na polyah (akor168) wrote,
Zametki na polyah
akor168

линейная алгебра в больших размерностях

Вообще забавно, я всего лишь буквально несколько лет назад серьезно проникся моментом, что если мы хотим обратить матрицу размерности миллион наивным методом Гаусса, то нам нужно миллион в кубе операций, то есть квинтиллион 10^18, что делает нашу задачу по сути нереальной.
И именно поэтому алгоритм, который делает обращение матрицы размерности N за время N3-A не просто теория, а без подобных алгоритмов работа с такими матрицами попросту невозможна. И с практической точки зрения алгоритмы, где A как можно ближе к 1, должны быть гораздо важнее для практики, чем все эти теории про P=NP.

Update: Грубо говоря, практически нужны алгоритмы вида С(N)*N^2, где с практической точки зрения С(N) ограничено несколькими тысячами на реальных данных объема N^2 (количество данных в матрице размерности N) с которыми человечество потенциально будет иметь дело.
Subscribe

  • 3-0 vs 42-0

    To put the magnitude of the U.S. defeat in context, losing 3-0 in soccer is the equivalent of losing 42-0 in football. Реально улыбнуло, поскольку…

  • Анекдоты: полная потеря смысла при пересказе

    Знаете, когда обсуждается сложность перевода с одного языка на другой, обычно рассказывается пример с круглым столом где каждый знает языки двух…

  • полезность регулярных проф-заметок

    Терри Тао пишет аж в 2013 году(в комментах) про полезность ведения ЖЖ собственного блога, в котором можно записывать прочитанные результаты,…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments