Общая идея в умножении Карацубы, Гаусса и Штрассена

19

Тождества, используемые в алгоритмах умножения

кажется, очень тесно связаны. Есть ли общие абстрактные рамки / обобщения?

sdcvvc
источник
3
Посмотрите асимптотическое неравенство Шёнхаге.
Юваль Фильмус
О каких личностях ты говоришь? Мы должны прочитать все три статьи, чтобы ответить? Пожалуйста, добавьте соответствующую информацию к вашему вопросу.
Рафаэль
1
@Raphael: тождества, которые являются основой для алгоритмов, выражающих 4 умножения чисел с 3 умножениями и 8 умножений матриц с 7.
sdcvvc

Ответы:

5

Классический каркас - это билинейные алгоритмы и разложения по тензорным рангам; в основном, вы строите трехсторонний тензор, связанный с билинейным отображением f(A,B)=AB , на основе коэффициентов, затем ищите его разложение в виде суммы тензоров ранга один (т.е. такие как Ti,j,k=uivjwk ). Вы найдете это объясненным более подробно, например, в этой статье Bläser или в книге Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory,

Насколько я понимаю, переформулировка в терминах групповых представлений, которую Суреш упоминает в своем ответе, является более поздней, и я считаю, что она менее подходит для первого подхода к предмету (но, конечно, это может быть предвзятым с моей стороны ).

Федерико Полони
источник
1
Это правильный ответ. Один из аспектов, который отсутствует, - это тензорность «разделяй и властвуй», которая стоит за алгоритмом Карацубы и алгоритмами быстрого (квадратного) матричного умножения.
Юваль Фильмус
8

Частичным ответом на ваш вопрос является теоретико-групповой подход, впервые разработанный Коном и Умансом, а затем разработанный Коном, Клейнбергом, Сегеди и Уманом. Он может «сортировать» захват Штрассена и Копперсмита-Винограда для умножения матриц.

Суреш
источник
Это действительно упускает из виду. Теоретико-групповой подход на самом деле является лишь одним из способов создания таких тождеств в первую очередь.
Ювал Фильмус