Матричное умножение в

13

Я искал о матричном умножении, поэтому я впервые посещал вики- алгоритмы умножения матриц, в ссылках я нашел статью, в которой утверждается, что используется алгоритм О(N2Lограмм(N)) , я собираюсь прочитать статью, но она сложная и Уилл читает слишком много времени, но если кто-то читает эту статью или знает об этом алгоритме, так ли это? и знаете ли вы о базовой идее этого, чтобы немного ее описать.

Спасибо заранее, я знаю, что это немного общий вопрос, но, если я найду, что это хороший подход, я собираюсь изучить детали.

ds.algorithms linear-algebra matrix-product Saeed
источник
5
Я думаю, что полезно понять ваш собственный вопрос лучше. Вы ищете последовательный алгоритм или параллельный алгоритм? Последовательные алгоритмы умножения матриц на время O (n ^ 2 log n) не известны, и статья Евы является частичным результатом таких алгоритмов (я не читал статью, я просто просмотрел ее). Если вы заботитесь о параллельном времени, то параллельное время O (log n) (при условии скалярного сложения и скалярного умножения в постоянном времени) является стандартным, и вы можете найти объяснение, например, в книге « Вычислительная сложность » Пападимитриу.
Цуёси Ито
2
(1) Пожалуйста, измените ваш вопрос так, чтобы было ясно, что вы спрашиваете о последовательных алгоритмах. (2) Я понял, что вы добавили тег [квантовые вычисления]. Пожалуйста, измените ваш вопрос, чтобы объяснить связь с квантовыми вычислениями. (Я предполагаю, что ваш вопрос мотивирован квантовыми вычислениями, но ваше собственное объяснение гораздо более полезно, чем любое предположение.)
Tsuyoshi Ito
2
Я бы порекомендовал вам сначала удалить этот вопрос, а затем сделать репост позже, если вы обнаружите, что у вас есть вопрос.
Суреш Венкат
3
@Saeed: эта проблема обсуждалась в мета-версии, и в настоящее время это политика сайта, если вы хотите обсудить политику, используйте мета. С другой стороны, вы можете изменить вопрос и не упоминать документ, чтобы сделать его тематическим, например, изменить вопрос так, чтобы он стал «каков самый известный алгоритм умножения матриц в модели X?» и это было бы по теме. (примечание: если вы сами не можете проверить правильность неопубликованной статьи и хотите процитировать ее, подождите, пока она не будет рецензирована и опубликована.)
Kaveh
3
Связанное обсуждение на Meta: можно ли спросить о правильности препринтов по темам, которые не нравятся? Я не утверждаю, что все, что написано на этой странице, относится к этому вопросу, но оно, по крайней мере, тесно связано.
Цуёси Ито

Ответы:

34

Я наткнулся на эту статью около года назад, но не удосужился прочитать ее внимательно. Я могу сказать вам, что этот подход не считается правильным. На странице 36 этой же статьи есть прикрепленный комментарий Дона Кнута, который указывает на серьезный недостаток этого подхода.

Чтобы понять эту статью, вам нужно узнать об алгебре групп и теории представлений. Будет тяжело, если вы раньше не видели такого материала.

Райан Уильямс
источник