ОТЫСКАНИЕ КОМПЛЕКСНОЗНАЧНЫХ РЕШЕНИЙ УРАВНЕНИЙ БРЕНТА СВЕДЕНИЕМ К НЕЛИНЕЙНОЙ ЗАДАЧЕ НАИМЕНЬШИХ КВАДРАТОВ

Обложка

Цитировать

Полный текст

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

Аннотация

Отыскание нетривиальных решений трилинейных уравнений Брента соответствует построению асимптотически быстрых алгоритмов перемножения матриц является важной, но в общем случае весьма сложной вычислительной задачей. Предлагаются способы параметризации уравнений Брента, основанные на использовании симметрий тензора матричного произведения, которые позволяют многократно уменьшить размерность задачи. Численное решение полученных трилинейных или кубических систем нелинейных уравнений осуществляется посредством сведения к нелинейной задаче наименьших квадратов и применения к ней специально разработанного итерационного метода, не требующего вычисления производных. Найденные решения параметризованных уравнений Брента, как правило, имеют ранг не больший (а иногда и меньший) по сравнению с известными результатами. Так, получен алгоритм перемножения двух матриц 4-го порядка за48 активных умножений. Библ. 16. Табл. 1.

Об авторах

И. Е Капорин

ФИЦ ИУ РАН

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, 58 p.
  2. Strassen V. Gaussian elimination is not optimal //Numer. Math. 13, 354—356 (1969).
  3. Laderman J. D. A noncommutative algorithm for multiplying 3x3 matrices using 23 multiplications. Bull. Amer. Math. Soc. 82, 126-128 (1976).
  4. Pan V. How we can speed up matrix multiplication? // SIAM Review, 26(3), 393-415 (1984).
  5. Smirnov A. V. The bilinear complexity and practical algorithms for matrix multiplication // Comp. Math. Mathem. Phys. 53, 1781-1785 (2013).
  6. Karstadt E., Schwartz O. Matrix multiplication, a little faster // J. of the ACM (JACM). 2020, 67(1), 1-31.
  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. Oseledets I. V., Savostyanov D. V. Minimization methods for approximating tensors and their comparison // Computational Mathematics and Mathematical Physics, 2006, 46(10), 1641-1650
  9. Kaporin I. E., Axelsson O. On a class of nonlinear equation solvers based on the residual norm reduction over a sequence of affine subspaces // SIAM J. Sci. Comput. 16(1), 228-249 (1994)
  10. Kaporin I. Preconditioned Subspace Descent Method for Nonlinear Systems of Equations // Open Computer Science, 2020, 10(1), 71-81
  11. Kozak D., Molinari C., Rosasco L., Tenorio L., Villa S. Zeroth order optimization with orthogonal random directions. // Mathematical Programming. 2022. V. 199. P. 1-41.
  12. Armijo L. Minimization of functions having Lipschitz continuous first partial derivatives // Pacific Journal of mathematics 16(1), 1-3 (1966).
  13. Ballard G., Ikenmeyer C., Landsberg J. M., Ryder N. The geometry of rank decompositions of matrix multiplication II: 3x3 matrices. // Journal of Pure and Applied Algebra, 2019, 223(8), 3205-3224.
  14. Berger G. O., Absil P. A., De Lathauwer L., Jungers R. M., Van Barel M. Equivalent polyadic decompositions of matrix multiplication tensors // J. of Computational and Applied Mathematics, 2022, 406, 113941. https://doi.org/10.1016/j.cam.2021.113941.
  15. Hopcroft J. E., Kerr L. R. On minimizing the number of multiplications necessary for matrix multiplication // SIAM Journal on Applied Mathematics, 1971, 20(1):30—36.
  16. Fawzi A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 2022, 610(7930): 47-53.

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

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

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