- Более быстрое прямоугольное матричное умножение с помощью анализа комбинированных потерь (arXiv)
Автор : Франсуа Ле Галль
Аннотация: Дуань, Ву и Чжоу (FOCS 2023) недавно получили улучшенную верхнюю границу показателя степени умножения квадратных матриц ω‹2,3719, внедрив новый подход для количественной оценки и компенсации «комбинационных потерь» в предыдущем анализе мощностей медников. -тензор Винограда. В этой статье мы покажем, как использовать этот новый подход для улучшения показателя степени умножения прямоугольных матриц. Наш основной технический вклад показывает, как объединить этот анализ комбинированных потерь и анализ четвертой степени тензора Копперсмита-Винограда в контексте умножения прямоугольных матриц, разработанного Ле Галлом и Уррутиа (SODA 2018).
2. Эффективно-проверяемые сильные однозначно решаемые головоломки и умножение матриц (arXiv)
Автор: Мэттью Андерсон, Ву Ле.
Аннотация: Мы совершенствуем структуру Кона-Уманса для разработки быстрых алгоритмов умножения матриц. Мы вводим, анализируем и ищем новый подкласс сильных однозначно разрешимых головоломок (SUSP), которые мы называем упрощаемыми SUSP. Мы показываем, что эти головоломки поддаются эффективной проверке, что остается открытым вопросом для общих SUSP. Мы также показываем, что отдельные упрощаемые SUSP могут достигать той же строгости границ показателя матричного умножения ω, что и бесконечные семейства SUSP. Мы сообщаем о построении с помощью компьютерного поиска более крупных SUSP, чем было известно ранее для малой ширины. Это, в сочетании с нашим более точным анализом, усиливает верхнюю границу показателя матричного умножения с 2,66 до 2,505, получаемого с помощью этого вычислительного подхода, и приближается к результатам ручных построений Кона и др.
