A low-rank approach to the computation of path integrals. (English) Zbl 1349.65549
Summary: We present a method for solving the reaction-diffusion equation with general potential in free space. It is based on the approximation of the Feynman-Kac formula by a sequence of convolutions on sequentially diminishing grids. For computation of the convolutions we propose a fast algorithm based on the low-rank approximation of the Hankel matrices. The algorithm has complexity of \(\mathcal{O}(n r M \log M + n r^2 M)\) flops and requires \(\mathcal{O}(M r)\) floating-point numbers in memory, where \(n\) is the dimension of the integral, \(r \ll n\), and \(M\) is the mesh size in one dimension. The presented technique can be generalized to the higher-order diffusion processes.
MSC:
| 65M99 | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
| 60J65 | Brownian motion |
Keywords:
low-rank approximation; Feynman-Kac formula; path integral; multidimensional integration; skeleton approximation; convolutionReferences:
| [1] | Feynman, R. P., Space-time approach to non-relativistic quantum mechanics, Rev. Mod. Phys., 20, 367-387 (1948) · Zbl 1371.81126 |
| [2] | Feynman, R.; Hibbs, A., Quantum Mechanics and Path Integrals, Int. Ser. Pure Appl. Phys. (1965), McGraw-Hill · Zbl 0176.54902 |
| [3] | Garrod, C., Hamiltonian path-integral methods, Rev. Mod. Phys., 38, 483-494 (1966) · Zbl 0192.30403 |
| [4] | Abrikosov, A. A.; Dzyaloshinskii, I.; Gorkov, L. P., Methods of Quantum Field Theory in Statistical Physics (1975), Dover |
| [5] | Mahan, G., Many-Particle Physics. Physics of Solids and Liquids (2000), Springer |
| [6] | Norman Bleistein, R. A.H., Asymptotic Expansions of Integrals (2010), Dover Edition |
| [7] | Zinn-Justin, J., Quantum Field Theory and Critical Phenomena (1996), Clarendon Press: Clarendon Press Oxford · Zbl 0865.00014 |
| [8] | Polonyi, J., Lectures on the functional renormalization group method, Cent. Eur. J. Phys., 1, 1 (2003) |
| [9] | Dick, J.; Kuo, F.; Peters, G.; Sloan, I., Monte Carlo and Quasi-Monte Carlo Methods (2012), Springer |
| [10] | Holtz, M., Sparse Grid Quadrature in High Dimensions with Applications in Finance and Insurance, Lect. Notes Comput. Sci. Eng., vol. 77 (2011), Springer · Zbl 1221.65080 |
| [11] | Garcke, J.; Griebel, M., Sparse Grids and Applications (2013), Springer |
| [12] | Wong, K. Y., Review of Feynman’s path integral in quantum statistics: from the molecular Schrodinger equation to Kleinert’s variational perturbation theory, Commun. Comput. Phys., 15, 4 (2014) · Zbl 1373.81219 |
| [13] | Masujima, M., Path Integral Quantization and Stochastic Quantization (2008), Springer · Zbl 1171.81002 |
| [14] | Kleinert, H., Path Integrals in Quantum Mechanics, Statistics, Polymer Physics, and Financial Markets (2009), World Scientific · Zbl 1169.81001 |
| [15] | Crank, J., The Mathematics of Diffusion (1975), Clarendon Press: Clarendon Press Oxford · Zbl 0071.41401 |
| [16] | Bass, R. F., Diffusions and Elliptic Operators (1998), Springer · Zbl 0914.60009 |
| [17] | Chaichian, A.; Demichev, A., Path Integrals in Physics, vol. I (2001), IoP Publishing · Zbl 1074.81537 |
| [18] | Borodin, A. N.; Salminen, P., Handbook of Brownian Motion. Facts and Formulae (2002), Springer · Zbl 1012.60003 |
| [19] | Kac, M., On some connections between probability theory and differential and integral equations (1951) · Zbl 0045.07002 |
| [20] | Karatzas, I.; Shreve, S. E., Brownian Motion and Partial Differential Equations (1991), Springer |
| [21] | Mazo, R. M., Brownian Motion. Fluctuations, Dynamics, and Applications (2002), Clarendon Press: Clarendon Press Oxford · Zbl 1140.60001 |
| [22] | Nelson, E., Dynamical Theories of Brownian Motion (2001), Princeton University Press · Zbl 1375.60013 |
| [23] | Smolyak, S. A., Quadrature and interpolation formulas for tensor products of certain class of functions, Dokl. Akad. Nauk SSSR. Dokl. Akad. Nauk SSSR, Sov. Math. Dokl., 4, 5, 240-243 (1963), Transl.: · Zbl 0202.39901 |
| [24] | Gerstner, T.; Griebel, M., Dimension-adaptive tensor-product quadrature, Computing, 71, 65-87 (2003) · Zbl 1030.65015 |
| [25] | Gerstner, T.; Griebel, M., Numerical integration using sparse grids, Numer. Algorithms, 18, 3-4, 209-232 (1998) · Zbl 0921.65022 |
| [26] | Makri, N.; Miller, W. H., Monte Carlo integration with oscillatory integrands: implications for Feynman path integration in real time, Chem. Phys. Lett., 139, 1, 10-14 (1987) |
| [27] | Gorshkov, V. N.; Tretiak, S.; Mozyrsky, D., Semiclassical Monte-Carlo approach for modelling non-adiabatic dynamics in extended molecules, Nat. Commun., 4, 1-8 (2013) |
| [28] | de Lathauwer, L., A survey of tensor methods, (IEEE International Symposium on Circuits and Systems (2009)), 2773-2776 |
| [29] | Smilde, A.; Bro, R.; Geladi, P., Multi-way Analysis with Applications in the Chemical Sciences (2004), Wiley |
| [30] | Khoromskij, B. N., Introduction to tensor numerical methods in scientific computing (2010), University of Zürich, Preprint, Lecture Notes 06-2011 |
| [31] | Khoromskij, B. N., Tensor-structured numerical methods in scientific computing: survey on recent advances, Chemom. Intell. Lab. Syst., 110, 1, 1-19 (2012) |
| [32] | Hitchcock, F. L., The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6, 1, 164-189 (1927) · JFM 53.0095.01 |
| [33] | Hitchcock, F. L., Multiple invariants and generalized rank of a p-way matrix or tensor, J. Math. Phys., 7, 1, 39-79 (1927) · JFM 53.0097.01 |
| [34] | Grasedyck, L.; Kressner, D.; Tobler, C., A literature survey of low-rank tensor approximation techniques, GAMM-Mitt., 36, 1, 53-78 (2013) · Zbl 1279.65045 |
| [35] | Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029 |
| [36] | Grasedyck, L.; Wolfgang, H., An introduction to hierarchical h-rank and tt-rank of tensors with examples, Comput. Methods Appl. Math., 11, 3, 291 (2011) · Zbl 1283.15075 |
| [37] | Oseledets, I. V.; Savostianov, D. V.; Tyrtyshnikov, E. E., Tucker dimensionality reduction of three-dimensional arrays in linear time, SIAM J. Matrix Anal. Appl., 30, 3, 939-956 (2008) · Zbl 1180.15025 |
| [38] | Tucker, L. R., Some mathematical notes on three-mode factor analysis, Psychometrika, 31, 279-311 (1966) |
| [39] | Tucker, L., Implications of factor analysis of three-way matrices for measurement of change, Probl. Meas. Change, 122-137 (1963) |
| [40] | Tucker, L. R., The extension of factor analysis to three-dimensional matrices, Contrib. Math. Psychol., 109-127 (1964) |
| [41] | de Lathauwer, L.; de Moor, B.; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 1253-1278 (2000) · Zbl 0962.15005 |
| [42] | Oseledets, I. V.; Tyrtyshnikov, E. E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, 1, 70-88 (2010) · Zbl 1183.65040 |
| [43] | 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 |
| [44] | Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018 |
| [45] | Hackbusch, W.; Kühn, S., A new scheme for the tensor representation, J. Fourier Anal. Appl., 15, 5, 706-722 (2009) · Zbl 1188.15022 |
| [46] | Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31, 4, 2029-2054 (2010) · Zbl 1210.65090 |
| [47] | Hackbusch, W., Tensor Spaces and Numerical Tensor Calculus (2012), Springer-Verlag: Springer-Verlag Berlin · Zbl 1244.65061 |
| [48] | Khoromskij, B. N.; Khoromskaia, V.; Chinnamsetty, S. R.; Flad, H. J., Tensor decomposition in electronic structure calculations on 3D Cartesian grids, J. Comput. Phys., 228, 16, 5749-5762 (2009) · Zbl 1171.82017 |
| [49] | Khoromskij, B. N.; Khoromskaia, V., Multigrid accelerated tensor approximation of function related multidimensional arrays, SIAM J. Sci. Comput., 31, 4, 3002-3026 (2009) · Zbl 1197.65215 |
| [50] | Khoromskaia, V.; Khoromskij, B., Tensor numerical methods in quantum chemistry: from Hartree-Fock to excitation energies, Phys. Chem. Chem. Phys. (2015) |
| [51] | Schneider, R.; Rohwedder, T.; Blauert, J., Direct minimization for calculating invariant subspaces in density functional computations of the electronic structure, J. Comput. Math., 27, 360 (2009) · Zbl 1212.81001 |
| [52] | Flad, Heinz-Jürgen, Best n-term approximation in electronic structure calculations. II. Jastrow factors, ESAIM: M2AN, 41, 2, 261-279 (2007) · Zbl 1135.81029 |
| [53] | Khoromskij, B. N.; Khoromskaia, V.; Flad, H. J., Numerical solution of the Hartree-Fock equation in multilevel tensor-structured format, SIAM J. Sci. Comput., 33, 1, 45-65 (2011) · Zbl 1227.65113 |
| [54] | Kazeev, V. A.; Khoromskij, B. N., Low-rank explicit QTT representation of the Laplace operator and inverse, SIAM J. Matrix Anal. Appl., 33, 3, 742-758 (2012) · Zbl 1268.15025 |
| [55] | Hackbusch, W.; Khoromskij, B. N., Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. I. Separable approximation of multi-variate functions, Computing, 76, 3-4, 177-202 (2006) · Zbl 1087.65049 |
| [56] | Hackbusch, W.; Khoromskij, B. N., Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. II. HKT representation of certain operators, Computing, 76, 3-4, 203-225 (2006) · Zbl 1087.65050 |
| [57] | Beylkin, G.; Mohlenkamp, M. J., Numerical operator calculus in higher dimensions, Proc. Natl. Acad. Sci. USA, 99, 16, 10246-10251 (2002) · Zbl 1008.65026 |
| [58] | Gavrilyuk, I. P.; Hackbusch, W.; Khoromskij, B. N., Tensor-product approximation to the inverse and related operators in high-dimensional elliptic problems, Computing, 74, 131-157 (2005) · Zbl 1071.65032 |
| [59] | Khoromskij, B. N., Tensor-structured preconditioners and approximate inverse of elliptic operators in \(R^d\), Constr. Approx., 30, 599-620 (2009) · Zbl 1185.65051 |
| [60] | Khoromskij, B. N.; Khoromskaia, V., Low rank Tucker-type tensor approximation to classical potentials, Cent. Eur. J. Math., 5, 3, 523-550 (2007) · Zbl 1130.65060 |
| [61] | Hackbusch, W.; Khoromskij, B. N., Tensor-product approximation to operators and functions in high dimensions, J. Complex., 23, 4-6, 697-714 (2007), festschrift for the 60th Birthday of Henryk Woźniakowski · Zbl 1141.65032 |
| [62] | Hackbusch, W.; Braess, D., Approximation of \(\frac{1}{x}\) by exponential sums in \([1, \infty]\), IMA J. Numer. Anal., 25, 4, 685-697 (2005) · Zbl 1082.65025 |
| [63] | Oseledets, I. V.; Muravleva, E. A., Fast orthogonalization to the kernel of discrete gradient operator with application to the Stokes problem, Linear Algebra Appl., 432, 6, 1492-1500 (2010) · Zbl 1183.65131 |
| [64] | Oseledets, I. V., Constructive representation of functions in low-rank tensor formats, Constr. Approx., 37, 1, 1-18 (2013) · Zbl 1282.15021 |
| [65] | Beylkin, G.; Mohlenkamp, M. J., Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput., 26, 6, 2133-2159 (2005) · Zbl 1085.65045 |
| [66] | Dolgov, S. V.; Khoromskij, B. N.; Oseledets, I. V., Fast solution of multi-dimensional parabolic problems in the tensor train/quantized tensor train-format with initial application to the Fokker-Planck equation, SIAM J. Sci. Comput., 34, 6, A3016-A3038 (2012) · Zbl 1259.82075 |
| [67] | Khoromskij, B. N.; Oseledets, I. V., Quantics-TT collocation approximation of parameter-dependent and stochastic elliptic PDEs, Comput. Methods Appl. Math., 10, 4, 376-394 (2010) · Zbl 1283.65039 |
| [68] | Khoromskij, B. N.; Oseledets, I. V., DMRG+QTT approach to computation of the ground state for the molecular Schrödinger operator (2010), MPI MIS: MPI MIS Leipzig, Preprint 69 |
| [69] | 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 |
| [70] | Lebedeva, O. S., Tensor conjugate-gradient-type method for Rayleigh quotient minimization in block QTT-format, Russ. J. Numer. Anal. Math. Model., 26, 5, 465-489 (2011) · Zbl 1252.65076 |
| [71] | Khoromskij, B. N.; Oseledets, I. V., QTT-approximation of elliptic solution operators in high dimensions, Russ. J. Numer. Anal. Math. Model., 26, 3, 303-322 (2011) · Zbl 1221.65288 |
| [72] | Savostyanov, D. V., QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images (2011), MPI MIS: MPI MIS Leipzig, Preprint 45 · Zbl 1244.65253 |
| [73] | 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 |
| [74] | Khoromskaia, V.; Khoromskij, B. N.; Schneider, R., Tensor-structured factorized calculation of two-electron integrals in a general basis, SIAM J. Sci. Comput., 35, 2, A987-A1010 (2013) · Zbl 1266.65069 |
| [75] | Ballani, J., Fast evaluation of singular BEM integrals based on tensor approximations, Numer. Math., 121, 3, 433-460 (2012) · Zbl 1261.65026 |
| [76] | Rakhuba, M. V.; Oseledets, I. V., Fast multidimensional convolution in low-rank tensor formats via cross approximation, SIAM J. Sci. Comput., 37, 2, A565-A582 (2015) · Zbl 1320.65197 |
| [77] | Khoromskij, B. N., Fast and accurate tensor approximation of multivariate convolution with linear scaling in dimension, J. Comput. Appl. Math., 234, 11, 3122-3139 (2010) · Zbl 1197.65216 |
| [78] | Kazeev, V.; Khoromskij, B. N.; Tyrtyshnikov, E. E., Multilevel Toeplitz matrices generated by tensor-structured vectors and convolution with logarithmic complexity (2011), MPI MIS: MPI MIS Leipzig, Tech. Rep. 36 · Zbl 1275.15018 |
| [79] | Dolgov, S. V.; Khoromskij, B. N.; Savostyanov, D. V., Superfast Fourier transform using QTT approximation, J. Fourier Anal. Appl., 18, 5, 915-953 (2012) · Zbl 1260.65114 |
| [80] | Beylkin, G.; Monzón, L., Approximation by exponential sums revisited, Appl. Comput. Harmon. Anal., 28, 2, 131-149 (2010) · Zbl 1189.65035 |
| [81] | Brigham, E. O., The Fast Fourier Transform and Its Applications (1988), Prentice Hall |
| [82] | Nussbaumer, H. J., Fast Fourier Transform and Convolution Algorithms (1981), Springer · Zbl 0476.65097 |
| [83] | Chiu, J.; Demanet, L., Sublinear randomized algorithms for skeleton decompositions, SIAM J. Matrix Anal. Appl., 34, 3, 1361-1383 (2013) · Zbl 1277.68296 |
| [84] | Bebendorf, M.; Grzhibovskis, R., Accelerating Galerkin BEM for linear elasticity using adaptive cross approximation, Math. Methods Appl. Sci., 29, 14, 1721-1747 (2006) · Zbl 1110.74054 |
| [85] | Bebendorf, M.; Kunis, S., Recompression techniques for adaptive cross approximation, J. Integral Equ. Appl., 21, 3, 331-357 (2009) · Zbl 1180.65162 |
| [86] | Bebendorf, M., Adaptive cross approximation of multivariate functions, Constr. Approx., 34, 2, 149-179 (2011) · Zbl 1248.41049 |
| [87] | Hairer, E.; Lubich, C.; Wanner, G., Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations, Springer Ser. Comput. Math. (2006), Springer · Zbl 1094.65125 |
| [88] | Brezinski, C.; Zaglia, M. R., Extrapolation Methods. Theory and Practice (1991), Elsevier · Zbl 0744.65004 |
| [89] | Stoer, J.; Bulirsch, R., Introduction to Numerical Analysis (2002), Springer · Zbl 1004.65001 |
| [90] | Makri, N., Numerical path integral techniques for long time dynamics of quantum dissipative systems, J. Math. Phys., 36, 5, 2430-2457 (1995) · Zbl 0846.65082 |
| [91] | Makri, N., Blip decomposition of the path integral: exponential acceleration of real-time calculations on quantum dissipative systems, J. Chem. Phys., 141, 13, Article 134117 pp. (2014) |
| [92] | Dubach, E., Artificial boundary conditions for diffusion equations: numerical study, J. Comput. Appl. Math., 70, 1, 127-144 (1996) · Zbl 0873.65096 |
| [93] | Wu, X.; Sun, Z. Z., Convergence of difference scheme for heat equation in unbounded domains using artificial boundary conditions, Appl. Numer. Math., 50, 2, 261-277 (2004) · Zbl 1053.65074 |
| [94] | Tyrtyshnikov, E. E., Mosaic-skeleton approximations, Calcolo, 33, 1, 47-57 (1996) · Zbl 0906.65048 |
| [95] | Goreinov, S. A.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., A theory of pseudo-skeleton approximations, Linear Algebra Appl., 261, 1-21 (1997) · Zbl 0877.65021 |
| [96] | Goreinov, S. A.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., Pseudo-skeleton approximations of matrices, Rep. Russ. Acad. Sci., 342, 2, 151-152 (1995) · Zbl 0875.15004 |
| [97] | Goreinov, S. A.; Zamarashkin, N. L.; Tyrtyshnikov, E. E., Pseudo-skeleton approximations by matrices of maximum volume, Math. Notes, 62, 4, 515-519 (1997) · Zbl 0916.65040 |
| [100] | Tyrtyshnikov, E. E., Incomplete cross approximation in the mosaic-skeleton method, Computing, 64, 4, 367-380 (2000) · Zbl 0964.65048 |
| [101] | Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86, 4, 565-589 (2000) · Zbl 0966.65094 |
| [102] | Goreinov, S. A.; Tyrtyshnikov, E. E., The maximal-volume concept in approximation by low-rank matrices, Contemp. Math., 280, 47-51 (2001) · Zbl 1003.15025 |
| [103] | Goreinov, S. A.; Oseledets, I. V.; Savostyanov, D. V.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., How to find a good submatrix (2008), ICM HKBU: ICM HKBU Kowloon Tong, Hong Kong, Research Report 08-10 · Zbl 1215.65078 |
| [104] | Litsarev, M. S.; Oseledets, I. V., Cross2d C++ code: included in the DEPOSIT distribution (2014) |
| [105] | Litsarev, M. S.; Oseledets, I. V., The DEPOSIT computer code based on the low rank approximations, Comput. Phys. Commun., 185, 10, 2801-2802 (2014) · Zbl 1360.65011 |
| [106] | Litsarev, M. S.; Oseledets, I. V., Fast low-rank approximations of multidimensional integrals in ion-atomic collisions modelling, Numer. Linear Algebra Appl. (2015) · Zbl 1399.65101 |
| [107] | Litsarev, M. S., Cross2d C++ code for the real and complex matrices (2015), template version |
| [108] | Gavrilyuk, I. P.; Khoromskij, B. N., Quantized-TT-Cayley transform to compute dynamics and spectrum of high-dimensional Hamiltonians, Comput. Methods Appl. Math., 11, 3, 273-290 (2011) · Zbl 1283.65036 |
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.
