ENHANCED ALGORITHM FOR COMPUTING CAYLEY’S FIRST HYPERDETERMINANT
https://doi.org/10.55452/1998-6688-2024-21-3-58-65
Abstract
Combinatorial hyperdeterminant DET – is the homogeneous polynomial in the entries of a hypermatrix of even number of indices, which is also a unique SL-invariant of minimal degree. It was first studied by Cayley in the middle of 19-th century. Given its fundamental nature, the computation of this polynomial is an important task. For fixed d and a cubical hypermatrix X of length n Barvinok introduced an algorithm of computing hyperdeterminant in 0(2nd nd-1) . Since the problem of deciding whether for the given hypermatrix X the hyperdeterminant DET(X) is equal to zero is NP-hard, it is essential to develop efficient algorithm for computing hyperdeterminant, as the size of problem grows exponentially. We provide enhanced algorithm of computing hyperdeterminant that requires 0(2 n(d-1) nd-1) arithmetic operations.
Supporting agencies: This research was supported by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP14869221).
About the Author
A. Amanov
Kazakh-British Technical University
Kazakhstan
Kazakhstan
PhD student
050000, Almaty
References
1. Cayley A. On the theory of determinants. Pitt Press, 1844.
2. Cayley A. On the theory of linear transformations. E. Johnson, 1845.
3. Barvinok A.I. New algorithms for linear k-matroid intersection and matroid k-parity problems. Mathematical Programming. 1995 Jul, 69:449–70.
4. Hillar C.J., Lim L.H. Most tensor problems are NP-hard. Journal of the ACM (JACM), 2013, 60(6), 1–39.
5. Gelfand I.M., Kapranov M.M., and Zelevinsky A.V., Hyperdeterminants, Advances in Mathematics, Dec. 1992, vol. 96, no. 2, pp. 226-263. https://doi.org/10.1016/0001-8708(92)90056-q
6. Sokolov N.P. Introduction to the theory of multidimensional matrices, Nukova Dumka, Kiev, 1972. [in Russian]
7. Luque J.G., and Thibon J.Y. Hankel hyperdeterminants and Selberg integrals. Journal of Physics A: mathematical and general, 2003, vol.36, no. 19, p. 5267.
8. Amanov A. and Yeliussizov D. Tensor slice rank and Cayley's first hyperdeterminant. Linear Algebra and its Applications, 2023, 656, pp. 224–246.
9. Cifuentes D. and Parrilo P.A. An efficient tree decomposition method for permanents and mixed discriminants. Linear Algebra and its Applications, 2016, 493, pp. 45–81.
10. Lim L.-H. Tensors and hypermatrices, Handbook of Linear Algebra, 2013, pp. 231–260.
11. Grochow J.A., & Qiao Y. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, Leibniz International Proceedings in Informatics (LIPIcs), 2021, vol. 2021, pp. 31:1-31:19, https://doi.org/10.4230/LIPIcs.ITCS.2021.31.
12. Lammers P.A generalisation of the honeycomb dimer model to higher dimensions. The Annals of Probability, 2021, vol. 49, no. 2, pp. 1033–66.
13. Zappa P. The Cayley determinant of the determinant tensor and the Alon–Tarsi conjecture. Advances in Applied Mathematics, 1997 Jul 1, vol. 19, no.1, pp. 31–44.
14. Blasiak J., Church T., Cohn H., Grochow J.A., Naslund E., Sawin W.F., and C. Umans. On cap sets and the group-theoretic approach to matrix multiplication, Discrete Anal., 2017, paper no. 3, 27 p.
15. Mukhametzhanov B. Half-wormholes in SYK with one time point. SciPost Physics, 2022, vol. 12, no. 1, p. 029.
16. Wigderson A. Non-commutative Optimization-Where Algebra, Analysis and Computational Complexity Meet. InProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation 2022 Jul 4, pp. 13–19.
17. Dobes I., Jing N. Qubits as hypermatrices and entanglement. Physica Scripta. 2024 Apr 11, vol. 99, no. 5, p. 055110.
18. Turatti E. On tensors that are determined by their singular tuples. SIAM Journal on Applied Algebra and Geometry, 2022, vol. 6, no. 2, pp. 319–338.
19. Lim LH. Tensors in computations. Acta Numerica. 2021 May, no. 30, pp. 555–764.
20. Zheng YN. The characteristic polynomial of the complete 3-uniform hypergraph. Linear Algebra and its Applications. 2021 Oct 15, no. 627, pp. 275–286.
21. Matsumoto S. Hyperdeterminantal expressions for Jack functions of rectangular shapes. Journal of Algebra. 2008 Jul 15, vol. 320, no. 2, pp. 612–632.
Review
For citations:
Amanov A. ENHANCED ALGORITHM FOR COMPUTING CAYLEY’S FIRST HYPERDETERMINANT. Herald of the Kazakh-British technical university. 2024;21(3):58-65. https://doi.org/10.55452/1998-6688-2024-21-3-58-65
Views:
327
Email this article 