kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2024-21-3-58-65kaz29-1369Research ArticleКОМПЬЮТЕРНЫЕ НАУКИCOMPUTER SCIENCEУЛУЧШЕННЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ПЕРВОГО ГИПЕРДЕТЕРМИНАНТА КЭЛИENHANCED ALGORITHM FOR COMPUTING CAYLEY’S FIRST HYPERDETERMINANThttps://orcid.org/0000-0002-7669-0656АмановА.AmanovA.

докторант 

050000, г. Алматы

PhD student 

050000, Almaty

alimzhan.amanov@gmail.comКазахстанско-Британский технический университетКазахстанKazakh-British Technical UniversityKazakhstan2024011020242135865Copyright © Аманов А., 20242024Аманов А.Amanov A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/1369

Комбинаторный гипердетерминант DET – это однородный многочлен от элементов гиперматрицы с четным числом индексов, который является единственным SL-инвариантом минимальной степени, который впервые стал изучать Кэли в середине XIX века. Учитывая его фундаментальную природу, вычисление этого многочлена является важной задачей в разных разделах науки. Для фиксированного d и кубической гиперматрицы X Барвинок предложил алгоритм вычисления гипердетерминанта, используя  0(2nd nd-1)арифметических операций. Поскольку задача определения, равен ли гипердетерминант DET(X) данной гиперматрицы X нулю, является NP-трудной, крайне важно разработать наиболее эффективный алгоритм, так как размер задачи растет экспоненциально. Мы предлагаем улучшенный алгоритм вычисления гипердетерминанта, который требует 0(2n(d-1) nd-1) арифметических операций.

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.

первый гипердетерминант КэлиSL-инвариантразложение ЛапласаCayley’s first hyperdeterminantSL-invariantLaplace expansionThis research was supported by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP14869221).ReferencesCayley A. On the theory of determinants. Pitt Press, 1844.Cayley A. On the theory of determinants. Pitt Press, 1844.Cayley A. On the theory of linear transformations. E. Johnson, 1845.Cayley A. On the theory of linear transformations. E. Johnson, 1845.Barvinok A.I. New algorithms for linear k-matroid intersection and matroid k-parity problems. Mathematical Programming. 1995 Jul, 69:449–70.Barvinok A.I. New algorithms for linear k-matroid intersection and matroid k-parity problems. Mathematical Programming. 1995 Jul, 69:449–70.Hillar C.J., Lim L.H. Most tensor problems are NP-hard. Journal of the ACM (JACM), 2013, 60(6), 1–39.Hillar C.J., Lim L.H. Most tensor problems are NP-hard. Journal of the ACM (JACM), 2013, 60(6), 1–39.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-qGelfand 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-qSokolov N.P. Introduction to the theory of multidimensional matrices, Nukova Dumka, Kiev, 1972. [in Russian]Sokolov N.P. Introduction to the theory of multidimensional matrices, Nukova Dumka, Kiev, 1972. [in Russian]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.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.Amanov A. and Yeliussizov D. Tensor slice rank and Cayley's first hyperdeterminant. Linear Algebra and its Applications, 2023, 656, pp. 224–246.Amanov A. and Yeliussizov D. Tensor slice rank and Cayley's first hyperdeterminant. Linear Algebra and its Applications, 2023, 656, pp. 224–246.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.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.Lim L.-H. Tensors and hypermatrices, Handbook of Linear Algebra, 2013, pp. 231–260.Lim L.-H. Tensors and hypermatrices, Handbook of Linear Algebra, 2013, pp. 231–260.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.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.Lammers P.A generalisation of the honeycomb dimer model to higher dimensions. The Annals of Probability, 2021, vol. 49, no. 2, pp. 1033–66.Lammers P.A generalisation of the honeycomb dimer model to higher dimensions. The Annals of Probability, 2021, vol. 49, no. 2, pp. 1033–66.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.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.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.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.Mukhametzhanov B. Half-wormholes in SYK with one time point. SciPost Physics, 2022, vol. 12, no. 1, p. 029.Mukhametzhanov B. Half-wormholes in SYK with one time point. SciPost Physics, 2022, vol. 12, no. 1, p. 029.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.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.Dobes I., Jing N. Qubits as hypermatrices and entanglement. Physica Scripta. 2024 Apr 11, vol. 99, no. 5, p. 055110.Dobes I., Jing N. Qubits as hypermatrices and entanglement. Physica Scripta. 2024 Apr 11, vol. 99, no. 5, p. 055110.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.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.Lim LH. Tensors in computations. Acta Numerica. 2021 May, no. 30, pp. 555–764.Lim LH. Tensors in computations. Acta Numerica. 2021 May, no. 30, pp. 555–764.Zheng YN. The characteristic polynomial of the complete 3-uniform hypergraph. Linear Algebra and its Applications. 2021 Oct 15, no. 627, pp. 275–286.Zheng YN. The characteristic polynomial of the complete 3-uniform hypergraph. Linear Algebra and its Applications. 2021 Oct 15, no. 627, pp. 275–286.Matsumoto S. Hyperdeterminantal expressions for Jack functions of rectangular shapes. Journal of Algebra. 2008 Jul 15, vol. 320, no. 2, pp. 612–632.Matsumoto S. Hyperdeterminantal expressions for Jack functions of rectangular shapes. Journal of Algebra. 2008 Jul 15, vol. 320, no. 2, pp. 612–632.

The authors declare that there are no conflicts of interest present.