×

Computing images of polynomial maps. (English) Zbl 1436.14099

It is well known that the image of a polynomial map is a constructible set. One may compute its closure in computer algebra systems however, a procedure for computing the constructible set itself is not known. In this paper, authors provide an algorithm, based on algebro-geometric techniques, addressing this problem. Afterwards, they apply the results presented in this paper to answer a question of W. Hackbusch on the non-closedness of site-independent cyclic matrix product states for infinitely many parameters.

MSC:

14Q15 Computational aspects of higher-dimensional varieties
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
15A69 Multilinear algebra, tensor calculus
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Buczyńska, W.; Wiśniewski, J., On the geometry of binary symmetric models of phylogenetic trees, J. Europ. Math. Soc., 9, 3, 609-635 (2007) · Zbl 1147.14027 · doi:10.4171/JEMS/90
[2] Buhrman, H., Christandl, M., Zuiddam, J.: Nondeterministic quantum communication complexity: The cyclic equality game and iterated matrix multiplication, arXiv:1603.03757 · Zbl 1402.68063
[3] Chen, C., Lemaire, F., Li, L., Maza, M., Pan, W., Xie, Y.: The ConstructibleSetTools and ParametricSystemTools modules of the RegularChains library in maple. In: International Conference on Computational Sciences and Its Applications, 2008, ICCSA’08, pp 342-352. IEEE (2008) · Zbl 1344.13001
[4] Chor, B.; Hendy, M.; Holland, B.; Penny, D., Multiple maxima of likelihood in phylogenetic trees: an analytic approach, Mol. Biol. Evol., 17, 10, 1529-1541 (2000) · doi:10.1093/oxfordjournals.molbev.a026252
[5] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. Springer (1992) · Zbl 0756.13017
[6] Drton, M., Sullivant, S.: Algebraic statistical models. Stat. Sin., 1273-1297 (2007) · Zbl 1132.62003
[7] De Silva, V.; Lim, L., Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., 30, 3, 1084-1127 (2008) · Zbl 1167.14038 · doi:10.1137/06066518X
[8] Grayson, D.R., Stillman, M.E.: Macaulay2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/
[9] Ganter, B., Algorithmen zur formalen Begriffsanalyse, Beiträge zur Begriffsanalyse (Darmstadt, 1986), 242-254 (1987), Mannheim: Bibliographisches Inst., Mannheim
[10] Geiger, D.; Meek, C.; Sturmfels, B., On the toric algebra of graphical models, Ann. Stat., 34, 3, 1463-1492 (2006) · Zbl 1104.60007 · doi:10.1214/009053606000000263
[11] Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus. Springer Science & Business Media (2012) · Zbl 1244.65061
[12] Hauenstein, J.; Ikenmeyer, C.; Landsberg, Jm, Equations for lower bounds on border rank, Exp. Math., 22, 4, 372-383 (2013) · Zbl 1361.68098 · doi:10.1080/10586458.2013.825892
[13] Hampe, S., Joswig, M., Schröter, B.: Algorithms for Tight Spans and Tropical Linear Spaces, arXiv:1612.03592 · Zbl 1498.05046
[14] Hopcroft, J.; Kerr, L., On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., 20, 1, 30-36 (1971) · Zbl 0215.55501 · doi:10.1137/0120004
[15] Landsberg, Jm, The border rank of the multiplication of 2x2 matrices is seven, J. Am. Math. Soc., 19, 2, 447-459 (2006) · Zbl 1088.68069 · doi:10.1090/S0894-0347-05-00506-0
[16] Landsberg, J.M.: Tensors: Geometry and Applications. American Mathematical Society (2012) · Zbl 1238.15013
[17] Landsberg, Jm; Michałek, M., On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM J. Appl. Algebra Geom., 1, 1, 2-19 (2017) · Zbl 1365.15034 · doi:10.1137/16M1067457
[18] Landsberg, Jm; Qi, Y.; Ye, K., On the geometry of tensor network states, Quant. Inf. Comput., 12, 3-4, 346-354 (2012) · Zbl 1268.81035
[19] Monagan, M.; Geddes, K.; Heal, K.; Labahn, G.; Vorkoetter, S.; Mccarron, J.; Demarco, P., Maple 10 Programming Guide (2005), Waterloo: Maplesoft, Waterloo
[20] Michałek, M., Geometry of phylogenetic group-based models, J. Algebra, 339, 1, 339-356 (2011) · Zbl 1251.14040 · doi:10.1016/j.jalgebra.2011.05.016
[21] Michałek, M., Toric varieties in phylogenetics, Dissertationes mathematicae, 2015, 511, 1-86 (2015) · Zbl 1375.14175
[22] Oseledets, Iv, Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018 · doi:10.1137/090752286
[23] Perez-Garcia, D.; Verstraete, F.; Wolf, M.; Cirac, J., Matrix product state representations, Quant. Inf. Comput., 7, 5, 401-430 (2007) · Zbl 1152.81795
[24] Qi, Y., Michałek, M., Lim, L.-H.: Complex tensors almost always have best low-rank approximations, to appear in Applied and Computational Harmonic Analysis. 10.1016/j.acha.2018.12.003
[25] Shafarevich, I.: Basic Algebraic Geometry, 1. Springer (2013) · Zbl 1277.14002
[26] Sturmfels, B.; Sullivant, S., Toric ideals of phylogenetic invariants, J. Comput. Biol., 12, 2, 204-228 (2005) · Zbl 1391.13058 · doi:10.1089/cmb.2005.12.204
[27] Szalay, S.; Pfeffer, M.; Murg, V.; Barcza, G.; Verstraete, F.; Schneider, R.; Legeza, Ö., Tensor product methods and entanglement optimization for ab initio quantum chemistry, Int. J. Quantum Chem., 115, 19, 1342-1391 (2015) · doi:10.1002/qua.24898
[28] Khrulkov, V., Hrinchuk, O., Oseledets, I: Generalized tensor models for recurrent neural networks, arXiv:1901.10801
[29] Khrulkov, V., Novikov, A., Oseledets, I: Expressive power of recurrent neural networks, arXiv:1711.00811
[30] Winograd, S., On multiplication of 2 × 2 matrices, Linear Algebra Appl., 4, 4, 381-388 (1971) · Zbl 0225.68018 · doi:10.1016/0024-3795(71)90009-7
[31] Wu, W.-T.: A zero structure theorem for polynomial equations solving, MM Research Preprints, 1(2) (1987)
[32] Zhao, Q., Zhou, G., Xie, S., Zhang, L., Cichocki, A: Tensor ring decomposition, arXiv:1606.05535
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.