Quantics-TT Collocation Approximation of Parameter-Dependent and Stochastic Elliptic PDEs

By Boris N. Khoromskij, Ivan V. Oseledets. 2010

86 citations recorded by the source corpus.

Abstract We investigate the convergence rate of the quantics-TT (QTT) stochas- tic collocation tensor approximations to solutions of multiparametric elliptic PDEs and construct efficient iterative methods for solving arising high-dimensional parameter- dependent algebraic systems of equations. Such PDEs arise, for example, in the para- metric, deterministic reformulation of elliptic PDEs with random field inputs, based, for example, on the M-term truncated Karhunen-Loève expansion. We consider both the case of additive and log-additive dependence on the multivariate parameter. The local-global versions of the QTT-rank estimates for the system matrix in terms of the parameter space dimension is proven. Similar rank bounds are observed in numerics for the solutions of the discrete linear system. We propose QTT-truncated iteration based on the construction of solution-adaptive preconditioner that provides robust conver- gence in both additive and log-additive cases. Various numerical tests indicate that the numerical complexity scales almost linearly in the dimension of parametric space M.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “…e.g., based on Hartree-Fock or DFT models [23,24,31,44,45,47,87,141–146,150,156–159]; • the solution of stochastic and parametric PDEs [68,69,76,77,161,165,171,189,202]; • approximation of Green’s functions of high-dimensional PDEs [30,113]; • the solution of the Boltzmann equation [129, 149],…”
Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse (2012, methodology): “Note that the straightforward discretizations of the Laplace operator we consider turn out to be very efficient in tensor-structured solvers based on the TT, QTT, and hierarchical tensor [15, 13] formats and yield convincing experimental results when constructed on fine meshes; see the papers [24, 8”
DMRG+QTT approach to computation of the ground state for the molecular Schrödinger operator (2010, methodology): “It is worth to note, that the QTT-format was already successfully applied to solving highdimensional elliptic equations [28], multiparametric SPDEs [27], and in electronic structure calculation [18] and the log-volume complexity was conrmed numerically and theoretically [9], so it is a natural idea ”
Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats (2014, background): “In [18, 17] based on [3, 31] this leads to several data-sparse representations of the objects encountered in discretisation of the model problem as well as the obtained solution.”
Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions (2013, unknown): “, algorithms for the solution of linear systems [51, 21, 47, 38, 34, 31, 39, 2, 8, 4, 3], partial eigenproblems [41, 40, 24, 20], and Fourier transform [11].”
Geometric Methods on Low-Rank Matrix and Tensor Manifolds (2020, methodology): “Similar approaches appear for weakly compressible fluid flow with the Boltzmann equation in [27] and stochastic transport PDEs in [32].”
Multilevel preconditioning and low‐rank tensor iteration for space–time simultaneous discretizations of parabolic PDEs (2015, methodology): “Methods for the solution of linear systems in the hierarchical Tucker format, as well as in the special case of the Tensor Train format [29], have been the subject of recent work [3, 12, 21, 23, 24, 26].”
Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, methodology): “To use all the benefits from tensor decompositions for low-dimensional data, we use the QTT format [26] [27] [28] [29] [44] [30] [45] [40].”
DMRG Approach to Fast Linear Algebra in the TT-Format (2011, background): “There are typical cases where TT-ranks are of the order of hundreds, for example in the solution of stochastic PDEs [16] and in the solution of high-dimensional eigenvalue problems [17].”
QTT approximation of elliptic solution operators in higher dimensions (2011, methodology): “For example, for stochastic PDEs, right-hand side has rank-1 structure [25]:”
Low-rank tensor methods for linear systems and eigenvalue problems (2012, methodology): “Examples for this strategy can be found in [7, 31, 39, 41, 48].”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives (2017, methodology): “…CP format [Beylkin and Mohlenkamp, 2005, Khoromskij and Schwab, 2011], CP and Tucker formats [Billaud-Friess et al., 2014], TT format [Dolgov, 2013, Khoromskij and Oseledets, 2010], HT format [Bachmayr and Dahmen, 2015, Bachmayr and Schneider, 2016, Kressner and Tobler, 2011a], and a subspace…”
ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS∗ (2014, methodology): “, algorithms for the solution of linear systems [51, 21, 47, 38, 34, 31, 39, 2, 8, 4, 3], partial eigenproblems [41, 40, 24, 20], and Fourier transform [11].”
Tensors-structured Numerical Methods in Scientific Computing: Survey on Recent Advances (2012, methodology): “Section 4 presents various numerical examples on the QTT approximation of N -d tensors applied to the elliptic/parabolic equations and to stochastic/multiparametric PDEs.”
Algorithm 941 (2014, background): “Examples for this strategy can be found in [4, 14, 20, 21, 25].”