Алгоритм Копперсмита — Винограда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом (англ.). В исходной версии асимптотическая сложность алгоритма составляла O(n2,3755), где  — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, является самым лучшим результатом среди известных алгоритмов умножения матриц.

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

Улучшения алгоритма[править | править вики-текст]

  • В 2010 Эндрю Стотерс усовершенствовал алгоритм до [1]
  • В 2011 году Вирджиния Вильямс усовершенствовала алгоритм еще раз — [2]
  • В 2014 году Франсуа Ле Галль упростил метод Уильямс и получил новую улучшенную оценку [3]

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Stothers, Andrew (2010), On the Complexity of Matrix Multiplication, <https://www.era.lib.ed.ac.uk/handle/1842/4734> .
  2. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier
  3. "Even if someone manages to prove one of the conjectures—thereby demonstrating that ω = 2—the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. (...) the input matrices must be astronomically large for the difference in time to be apparent."Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014)