Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом[англ.]. В исходной версии асимптотическая сложность алгоритма составляла , где — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, обладает лучшей асимптотикой среди известных алгоритмов умножения матриц.
На практике алгоритм Копперсмита—Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров.
↑«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), arXiv:1401.7714
Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. arXiv: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.
Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.
Гипотеза Штрассена — утверждение о том, что для сколь угодно малого существует алгоритм, при достаточно больших натуральных гарантирующий перемножение двух квадратных матриц размера за операций.
В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения. Класс P включён в более широкие классы сложности алгоритмов.
Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних, находятся все переменные системы.
Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Фолькером Штрассеном в 1969 году и является обобщением метода умножения Карацубы на матрицы.
Дискре́тное логарифми́рование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе .
Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению.
Метод умножения Шёнхаге — Штрассена — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует ) битовых операций, где — количество двоичных цифр в произведении.
Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц. Элементы новой матрицы получаются из элементов старых матриц в соответствии с правилами, проиллюстрированными ниже.
Алгоритм Фюрера — быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого умножения больших чисел представляет большой интерес в области криптографии с открытым ключом.
В математике матрица Коши — это матрица размера m × n с элементами вида
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места понимается задача, похожая на задачу о назначениях.
Алгоритм Бурникеля — Циглера — алгоритм деления больших целых чисел, описанный Кристофом Бурникелем и Йоахимом Циглером в 1998 году, позволяющий эффективно вычислить и частное, и остаток от деления.
Алгоритм Полларда — Штрассена является самым популярным среди алгоритмов факторизации целых чисел с экспоненциальной сложностью, так как имеет наилучшую оценку сложности и однозначно находит разложение числа n на два множителя за арифметических операций. Алгоритм основан на следующей теореме.
Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы, это группа алгоритмов в мультивариантном анализе и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым данным. Поскольку задача в общем случае неразрешима, её обычно численно аппроксимируют.
Алгоритм Харви — ван дер Хувена — алгоритм умножения двух -битных целых чисел с временной сложностью в модели многоленточной машины Тьюринга. Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.
Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая научные вычисления и распознавания образов, а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров.
Галакти́ческий алгори́тм — алгоритм, превосходящий любой другой алгоритм для решения существенно больши́х задач, где «существенно большие» задачи означают настолько большой масштаб, что такой алгоритм не используется на практике. Галактические алгоритмы были так названы Ричардом Липтоном и Кеном Риганом, поскольку они никогда не будут применимы на любых «земных», привычных нам данных.
Алгоритм Тоома — Кука, иногда упоминаемый как Tоом-3 — это алгоритм умножения больших чисел, названный именами Андрея Леоновича Тоома, предложившего новый алгоритм с низкой сложностью и Стивена Кука, более ясно его описавшего.
Цветовое кодирование — алгоритмическая техника, которая полезна для обнаружения структурных мотивов. Например, оно может быть использовано для обнаружения простого пути длины k в заданном графе. Традиционный алгоритм цветового кодирования является вероятностным, но он может быть дерандомизирован без существенного увеличения времени работы.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
