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

Быстрое умножение матрицы на вектор?

Гмм, алгоритмы умножения двух матриц размерности NxN сложности N^{2+b}, где b строго меньше единицы, известны. А вот насчет быстрого(быстрее N^2) умножения матрицы NxN на вектор Nx1 я что-то ничего сразу не нахожу. Вообще говоря, если есть алгоритм N^(1+b) для матрица на вектор, то должен быть и алгоритм N^(2+b) для матриц, а вот в обратную сторону не совсем понятно как из алгоритма для матриц соорудить алгоритм для матрица на вектор.

Мне вот сейчас желателен как раз хотя бы N^(3/2) для перемножения матрицы и вектора. Но известен ли такой?


Update: А вот интересно можно ли ожидать что существует алгоритм N*Log(N) и следовательно теоретический N*N*Log(N) для матриц. Или это из разряда мечтаний что NP=P.

Update 2: Мда, как справедливо сразу же отметили, результат существенно зависит от всех элементов матрицы, то есть N^2 это нижняя граница. И золота здесь нет (((

Update 3: Матрицы(вектора) которые интересуют меня из целых чисел. Можно ли что-то улучшить в этом случае. Свести как-то к быстрому умножению M-разрядных чисел. Или что-то в этом роде.
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.
  • 12 comments

  • 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 году(в комментах) про полезность ведения ЖЖ собственного блога, в котором можно записывать прочитанные результаты,…