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

12.03.2021

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

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

Улучшения алгоритма

  • В 2010 Эндрю Стотерс усовершенствовал алгоритм до O ( n 2.374 ) . {displaystyle O(n^{2.374}).}
  • В 2011 году Вирджиния Вильямс усовершенствовала алгоритм ещё раз — O ( n 2.3728642 ) . {displaystyle O(n^{2.3728642}).}
  • В 2014 году Франсуа Ле Галль упростил метод Вильямс и получил новую улучшенную оценку O ( n 2.3728639 ) . {displaystyle O(n^{2.3728639}).}