Numerical algorithm and complexity analysis for diagonalization of multivariate homogeneous polynomials

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

We study the computational complexity of a diagonalization technique for multivariate homogeneous polynomials, expressing them as the sums of powers of independent linear forms. It is based on Harrison’s center theory and consists of a criterion and a diagonalization algorithm. Detailed formulations and the computational complexity of each component of the technique are given. The complexity analysis focuses on the impacts of the number of variables and the degree of given polynomials. We show that this criterion runs in polynomial time, and the diagonalization process performs efficiently in numerical experiments. Other diagonalization techniques are reviewed and compared in terms of complexity.

Keywords

multivariate homogeneous polynomial / diagonalization / complexity analysis / center / symmetric tensor

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] N. Kayal, Efficient algorithms for some special cases of the polynomial equivalence problem, in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1 (2011), 1409-1421. https://doi.org/10.5555/2133036.2133144

[2] P. Koiran, M. Skomra, Derandomization and absolute reconstruction for sums of powers of linear forms, Theor. Comput. Sci., 887 (2021), 63-84. https://doi.org/10.1016/j.tcs.2021.07.005

[3] P. Koiran, S. Saha, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Comput. Complexity, 32 (2023), 1-66. https://doi.org/10.1007/s00037-023-00239-8

[4] E. Robeva, Orthogonal decomposition of symmetric tensors, SIAM J. Matrix Anal. Appl., 37 (2016), 86-102. https://doi.org/10.1137/140989340

[5] P. Koiran, Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective, Linear Multilinear Algebra, 69 (2021), 2353-2388. https://doi.org/10.1080/03081087.2019.1674771

[6] T. Kolda, Orthogonal tensor decompositions, SIAM J. Matrix Anal. Appl., 23 (2000), 243-255. https://doi.org/10.1137/S0895479800368354

[7] A. Boralevi, J. Draisma, E. Horobeţ, E. Robeva, Orthogonal and unitary tensor decomposition from an algebraic perspective, Isr. J. Math., 222 (2017), 223-260. https://doi.org/10.1007/s11856-017-1588-6

[8] D. K. Harrison, A grothendieck ring of higher degree forms, J. Algebra, 35 (1975), 123-138. https://doi.org/10.1016/0021-8693(75)90039-3

[9] H. L. Huang, H. Lu, Y. Ye, C. Zhang, Diagonalizable higher degree forms and symmetric tensors, Linear Algebra Appl., 613 (2021), 151-169. https://doi.org/10.1016/j.laa.2020.12.018

[10] H. L. Huang, H. Lu, Y. Ye, C. Zhang, On centres and direct sum decompositions of higher degree forms, Linear Multilinear Algebra, 70 (2022), 7290-7306. https://doi.org/10.1080/03081087.2021.1985057

[11] E. Kaltofen, Factorization of polynomials given by straight-line programs, Adv. Comput. Res., 5 (1989), 375-412.

[12] H. L. Huang, L. Liao, H. Lu, Y. Ye, C. Zhang, Harrison center and products of sums of powers, Commun. Math. Stat., 2023 (2023). https://doi.org/10.1007/s40304-023-00367-1

[13] H. L. Huang, H. Lu, Y. Ye, C. Zhang, Centers of multilinear forms and applications, Linear Algebra Appl., 673 (2023), 160-176. https://doi.org/10.1016/j.laa.2023.05.012

[14] G. H. Golub, C. F. Van Loan, Matrix Computations , JHU Press, Baltimore, 2013.

[15] H. Y. Cheung, T. C. Kwok, L. C. Lau, Fast matrix rank algorithms and applications, J. ACM, 60 (2013), 1-25. https://doi.org/10.1145/2528404

[16] D. G. Cantor, E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inf., 28 (1991), 693-701. https://doi.org/10.1007/BF01178683

[17] S. Boyd, L. Vandenberghe, Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares , Cambridge University Press, Cambridge, 2018. https://doi.org/10.1017/9781108583664

[18] D. Bini, V. Y. Pan, Polynomial and Matrix Computations: Fundamental Algorithms , Springer Science & Business Media, Basel, 2012. https://doi.org/10.1007/978-1-4612-0265-3

[19] A. Cordero, J. L. Hueso, E. Martínez, J. R. Torregrosa, Increasing the convergence order of an iterative method for nonlinear systems, Appl. Math. Lett., 25 (2012), 2369-2374. https://doi.org/10.1016/j.aml.2012.07.005

[20] E. Kaltofen, B. M. Trager, Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators, J. Symb. Comput., 9 (1990), 301-320. https://doi.org/10.1016/S0747-7171(08)80015-6

[21] A. Sinhababu, T. Thierauf, Factorization of polynomials given by arithmetic branching programs, Comput. Complexity, 30 (2021). https://doi.org/10.1007/s00037-021-00215-0

[22] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, M. Telgarsky, Tensor decompositions for learning latent variable models, J. Mach. Learn. Res., 15 (2014) 2773-283. https://doi.org/10.5555/2627435.2697055

[23] J. Brachat, P. Comon, B. Mourrain, E. Tsigaridas, Symmetric tensor decopmosition, Linear Algebra Appl., 433 (2010), 1851-1872. https://doi.org/10.1016/j.laa.2010.06.046

[24] Y. Chen, E. J. Candés, Solving random quadratic systems of equations is nearly as easy as solving linear systems, Commun. Pure Appl. Math., 70 (2017), 822-883. https://doi.org/10.1002/cpa.21638