Гипотеза Штрассена

Гипотеза Штрассена — утверждение о том, что для сколь угодно малого $\varepsilon >0$ существует алгоритм, при достаточно больших натуральных $n$ гарантирующий перемножение двух квадратных матриц размера $n\times n$ за $O(n^{2+\varepsilon })$ операций.

Выдвинута Фолькером Штрассеном в 1969 году; по состоянию на 2023 год остаётся одной из важных нерешенных проблем линейной алгебры и теории сложности вычислений.

Задача перемножения двух больших квадратных матриц часто встречается в приложениях и её ускорение этой операции имеет большое практическое значение. Поскольку при умножении матриц надо вычислить $n^{2}$ новых, вообще говоря, разных значений элементов матриц, это нельзя сделать менее, чем за $O(n^{2})$ операций. Стандартный алгоритм согласно определению умножения матриц требует $O(n^{3})$ операций. Алгоритм Штрассена, опубликованный в 1969 году^[1], требовал ${O}(n^{\log _{2}7})\approx {O}(n^{2,81})$ умножений; в той же работе выдвинута гипотеза о возможности перемножать матрицы со скоростью, сколь угодно близкой к $O(n^{2})$ .

В 1990 году было доказано, что достаточно ${O}(n^{2,376})$ операций (алгоритм Копперсмита — Винограда)^[2]. Этот алгоритм имеет теоретическое значение и не может использоваться на практике, поскольку реально ускоряет умножение только для астрономически больших матриц. В дальнейшем было получено несколько очень незначительных улучшений последней оценки на базе того же метода^[3]. Это позволяет предположить существование «барьера Копперсмита — Винограда» в теоретических оценках сложности этой задачи, хотя большинство исследователей полагает, что гипотеза Штрассена верна. Показатель степени в практических алгоритмах был несколько улучшен по сравнению с показателем алгоритма Штрассена, но пока он остаётся существенно больше показателя алгоритма Копперсмита — Винограда.

Примечания

↑ Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354—356, 1969
↑ Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990
↑ Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier Архивная копия от 20 января 2013 на Wayback Machine

Ссылки

Strassen V. Gaussian Elimination is not Optimal (англ.) // Numerische Mathematik / F. Brezzi — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354—356. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF02165411

Похожие исследовательские статьи

Гипо́теза Ри́мана — сформулированная немецким математиком Бернхардом Риманом в 1859 году математическая гипотеза о том, что дзета-функция Ри́мана $\text{[math]}$ принимает нулевые значения только в отрицательных чётных числах: $\text{[math]}$ , и комплексных числах с вещественной частью $\text{[math]}$ . Гипотеза Римана касается расположения этих нетривиальных нулей и утверждает, что:

Быстрое преобразование Фурье — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем $\text{[math]}$ . Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность $\text{[math]}$ .

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Фолькером Штрассеном в 1969 году и является обобщением метода умножения Карацубы на матрицы.

Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом. В исходной версии асимптотическая сложность алгоритма составляла $\text{[math]}$ , где $\text{[math]}$ — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, обладает лучшей асимптотикой среди известных алгоритмов умножения матриц.

В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число $\text{[math]}$ , такое, что время работы алгоритма для всех входов длины $\text{[math]}$ не превосходит $\text{[math]}$ , то временную сложность данного алгоритма можно асимптотически оценить как $\text{[math]}$ .

Метод умножения Шёнхаге — Штрассена — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует $\text{[math]}$ ) битовых операций, где $\text{[math]}$ — количество двоичных цифр в произведении.

<span class="mw-page-title-main">Карацуба, Анатолий Алексеевич</span> советский и российский математик

Анато́лий Алексе́евич Карацу́ба — советский и российский математик. Создатель первого быстрого метода в истории математики — метода умножения больших чисел.

Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц. Элементы новой матрицы получаются из элементов старых матриц в соответствии с правилами, проиллюстрированными ниже.

Алгоритм Фюрера — быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого умножения больших чисел представляет большой интерес в области криптографии с открытым ключом.

Гипотеза Эрдёша об арифметических прогрессиях — предположение в аддитивной комбинаторике, сформулированное Палом Эрдёшем, согласно которому в случае, если сумма обратных величин положительных натуральных чисел некоторого множества расходится, то множество содержит сколь угодно длинные арифметические прогрессии.

Фо́лькер Штра́ссен — немецкий математик, почетный профессор кафедры математики и статистики Констанцского университета.

В математике матрица Коши — это матрица размера m × n с элементами вида

\text{[math]}

Алгоритм Полларда — Штрассена является самым популярным среди алгоритмов факторизации целых чисел с экспоненциальной сложностью, так как имеет наилучшую оценку сложности и однозначно находит разложение числа n на два множителя за $\text{[math]}$ арифметических операций. Алгоритм основан на следующей теореме.

Теорема Копперсмита — теорема, позволяющая эффективно найти все нули нормированных многочленов по определённому модулю.

Атака Копперсмита описывает класс криптографических атак на открытый ключ криптосистемы RSA, основанный на методе Копперсмита. Особенность применения этого метода для атак RSA включает случаи, когда открытая экспонента мала или когда частично известен секретный ключ.

Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу, когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами и логике.

Алгоритм Харви — ван дер Хувена — алгоритм умножения двух $\text{[math]}$ -битных целых чисел с временной сложностью $\text{[math]}$ в модели многоленточной машины Тьюринга. Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в $\text{[math]}$ на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.

Быстрый мультипольный метод (БММ) — это численный метод, разработанный для ускорения расчета дальнодействующих сил гравитационной задачи n-тел. Это достигается путем расширения функции Грина в системе с помощью многополюсного расширения, которое позволяет группировать источники сил, расположенные близко друг к другу, и обрабатывать их, как если бы они были одним источником силы.

Алгоритм Барейса — алгоритм вычисления определителя или приведения к ступенчатому виду матрицы с целыми элементами с помощью исключительно целочисленной арифметики. Назван именем Э. Барейса. Любое деление, выполняемое по алгоритму, гарантирует точное деление. Метод может быть использован также для вычисления определителя матрицы с (приблизительными) вещественными элементами, что исключает ошибки округления, за исключением ошибок, уже присутствующих во входных данных.

Поскольку умножение матриц является центральной операцией во многих численных алгоритмах, много усилий было вложено в повышение эффективности алгоритма умножения матриц. Приложения алгоритма умножения матриц в вычислительных задачах найдены во многих областях, включая научные вычисления и распознавания образов, а также во вроде бы не имеющих отношение к матрицам задачах, таких как подсчёт путей через граф. Было разработано много различных алгоритмов для умножения матриц на оборудовании различного типа, включая параллельные и распределённые системы, где вычисления распределены на несколько процессоров.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.