Тождества, используемые в алгоритмах умножения
кажется, очень тесно связаны. Есть ли общие абстрактные рамки / обобщения?
algorithms
matrices
sdcvvc
источник
источник
Ответы:
Классический каркас - это билинейные алгоритмы и разложения по тензорным рангам; в основном, вы строите трехсторонний тензор, связанный с билинейным отображениеме( A , B ) = A ⋅ B , на основе коэффициентов, затем ищите его разложение в виде суммы тензоров ранга один (т.е. такие как Tя , J , K= тыяvJвесК ). Вы найдете это объясненным более подробно, например, в этой статье Bläser или в книге Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory,
Насколько я понимаю, переформулировка в терминах групповых представлений, которую Суреш упоминает в своем ответе, является более поздней, и я считаю, что она менее подходит для первого подхода к предмету (но, конечно, это может быть предвзятым с моей стороны ).
источник
Частичным ответом на ваш вопрос является теоретико-групповой подход, впервые разработанный Коном и Умансом, а затем разработанный Коном, Клейнбергом, Сегеди и Уманом. Он может «сортировать» захват Штрассена и Копперсмита-Винограда для умножения матриц.
источник