Gelß, Patrick; Klus, Stefan; Matera, Sebastian; Schütte, Christof Nearest-neighbor interaction systems in the tensor-train format. (English) Zbl 1377.82015 J. Comput. Phys. 341, 140-162 (2017). Summary: Low-rank tensor approximation approaches have become an important tool in the scientific computing community. The aim is to enable the simulation and analysis of high-dimensional problems which cannot be solved using conventional methods anymore due to the so-called curse of dimensionality. This requires techniques to handle linear operators defined on extremely large state spaces and to solve the resulting systems of linear equations or eigenvalue problems. In this paper, we present a systematic tensor-train decomposition for nearest-neighbor interaction systems which is applicable to a host of different problems. With the aid of this decomposition, it is possible to significantly reduce the memory consumption as well as the computational costs. Furthermore, it can be shown that in some cases the rank of the tensor decomposition does not depend on the network size. The format is thus feasible even for high-dimensional systems. We will illustrate the results with several guiding examples such as the Ising model, a system of coupled oscillators, and a CO oxidation model. Cited in 3 Documents MSC: 82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics 15A69 Multilinear algebra, tensor calculus 65F99 Numerical linear algebra 90B22 Queues and service in operations research 90B20 Traffic problems in operations research Keywords:tensor decompositions; tensor-train format; nearest-neighbor interactions; Ising models; linearly coupled oscillators; Markovian master equation; heterogeneous catalysis; queuing problems PDFBibTeX XMLCite \textit{P. Gelß} et al., J. Comput. Phys. 341, 140--162 (2017; Zbl 1377.82015) Full Text: DOI arXiv References: [1] White, S. R., Density matrix formulation for quantum renormalization groups, Phys. Rev. Lett., 69, 19, 2863-2866 (1992) [2] (Meyer, H.-D.; Gatti, F.; Worth, G. A., Multidimensional Quantum Dynamics: MCTDH Theory and Applications (2009), Wiley-VCH Verlag GmbH & Co. KGaA) [3] Jahnke, T.; Huisinga, W., A dynamical low-rank approach to the chemical master equation, Bull. Math. Biol., 70, 8, 2283-2302 (2008) · Zbl 1169.92021 [4] Kazeev, V.; Khammash, M.; Nip, M.; Schwab, C., Direct solution of the chemical master equation using quantized tensor trains, PLoS Comput. Biol., 10, 3, Article e1003359 pp. (2014) [5] Dolgov, S.; Khoromskij, B., Simultaneous state-time approximation of the chemical master equation using tensor product formats, Numer. Linear Algebra Appl., 22, 2, 197-219 (2015) · Zbl 1363.65117 [6] Kazeev, V.; Schwab, C., Tensor approximation of stationary distributions of chemical reaction networks, SIAM J. Matrix Anal. Appl., 36, 3, 1221-1247 (2015) · Zbl 1322.60155 [7] Gelß, P.; Matera, S.; Schütte, C., Solving the master equation without kinetic Monte Carlo: tensor train approximations for a CO oxidation model, J. Comput. Phys., 314, 489-502 (2016) · Zbl 1349.80031 [8] Buchholz, P., Product form approximations for communicating Markov processes, Perform. Eval., 67, 9, 797-815 (2010) [9] Kressner, D.; Macedo, F., Low-rank tensor methods for communicating Markov processes, (Quantitative Evaluation of Systems. Quantitative Evaluation of Systems, Lecture Notes in Computer Science, vol. 8657 (2014)), 25-40 [10] Beylkin, G.; Garcke, J.; Mohlenkamp, M. J., Multivariate regression and machine learning with sums of separable functions, SIAM J. Sci. Comput., 31, 3, 1840-1857 (2009) · Zbl 1190.62135 [11] Novikov, A.; Podoprikhin, D.; Osokin, A.; Vetrov, D., Tensorizing neural networks, (Cortes, C.; Lawrence, N. D.; Lee, D. D.; Sugiyama, M.; Garnett, R., Advances in Neural Information Processing Systems 28 (NIPS) (2015), Curran Associates, Inc.), 442-450 [12] Cohen, N.; Sharir, O.; Shashua, A., On the expressive power of deep learning: a tensor analysis (2015) [13] Klus, S.; Gelß, P.; Peitz, S.; Schütte, C., Tensor-based dynamic mode decomposition, SIAM J. Sci. Comput. (2016), submitted for publication [14] Oseledets, I. V., A new tensor decomposition, Dokl. Math., 80, 1, 495-496 (2009) · Zbl 1183.15023 [15] Oseledets, I. V.; Tyrtyshnikov, E. E., Breaking the curse of dimensionality, or how to use SVD in many dimensions, SIAM J. Sci. Comput., 31, 5, 3744-3759 (2009) · Zbl 1200.65028 [16] Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018 [17] Hackbusch, W.; Kühn, S., A new scheme for the tensor representation, J. Fourier Anal. Appl., 15, 5, 706-722 (2009) · Zbl 1188.15022 [18] Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31, 4, 2029-2054 (2010) · Zbl 1210.65090 [19] Arnold, A.; Jahnke, T., On the approximation of high-dimensional differential equations in the hierarchical Tucker format, BIT Numer. Math., 54, 2, 305-341 (2013) · Zbl 1308.65113 [20] Lubich, C.; Rohwedder, T.; Schneider, R.; Vandereycken, B., Dynamical approximation by hierarchical Tucker and tensor-train tensors, SIAM J. Matrix Anal. Appl., 34, 2, 470-494 (2013) · Zbl 1391.15087 [21] Holtz, S.; Rohwedder, T.; Schneider, R., On manifolds of tensors of fixed TT-rank, Numer. Math., 120, 4, 701-731 (2012) · Zbl 1242.15022 [22] Dolgov, S. V.; Savostyanov, D. V., Alternating minimal energy methods for linear systems in higher dimensions. Part II: faster algorithm and application to nonsymmetric systems (2013) [23] Hitchcock, F. L., The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6, 164-189 (1927) · JFM 53.0095.01 [24] Carroll, J. D.; Chang, J. J., Analysis of individual differences in multidimensional scaling via an n-way generalization of ‘Eckart-Young’ decomposition, Psychometrika, 35, 3, 283-319 (1970) · Zbl 0202.19101 [25] Sidiropoulos, N. D.; Bro, R.; Giannakis, G. B., Parallel factor analysis in sensor array processing, IEEE Trans. Signal Process., 48, 8, 2377-2388 (2000) [26] Lathauwer, L. D.; Castaing, J., Tensor-based techniques for the blind separation of DS-CDMA signals, Signal Process., 87, 2, 322-336 (2007) · Zbl 1186.94413 [27] de Silva, V.; Lim, L.-H., 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 [28] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029 [29] Oseledets, I. V.; Tyrtyshnikov, E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, 1, 70-88 (2010) · Zbl 1183.65040 [30] Falcó, A.; Hackbusch, W., On minimal subspaces in tensor representations, Found. Comput. Math., 12, 6, 765-803 (2012) · Zbl 1260.15040 [31] Kazeev, V.; Khoromskij, B. N., Low-rank explicit QTT representation of the Laplace operator and its inverse, SIAM J. Matrix Anal. Appl., 33, 3, 742-758 (2012) · Zbl 1268.15025 [32] Lin, Z., Distributed Control and Analysis of Coupled Cell Systems (2008), VDM Verlag [33] Winful, H. G.; Wang, S. S., Stability of phase locking in coupled semiconductor laser arrays, Appl. Phys. Lett., 53, 1894-1896 (1988) [34] Griffiths, J. B., The Theory of Classical Dynamics (1985), Cambridge University Press · Zbl 0566.70001 [35] Gillespie, D. T., A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Comput. Phys., 22, 4, 403-434 (1976) [36] Lenz, W., Beiträge zum Verständnis der magnetischen Eigenschaften in festen Körpern, Phys. Z., 21, 613-615 (1920) [37] Ising, E., Beitrag zur Theorie des Ferromagnetismus, Z. Phys., 31, 253-258 (1925) · Zbl 1439.82056 [38] Lievens, S.; Stoilova, N.; der Jeugt, J. V., Harmonic oscillators coupled by springs: discrete solutions as a Wigner quantum system, J. Math. Phys., 47, 11, 113504 (2006) · Zbl 1112.81068 [39] Plenio, M. B.; Hartley, J.; Eisert, J., Dynamics and manipulation of entanglement in coupled harmonic systems with many degrees of freedom, New J. Phys., 6 (2004) [40] van Kampen, N. G., Stochastic Processes in Physics and Chemistry (2007), North-Holland Personal Library, Elsevier B.V. · Zbl 0511.60038 [41] Gillespie, D. T., A rigorous derivation of the chemical master equation, Physica A, 188, 1-3, 404-425 (1992) [42] Hegland, M.; Burden, C.; Santoso, L.; MacNamara, S.; Booth, H., A solver for the stochastic master equation applied to gene regulatory networks, J. Comput. Appl. Math., 205, 2, 708-724 (2007) · Zbl 1121.65009 [43] Ammar, A.; Cueto, E.; Chinesta, F., Reduction of the chemical master equation for gene regulatory networks using proper generalized decompositions, Int. J. Numer. Methods Biomed. Eng., 28, 9, 960-973 (2012) [44] Holtz, S.; Rohwedder, T.; Schneider, R., The alternating linear scheme for tensor optimization in the tensor train format, SIAM J. Sci. Comput., 34, 2, A683-A713 (2012) · Zbl 1252.15031 [45] Oseledets, I. V., Approximation of matrices with logarithmic number of parameters, Dokl. Math., 80, 2, 653-654 (2009) · Zbl 1181.65065 [46] Oseledets, I. V., Approximation of \(2^d \times 2^d\) matrices using tensor decomposition, SIAM J. Matrix Anal. Appl., 31, 4, 2130-2145 (2010) · Zbl 1200.15005 [47] Khoromskij, B. N., O(d log n)-quantics approximation of n-d tensors in high-dimensional numerical modeling, Constr. Approx., 34, 2, 257-280 (2011) · Zbl 1228.65069 [48] Meskine, H.; Matera, S.; Scheffler, M.; Reuter, K.; Metiu, H., Examination of the concept of degree of rate control by first-principles kinetic Monte Carlo simulations, Surf. Sci., 603, 10, 1724-1730 (2009) [49] Reuter, K.; Scheffler, M., First-principles kinetic Monte Carlo simulations for heterogeneous catalysis: application to the CO oxidation at \(RuO_2(110)\), Phys. Rev. B, 73, 4, Article 045433 pp. (2006) [50] Matera, S.; Meskine, H.; Reuter, K., Adlayer inhomogeneity without lateral interactions: rationalizing correlation effects in CO oxidation at \(RuO_2(110)\) with first-principles kinetic Monte Carlo, J. Chem. Phys., 134, Article 064713 pp. (2011) [51] Hackbusch, W., Tensor spaces and numerical tensor calculus, (Springer Series in Computational Mathematics, vol. 42 (2012), Springer) · Zbl 1244.65061 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.