КЭЙЛИ БІРІНШІ ГИПЕРДЕТЕРМИНАНТЫН ЕСЕПТЕУДІҢ ЖЕТІЛДІРІЛГЕН АЛГОРИТМІ
https://doi.org/10.55452/1998-6688-2024-21-3-58-65
Аннотация
Комбинаторлық гипердетерминант DET – бұл жұп индекстер саны бар гиперматрица жазбалары бойынша біртекті көпмүше, сондай-ақ ол ең төменгі дәрежелі жалғыз SL-инварианты. Бұл тұжырымды алғаш рет 19 ғасырдың ортасында Кэйли зерттеген. Оның іргелі сипатына байланысты бұл көпмүшенің есебін шығару маңызды мәселеге айналды. Барвинок белгілі бір d және ұзындығы n болатын кубтық гиперматрица X үшін гипердетерминантты есептеудің 0(2nd nd-1) алгоритмін ұсынды. DET(X) гипердетерминантының берілген гиперматрица X үшін нөлге тең болу мәселесі NP-қатерлі болғандықтан, гипердетерминантты тиімді есептеу алгоритмін анықтау қажет, себебі есептің көлемі экспоненциалды түрде өседі. Біз гипердетерминантты есептеудің жақсартылған алгоритмін ұсынамыз, ол 0(2n(d-1) nd-1)арифметикалық операцияларды қажет етеді.
Автор туралы
Ә. Аманов
Қазақстан-Британ техникалық университет
Қазақстан
Қазақстан
докторант
050000, Алматы қ.
Әдебиет тізімі
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.
Рецензия
Дәйектеу үшін:
Аманов Ә. КЭЙЛИ БІРІНШІ ГИПЕРДЕТЕРМИНАНТЫН ЕСЕПТЕУДІҢ ЖЕТІЛДІРІЛГЕН АЛГОРИТМІ. Қазақстан-Британ техникалық университетінің хабаршысы. 2024;21(3):58-65. https://doi.org/10.55452/1998-6688-2024-21-3-58-65
For citation:
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
Қараулар:
329
Мақаланы эл. пошта арқылы жіберу 