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

рассмотрели в своих работах алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали, что гипотеза Штрассена справедлива (т.е. минимальная...

Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм умножения больших целых чисел, основанный на быстром преобразовании...

появления алгоритма Штрассена в 1960-х годах, но оптимальное время остаётся неизвестным (то есть, неизвестна сложность задачи). К концу 2020 года алгоритм умножения...

Алгоритм Полларда — Штрассена однозначно находит разложение числа n {\displaystyle n} на два множителя за O ( n 1 / 4 log 4 ⁡ n ) {\displaystyle O(n^{1/4}\log...

небольших размерностей. Так для матриц 4X4 алгоритм Штрассена требует 49 умножений, а AlphaTensor нашёл алгоритм, требующий 47 умножений, но работает он...

стандартный алгоритм перемножения матриц требует n3 умножений (хотя существуют и более быстрые алгоритмы, например, алгоритм Штрассена). Степень многочлена...

Гипотеза Штрассена — утверждение о том, что для сколь угодно малого ε > 0 {\displaystyle \varepsilon >0} существует алгоритм, при достаточно больших натуральных...

3728596}).} Алгоритм Штрассена Гипотеза Штрассена Открытые математические проблемы — определить точную нижнюю границу сложности алгоритма умножения матриц...

предложен тест Соловея — Штрассена на простоту, он был опубликован в 1977 году, дополнения к нему в 1978 году. Тест Соловея — Штрассена опирается на малую теорему...

Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого...

анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй...

результат, известный сегодня как принцип инвариантности Штрассена или закон повторного логарифма Штрассена, обильно цитировался и был представлен в 1966 году...

} Для ускорения алгоритма Евклида могут быть использованы современные алгоритмические методы, основанные на методе Шёнхаге — Штрассена для быстрого целочисленного...

включая поиск ближайшего соседа, см. книгу Ханана Самета[англ.]. Алгоритм Штрассена для умножения матриц базируется на разбиении матриц на четыре блока...

Карацубы, алгоритмам быстрой сортировки и сортировки слиянием, алгоритму Штрассена для умножения матриц и быстрых преобразований Фурье. Во всех этих примерах...

алгоритмов факторизации, такие как метод квадратичных форм Шенкса и алгоритм Полларда — Штрассена, требуют времени порядка M 1 / 4 . {\displaystyle M^{1/4}.}...

улучшение алгоритма со сложностью O(N3) — алгоритм Штрассена, рекурсивный алгоритм со сложностью (N2,807). Этот алгоритм ещё не является галактическим, он используется...

O(n^{c})} . Если в вычислениях используется метод умножения Шёнхаге — Штрассена с O ( n log ⁡ n log ⁡ log ⁡ n ) {\displaystyle O(n\log n\log \log n)}...

Расширенный алгоритм Евклида — модификация алгоритма Евклида, вычисляющая, кроме наибольшего общего делителя (НОД) целых чисел a {\displaystyle a} и b...

Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, LLL-алгоритм) — алгоритм редукции базиса решётки[англ.], разработанный Арьеном Ленстрой, Хендриком...

ε ) {\displaystyle O(n^{1/5+\varepsilon })} . В отличие от алгоритма Полларда - Штрассена не требует выделения больших объёмов памяти, к тому же имеет...

Соловея — Штрассена, показывают большую эффективность использования и простоту выражения по сравнению с детерминированными тестами. Алгоритм Миллера-Рабина...

алгоритмов умножения[англ.], таких как Алгоритм Карацубы, умножение Тума – Кука[англ.], или алгоритм Шёнхаге — Штрассена. В результате вычислительная сложность...

/ 3n³ + 2n², независимо от фактически используемого алгоритма. Использование алгоритма Штрассена не допускается, поскольку оно искажает реальную скорость...

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

заданная алгоритмом Шёнхаге и Штрассена оставалась без улучшений. Только в 2007 году, спустя 36 лет, Мартин Фюрер предложил алгоритм со временем работы O ( n...

размера, пока не был обнаружен асимптотически более быстрый алгоритм Шёнхаге — Штрассена (со сложностью Θ ( n log ⁡ n log ⁡ log ⁡ n ) ) {\displaystyle...

Применяем алгоритм Полларда-Штрассена, выбирая за t {\displaystyle t} неразложенную часть, получим разложение a {\displaystyle a} . Сложность алгоритма Диксона...

проблема простоты. Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число N {\displaystyle N} , позволяет либо не...

Также известны алгоритмы основанные на быстром умножении матриц, например на алгоритмах Штрассена и Копперсмита-Винограда. Свои алгоритмы были предложены...