Восстановление Алгоритма Штрассена С Помощью Нейронных Сетей

Быстрое умножение матриц можно представить как поиск низкоранговых разложений тензора матричного умножения. Мы разработали нейронную архитектуру, названную \textsc{StrassenNet}, которая воспроизводит алгоритм Штрассена для умножения матриц размером $2\times 2$. В ходе многочисленных независимых запусков нейронная сеть всегда сходится к тензору ранга 7, тем самым численно восстанавливая оптимальный алгоритм Штрассена.

Восстановление алгоритма Штрассена

Далее мы обучили ту же архитектуру на умножении матриц размером $3\times 3$ с рангом $r$, принимающим значения от 19 до 23. Наши эксперименты выявили четкий численный порог: модели с $r=23$ достигают значительно более низкой ошибки валидации, чем модели с $r\le 22$. Это позволяет предположить, что $r=23$ может быть наименьшим эффективным рангом тензора матричного умножения $3\times 3$.

Расширение метода на пограничные разложения

Мы также наметили расширение метода на пограничные разложения с использованием $\varepsilon$-параметризации и представили предварительные результаты, соответствующие известным границам для пограничного ранга тензора матричного умножения $3\times 3$. Пограничные разложения представляют интерес, поскольку позволяют аппроксимировать тензор матричного умножения с использованием разложений, которые не являются строго низкоранговыми, но приближаются к ним по мере уменьшения $\varepsilon$. Полученные результаты подтверждают теоретические оценки и указывают на перспективность применения данного подхода для исследования и оптимизации алгоритмов умножения матриц.