×

Parallel tensor methods for high-dimensional linear PDEs. (English) Zbl 1416.65387

Summary: High-dimensional partial-differential equations (PDEs) arise in a number of fields of science and engineering, where they are used to describe the evolution of joint probability functions. Their examples include the Boltzmann and Fokker-Planck equations. We develop new parallel algorithms to solve such high-dimensional PDEs. The algorithms are based on canonical and hierarchical numerical tensor methods combined with alternating least squares and hierarchical singular value decomposition. Both implicit and explicit integration schemes are presented and discussed. We demonstrate the accuracy and efficiency of the proposed new algorithms in computing the numerical solution to both an advection equation in six variables plus time and a linearized version of the Boltzmann equation.

MSC:

65M75 Probabilistic methods, particle methods, etc. for initial value and initial-boundary value problems involving PDEs
65H10 Numerical computation of solutions to systems of equations
65C20 Probabilistic models, generic numerical methods in probability and statistics

Software:

htucker; LSQR; CRAIG
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cercignani, C., The Boltzmann Equation and Its Applications (1988), Springer: Springer New York · Zbl 0646.76001
[2] (Moss, F.; McClintock, P. V.E., Noise in Nonlinear Dynamical Systems (1989), Cambridge University Press)
[3] Venturi, D.; Sapsis, T. P.; Cho, H.; Karniadakis, G. E., A computable evolution equation for the joint response-excitation probability density function of stochastic dynamical systems, Proc. R. Soc. A, 468, 2139, 759-783 (2011) · Zbl 1365.92023
[4] Shlesinger, M. F.; Swean, T., Stochastically Excited Nonlinear Ocean Structures (1998), World Scientific · Zbl 0920.92036
[5] Monin, A. S.; Yaglom, A. M., Statistical Fluid Mechanics, Volume II: Mechanics of Turbulence (2007), Dover · Zbl 1140.76004
[6] Frisch, U., Turbulence: The Legacy of A.N. Kolmogorov (1995), Cambridge University Press
[7] Venturi, D., The numerical approximation of nonlinear functionals and functional differential equations, Phys. Rep., 732, 1-102 (2018) · Zbl 1473.65064
[8] Cowen, L.; Ideker, T.; Raphael, B. J.; Sharan, R., Network propagation: a universal amplifier of genetic associations, Nat. Rev. Genet., 18, 9, 551-562 (2017)
[9] Zinn-Justin, J., Quantum Field Theory and Critical Phenomena (2002), Oxford University Press
[10] Amit, D. J.; Martin-Mayor, V., Field Theory, the Renormalization Group, and Critical Phenomena (2005), World Scientific
[11] Risken, H., The Fokker-Planck Equation (1989), Springer Berlin Heidelberg · Zbl 0665.60084
[12] Tartakovsky, D. M.; Gremaud, P. A., Method of distributions for uncertainty quantification, (Ghanem, R.; Higdon, D.; Owhadi, H., Handbook of Uncertainty Quantification (2017), Springer International Publishing: Springer International Publishing Switzerland), 763-783
[13] Pope, S. B., Lagrangian PDF methods for turbulent flows, Annu. Rev. Fluid Mech., 26, 1, 23-63 (1994) · Zbl 0802.76033
[14] Dimarco, G.; Pareschi, L., Numerical methods for kinetic equations, Acta Numer., 23, 369-520 (2014) · Zbl 1398.65260
[15] Rjasanow, S.; Wagner, W., Stochastic Numerics for the Boltzmann Equation (2004), Springer
[16] Babovsky, H.; Neunzert, H., On a simulation scheme for the Boltzmann equation, Math. Methods Appl. Sci., 8, 1, 223-233 (1986) · Zbl 0609.76084
[17] Ansumali, S., Mean-field model beyond Boltzmann-Enskog picture for dense gases, Commun. Comput. Phys., 9, 05, 1106-1116 (2011) · Zbl 1364.82048
[18] Ramanathan, S.; Koch, D. L., An efficient direct simulation Monte Carlo method for low Mach number noncontinuum gas flows based on the Bhatnagar-Bross-Krook model, Phys. Fluids, 21, 3, Article 033103 pp. (2009) · Zbl 1183.76426
[19] Peraud, J.-P. M.; Landon, C. D.; Hadjiconstantinou, N. G., Monte Carlo methods for solving the Boltzmann transport equation, Annu. Rev. Heat Transf., 17, 205-265 (2014)
[20] Rogier, F.; Schneider, J., A direct method for solving the Boltzmann equation, Transp. Theory Stat. Phys., 23, 1-3, 313-338 (1994) · Zbl 0811.76050
[21] Cho, H.; Venturi, D.; Karniadakis, G., Numerical methods for high-dimensional probability density function equations, J. Comput. Phys., 305, 817-837 (2016) · Zbl 1349.65046
[22] Zhang, Z.; Karniadakis, G. E., Numerical Methods for Stochastic Partial Differential Equations with White Noise (2017), Springer International Publishing · Zbl 1380.65021
[23] E, W.; Han, J.; Jentzen, A., Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations, Commun. Math. Stat., 5, 4, 349-380 (2017) · Zbl 1382.65016
[24] Bachmayr, M.; Schneider, R.; Uschmajew, A., Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations, Found. Comput. Math., 16, 6, 1423-1472 (2016) · Zbl 1357.65153
[25] Hesthaven, J. S.; Gottlieb, S.; Gottlieb, D., Spectral Methods for Time-Dependent Problems, vol. 21 (2007), Cambridge University Press · Zbl 1111.65093
[26] 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
[27] Acar, E.; Dunlavy, D. M.; Kolda, T. G., A scalable optimization approach for fitting canonical tensor decompositions, J. Chemom., 25, 2, 67-86 (2011)
[28] Espig, M.; Hackbusch, W., A regularized Newton method for the efficient approximation of tensors represented in the canonical tensor format, Numer. Math., 122, 3, 489-525 (2012) · Zbl 1264.65087
[29] Karlsson, L.; Kressner, D.; Uschmajew, A., Parallel algorithms for tensor completion in the CP format, Parallel Comput., 57, 222-234 (2016)
[30] Doostan, A.; Validi, A.; Iaccarino, G., Non-intrusive low-rank separated approximation of high-dimensional stochastic models, Comput. Methods Appl. Mech. Eng., 263, 42-55 (2013) · Zbl 1286.65014
[31] Reynolds, M. J.; Doostan, A.; Beylkin, G., Randomized alternating least squares for canonical tensor decompositions: application to a PDE with random data, SIAM J. Sci. Comput., 38, 5, A2634-A2664 (2016) · Zbl 1348.65012
[32] Battaglino, C.; Ballard, G.; Kolda, T. G., A practical randomized CP tensor decomposition (2017) · Zbl 1444.65016
[33] Uschmajew, A., Local convergence of the alternating least squares algorithm for canonical tensor approximation, SIAM J. Matrix Anal. Appl., 33, 2, 639-652 (2012) · Zbl 1252.65085
[34] Espig, M.; Hackbusch, W.; Khachatryan, A., On the convergence of alternating least squares optimisation in tensor format representations (2015)
[35] Bezdek, J. C.; Hathaway, R. J., Convergence of alternating optimization, Neural Parallel Sci. Comput., 11, 351-368 (2003) · Zbl 1063.90051
[36] Rohwedder, T.; Uschmajew, A., On local convergence of alternating schemes for optimization of convex problems in the tensor train format, SIAM J. Numer. Anal., 51, 2, 1134-1162 (2013) · Zbl 1273.65088
[37] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (2000), Society for Industrial and Applied Mathematics · Zbl 0949.65053
[38] Kaya, O.; Ucar, B., Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees, SIAM J. Sci. Comput., 40, 1, C99-C130 (2018) · Zbl 1383.65037
[39] Hackbusch, W.; Kühn, S., A new scheme for the tensor representation, J. Fourier Anal. Appl., 15, 5, 706-722 (2009) · Zbl 1188.15022
[40] Hackbusch, W., Tensor Spaces and Numerical Tensor Calculus (2012), Springer Berlin Heidelberg · Zbl 1244.65061
[42] Grasedyck, L., Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl., 31, 4, 2029-2054 (2010) · Zbl 1210.65090
[43] De Lathauwer, L.; De Moor, B.; Vandewalle, J., A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21, 4, 1253-1278 (2000) · Zbl 0962.15005
[44] Venturi, D., A fully symmetric nonlinear biorthogonal decomposition theory for random fields, Physica D, 240, 4-5, 415-425 (2011) · Zbl 1209.60031
[45] Peres, A., Higher order Schmidt decompositions, Phys. Lett. A, 202, 1, 16-17 (1995) · Zbl 1020.81540
[46] 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
[47] Hillar, C. J.; Lim, L.-H., Most tensor problems are NP-hard, J. ACM, 60, 6, 1-39 (2013) · Zbl 1281.68126
[48] Vannieuwenhoven, N.; Nicaise, J.; Vandebril, R.; Meerbergen, K., On generic nonexistence of the Schmidt-Eckart-Young decomposition for complex tensors, SIAM J. Matrix Anal. Appl., 35, 3, 886-903 (2014) · Zbl 1311.15027
[49] Kressner, D.; Tobler, C., Algorithm 941, ACM Trans. Math. Softw., 40, 3, 1-22 (2014) · Zbl 1322.65054
[50] Da Silva, C.; Herrmann, F. J., Optimization on the hierarchical Tucker manifold - applications to tensor completion, Linear Algebra Appl., 481, 131-173 (2015) · Zbl 1317.65136
[51] Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018
[52] Grasedyck, L.; Kriemann, R.; Löbbert, C.; Nägel, A.; Wittum, G.; Xylouris, K., Parallel tensor sampling in the hierarchical Tucker format, Comput. Vis. Sci., 17, 2, 67-78 (2015) · Zbl 1360.65042
[53] Nouy, A., Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats (2017)
[54] Etter, S., Parallel ALS algorithm for solving linear systems in the hierarchical Tucker representation, SIAM J. Sci. Comput., 38, 4, A2585-A2609 (2016) · Zbl 1347.65072
[55] Grasedyck, L.; Löbbert, C., Distributed Hierarchical SVD in the Hierarchical Tucker format (2017) · Zbl 1513.65097
[57] Zhou, G.; Cichocki, A.; Xie, S., Accelerated canonical polyadic decomposition using mode reduction, IEEE Trans. Neural Netw. Learn. Syst., 24, 12, 2051-2062 (2013)
[58] Hatch, D.; del Castillo-Negrete, D.; Terry, P., Analysis and compression of six-dimensional gyrokinetic datasets using higher order singular value decomposition, J. Comput. Phys., 231, 11, 4234-4256 (2012) · Zbl 1426.76647
[59] Kormann, K., A semi-Lagrangian Vlasov solver in tensor train format, SIAM J. Sci. Comput., 37, 4, B613-B632 (2015) · Zbl 1325.76132
[60] Dolgov, S.; Smirnov, A.; Tyrtyshnikov, E., Low-rank approximation in the numerical modeling of the Farley-Buneman instability in ionospheric plasma, J. Comput. Phys., 263, 268-282 (2014) · Zbl 1349.76453
[61] Quarteroni, A.; Sacco, R.; Saleri, F., Numerical Mathematics (2007), Springer: Springer New York · Zbl 0913.65002
[62] Rhee, H.-K.; Aris, R.; Amundson, N. R., First-Order Partial Differential Equations, Volume 1: Theory and Applications of Single Equations (2001), Dover
[63] Dimarco, G.; Loubère, R.; Narski, J.; Rey, T., An efficient numerical method for solving the Boltzmann equation in multidimensions, J. Comput. Phys., 353, 46-81 (2018) · Zbl 1380.76088
[64] Desvillettes, L.; Mischler, S., About the splitting algorithm for Boltzmann and B.G.K. equations, Math. Models Methods Appl. Sci., 06, 08, 1079-1101 (1996) · Zbl 0876.35088
[65] Shuleshko, P., A new method of solving boundary-value problems of mathematical physics, Aust. J. Appl. Sci., 10, 1-7 (1959)
[66] Snyder, L. J.; Spriggs, T. W.; Stewart, W. E., Solution of the equations of change by Galerkin’s method, AIChE J., 10, 4, 535-540 (1964)
[67] Zinn, B.; Powell, E., Application of the Galerkin method in the solution of combustion-instability problems, (XlXth International Astronautical Congress, vol. 3 (1968)), 59-73
[68] Comon, P.; Luciani, X.; de Almeida, A. L.F., Tensor decompositions, alternating least squares and other tales, J. Chemom., 23, 7-8, 393-405 (2009)
[69] Cercignani, C.; Gerasimenko, V. I.; Petrina, D. Y., Many-Particle Dynamics and Kinetic Equations (1997), Springer: Springer Netherlands · Zbl 0933.82001
[70] Villani, C., A review of mathematical topics in collisional kinetic theory, (Friedlander, S.; Serre, D., Handbook of Mathematical Fluid Mechanics, vol. 1 (2002), North-Holland), 71-305 · Zbl 1170.82369
[71] Cercignani, C.; Illner, R.; Pulvirenti, M., The Mathematical Theory of Dilute Gases (1994), Springer: Springer New York · Zbl 0813.76001
[72] Nishida, T., Fluid dynamical limit of the nonlinear Boltzmann equation to the level of the compressible Euler equation, Commun. Math. Phys., 61, 2, 119-148 (1978) · Zbl 0381.76060
[73] Caflisch, R. E., The fluid dynamic limit of the nonlinear Boltzmann equation, Commun. Pure Appl. Math., 33, 5, 651-666 (1980) · Zbl 0424.76060
[74] Struchtrup, H., Macroscopic Transport Equations for Rarefied Gas Flows (2005), Springer Berlin Heidelberg · Zbl 1119.76002
[75] Levermore, C. D., Moment closure hierarchies for kinetic theories, J. Stat. Phys., 83, 5-6, 1021-1065 (1996) · Zbl 1081.82619
[76] Müller, I.; Ruggeri, T., Rational Extended Thermodynamics (1998), Springer: Springer New York · Zbl 0895.00005
[77] Bhatnagar, P. L.; Gross, E. P.; Krook, M., A model for collision processes in gases. I. Small amplitude processes in charged and neutral one-component systems, Phys. Rev., 94, 3, 511-525 (1954) · Zbl 0055.23609
[78] Mieussens, L., Discrete-velocity models and numerical schemes for the Boltzmann-BGK equation in plane and axisymmetric geometries, J. Comput. Phys., 162, 2, 429-466 (2000) · Zbl 0984.76070
[79] Nassios, J.; Sader, J. E., High frequency oscillatory flows in a slightly rarefied gas according to the Boltzmann-BGK equation, J. Fluid Mech., 729, 1-46 (2013) · Zbl 1291.76278
[80] Andries, P.; Le Tallec, P.; Perlat, J.-P.; Perthame, B., The Gaussian-BGK model of Boltzmann equation with small Prandtl number, Eur. J. Mech. B, Fluids, 19, 6, 813-830 (2000) · Zbl 0967.76082
[81] Borghini, N., Topics in Nonequilibrium Physics (Sep. 2016)
[82] Barichello, L.; Siewert, C., Some comments on modeling the linearized Boltzmann equation, J. Quant. Spectrosc. Radiat. Transf., 77, 1, 43-59 (2003)
[83] Pekeris, C. L.; Alterman, Z., Solution of the Boltzmann-Hilbert integral equation. II. The coefficients of viscosity and heat conduction, Proc. Natl. Acad. Sci., 43, 11, 998-1007 (1957) · Zbl 0080.09102
[84] Loyalka, S. K., Model dependence of the slip coefficient, Phys. Fluids, 10, 8, 1833 (1967) · Zbl 0204.27901
[85] Huang, H.; Dennis, J. M.; Wang, L.; Chen, P., A scalable parallel LSQR algorithm for solving large-scale linear system for tomographic problems: a case study in seismic tomography, Proc. Comput. Sci., 18, 581-590 (2013)
[86] Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8, 1, 43-71 (1982) · Zbl 0478.65016
[87] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), Society for Industrial and Applied Mathematics
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.