×

Nearest-neighbor interaction systems in the tensor-train format. (English) Zbl 1377.82015

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.

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
PDFBibTeX XMLCite
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.