Preconditioned Low-Rank Methods for High-Dimensional Elliptic PDE Eigenvalue Problems

By Daniel Kressner, Christine Tobler. 2011

75 citations recorded by the source corpus.

Abstract We consider elliptic PDE eigenvalue problems on a tensorized domain, discretized such that the resulting matrix eigenvalue problem Ax=λx exhibits Kronecker product structure. In particular, we are concerned with the case of high dimensions, where standard approaches to the solution of matrix eigenvalue problems fail due to the exponentially growing degrees of freedom. Recent work shows that this curse of dimensionality can in many cases be addressed by approximating the desired solution vector x in a low-rank tensor format. In this paper, we use the hierarchical Tucker decomposition to develop a low-rank variant of LOBPCG, a classical preconditioned eigenvalue solver. We also show how the ALS and MALS (DMRG) methods known from computational quantum physics can be adapted to the hierarchical Tucker decomposition. Finally, a combination of ALS and MALS with LOBPCG and with our low-rank variant is proposed. A number of numerical experiments indicate that such combinations represent the methods of choice.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Statistical and Nonlinear Physics

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 Statistical and Nonlinear Physics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “…and the chemical master / Fokker-Planck equations [4,6,61,64,86,122,133,135,196] • the solution of high-dimensional Schr¨odinger equations [46,160,172,184,192,193]; • computational tasks in micromagnetics [80,81]; • rational approximation problems [242]; • computational homogenization…”
Dynamical Approximation by Hierarchical Tucker and Tensor-Train Tensors (2013, result): “Aside from some necessary concepts from [7, 9], we also introduce notation similar to that of [19, 18, 30] that is better suited to our analysis.”
The geometry of algorithms using hierarchical tensors (2013, methodology): “For the TT format this idea has been realized in [31], and for the HT format in [47].”
Computing Inner Eigenvalues of Matrices in Tensor Train Matrix Format (2013, methodology): “In [9] Christine Tobler and Daniel Kressner investigated the usage of LOBPCG for the solution of eigenvalues problems with matrices in H -Tucker format.”
Low-rank tensor methods for linear systems and eigenvalue problems (2012, background): “The contents of this chapter are based on [49].”
On Local Convergence of Alternating Schemes for Optimization of Convex Problems in the Tensor Train Format (2013, background): “[1, 2, 22, 26, 29]; while the former approach seems to be superior on some problems in the sense that it sometimes provides lower ranks [16], the latter has advantage of being conceptually quite simple, thus often allowing for a simpler analysis from the theoretical point of view, and enabling, from”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives (2017, methodology): “…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 projection method combined with HT format [Ballani and Grasedyck, 2013]; • A subspace projection method…”
Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, unknown): “Recently, the HT variant was developed [46], and here the QTTTucker one, all of them give satisfactory results for considered problems.”
LOCAL CONVERGENCE OF ALTERNATING SCHEMES FOR OPTIMIZATION OF CONVEX PROBLEMS IN THE TT FORMAT (2011, background): “[1, 2, 20, 24, 27]; while the former approach seems to be superior on some problems in the sense that it sometimes provides lower ranks [15], the latter has advantage of being conceptually quite simple, thus often allowing for a simpler analysis from the theoretical point of view, and enabling, from”
Adaptive low rank wavelet methods and applications to two-electron Schrödinger equations (2012, background): “, in [101, 5, 96, 140], and for eigenvalue problems in [92, 6, 74, 102, 95, 140].”
Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions (2013, unknown): “For ALS there is also a lack of convergence estimates both in the classical papers [16, 4], and in the recent ones, where ALS was applied to the Tucker model [5, 33], tensor trains [29], hierarchical Tucker format [25] and high–dimensional interpolation [34].”
An Error Analysis of Galerkin Projection Methods for Linear Systems with Tensor Product Structure (2013, methodology): “5) can be used as preconditioners in iterative methods for more general linear systems [19, 4] and eigenvalue problems [22].”