Алгоритм Копперсмита

Алгоритм Копперсмита

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

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

См. также

Литература

Ссылки

  1. ↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier


Формула

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


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

  • Алгоритм Копперсмита — Винограда — Алгоритм Копперсмита  Винограда  самый асимптотически быстрый из всех известных алгоритмов умножения матриц. Работает за время . Предложен в 1987 году. Однако, на практике обычно пользуются алгоритмом Штрассена по причинам простоты… …   Википедия

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

  • Алгоритм Штрассена — предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы. В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Умножение матриц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведением матриц. Содержание 1 Определение 2 Иллюстрация 3 Мотивировка …   Википедия

  • Дискретное логарифмирование — (DLOG) задача обращения функции в некоторой конечной мультипликативной группе . Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической… …   Википедия

  • Дискретный логарифм — Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной… …   Википедия

  • Индекс числа по модулю — Дискретное логарифмирование (DLOG) – задача обращения функции gx в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов, в мультипликативной… …   Википедия

  • MARS — У этого термина существуют и другие значения, см. Mars (значения). MARS Создан: 1998 г. Опубликован: 1998 г. Размер ключа …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»