- Код статьи
- 10.31857/S2686954324040056-1
- DOI
- 10.31857/S2686954324040056
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 518 / Номер выпуска 1
- Страницы
- 29-34
- Аннотация
- Предлагается параметризация канонических разложений тензоров матричного произведения с многократно меньшим (по сравнению со стандартными уравнениями Брента) числом переменных. Последние определяются численно с использованием итерационного метода решения задачи нелинейных наименьших квадратов. Получены более быстрые по сравнению с известными алгоритмы перемножения двух 4 × 4-матриц за 48 умножений и 2 × 4-матрицы на 4 × 5-матрицу за 32 умножения.
- Ключевые слова
- быстрое умножение матриц алгоритм Штрассена уравнения Брента
- Дата публикации
- 15.06.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 38
Библиография
- 1. Brent R.P. Algorithms for matrix multiplication. (Report No. STAN-CS-70-157). Stanford Univ. CA Dept. of Computer Science, 1970, 58p.
- 2. Strassen V. Gaussian elimination is not optimal // Numer. Math. 1969. V. 13. № 4. P. 354–356.
- 3. Смирнов А.В. О билинейной сложности и практических алгоритмах умножения матриц // ЖВМ и МФ. 2013. Т. 53. № 12. С. 1970–1984.
- 4. Beniamini G. et al., Sparsifying the operators of fast matrix multiplication algorithms. arXiv preprint arXiv:2008.03759 (2020) https://arxiv.org/pdf/2008.03759.pdf
- 5. Ballard G., Ikenmeyer C., Landsberg J.M., Ryder N. The geometry of rank decompositions of matrix multiplication II: 3×3 matrices // J. of Pure and Applied Algebra. 2019. V. 223. № 8. P. 3205–3224.
- 6. Laderman J.D. A noncommutative algorithm for multiplying 3x3 matrices using 23 multiplications // Bull. Amer. Math. Soc. 1976. V. 82. № 1. P. 126–128.
- 7. Kaporin I. A derivative-free nonlinear least squares solver. In: Olenev N.N., Evtushenko Y.G., Jacimovic M., Khachay M., Malkova V. (eds.) Optimization and Applications. OPTIMA 2021. Lecture Notes in Computer Science, V. 13078. P. 217–230. Springer, Cham, 2021. https://doi.org/10.1007/978-3-030-91059-4_16
- 8. Kaporin I. Verifying the correctness of the (4,4,4;48) matrix multiplication scheme with complex coefficients exact up to the floating point tolerance // 2024. URL: https://cloud.mail.ru/public/Yfij/ErDxopqBh
- 9. Hopcroft J.E., Kerr L.R. On minimizing the number of multiplications necessary for matrix multiplication // SIAM Journal on Appl. Math. 1971. V. 20. № 1 P. 30–36.
- 10. Berger G.O., Absil P.A., De Lathauwer L., Jungers R.M., Van Barel M. Equivalent polyadic decompositions of matrix multiplication tensors // J. of Comput. and Appl. Math. 2022. V. 406. P. 113941. https://doi.org/10.1016/j.cam.2021.113941
- 11. Fawzi A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning // Nature. 2022. V. 610. № 7930. P. 47–53.
- 12. Li X., Zhang L., Ke Y. Deflation conjecture and local dimensions of Brent equations // arXiv preprint arXiv:2310.11686. 2023 Oct 18.
- 13. Ballard G., Weissenberger J., Zhang L. Accelerating neural network training using arbitrary precision approximating matrix multiplication algorithms // 50th International Conference on Parallel Processing Workshop 2021 Aug 9. P. 1–8. https://doi.org/10.1145/3458744.3474050
