Численно-аналитическое решение уравнений Брента

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Предлагается параметризация канонических разложений тензоров матричного произведения с многократно меньшим (по сравнению со стандартными уравнениями Брента) числом переменных. Последние определяются численно с использованием итерационного метода решения задачи нелинейных наименьших квадратов. Получены более быстрые по сравнению с известными алгоритмы перемножения двух 4 × 4-матриц за 48 умножений и 2 × 4-матрицы на 4 × 5-матрицу за 32 умножения.

Об авторах

И. Е. Капорин

Федеральный исследовательский центр “Информатика и управление” Российской академии наук

Автор, ответственный за переписку.
Email: igorkaporin@mail.ru
Россия, Москва

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024