Алгоритм Копперсмита — Винограда | это... Что такое Алгоритм Копперсмита — Винограда? (original) (raw)

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

Алгоритм Копперсмита — Винограда — самый асимптотически быстрый из всех известных алгоритмов умножения матриц. Работает за время $\operatorname{O}(n^{2,375477})$ . Предложен в 1987 году. Однако, на практике обычно пользуются алгоритмом Штрассена по причинам простоты реализации и меньшей константе в оценке трудоемкости.

См. также

Литература

Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arΧiv:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379—388.
Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.
Robinson, Sara (2005), "Toward an Optimal Algorithm for Matrix Multiplication", SIAM News Т. 38 (9), <http://www.siam.org/pdf/news/174.pdf> .

Wikimedia Foundation.2010.

Полезное

Смотреть что такое "Алгоритм Копперсмита — Винограда" в других словарях:

Алгоритм Копперсмита — Алгоритм Копперсмита Винограда алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом (англ.) и улучшенный в 2010 году Вирджинией Вильямс. В исходной версии асимптотическая сложность… … Википедия
Алгоритм Копперсмита—Винограда — … Википедия
Алгоритм Штрассена — предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы. В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) … Википедия
Умножение матриц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведением матриц. Содержание 1 Определение 2 Иллюстрация 3 Мотивировка … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
MARS — У этого термина существуют и другие значения, см. Mars (значения). MARS Создан: 1998 г. Опубликован: 1998 г. Размер ключа … Википедия
MARS (криптография) — У этого термина существуют и другие значения, см. Mars (значения). MARS Создан: 1998 г … Википедия
Гипотеза Штрассена — В теории сложности вычислений и линейной алгебре гипотеза Штрассена утверждает, что для любой заданной скорости (до определённого предела) существует алгоритм, позволяющий перемножать достаточно большие матрицы с такой скоростью. Были найдены… … Википедия
Открытые математические проблемы — Открытые (нерешённые) математические проблемы проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… … Википедия