УЛУЧШЕННЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ПЕРВОГО ГИПЕРДЕТЕРМИНАНТА КЭЛИ
https://doi.org/10.55452/1998-6688-2024-21-3-58-65
Аннотация
Комбинаторный гипердетерминант DET – это однородный многочлен от элементов гиперматрицы с четным числом индексов, который является единственным SL-инвариантом минимальной степени, который впервые стал изучать Кэли в середине XIX века. Учитывая его фундаментальную природу, вычисление этого многочлена является важной задачей в разных разделах науки. Для фиксированного d и кубической гиперматрицы 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
Просмотров:
326
Послать статью по эл. почте 