Search Advanced

Electronic Research Archive

2025, Volume 33, Issue 9: 5252-5276. doi: 10.3934/era.2025235
Previous Article Next Article
Research article

Numerical algorithm and complexity analysis for diagonalization of multivariate homogeneous polynomials

  • School of Mathematical Sciences, Huaqiao University, Quanzhou 362021, China
  • Published: 05 September 2025

  • 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.

    Citation: Lishan Fang, Hua-Lin Huang, Yuechen Li. Numerical algorithm and complexity analysis for diagonalization of multivariate homogeneous polynomials[J]. Electronic Research Archive, 2025, 33(9): 5252-5276. doi: 10.3934/era.2025235

    Related Papers:

  • 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.



    加载中


    [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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 10.1002/cpa.21638
  • Reader Comments
  • © 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Electronic Research Archive
1.1 1.7

Metrics

Article views(454) PDF downloads(31) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(6)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog