HT-AWGM: A Hierarchical Tucker-Adaptive Wavelet Galerkin Method for High Dimensional Elliptic Problems
For researchers in numerical PDEs and high-dimensional approximation, this work provides a novel adaptive method that combines wavelet and tensor techniques, but the results are incremental as they build on existing methods and the complexity analysis involves powers of four.
This paper develops a Hierarchical Tucker-Adaptive Wavelet Galerkin Method (HT-AWGM) for solving high-dimensional elliptic PDEs, achieving convergence rates dependent only on the desired tolerance and the Besov regularity of low-dimensional factors, with algebraic complexity in tensor ranks. Numerical experiments demonstrate quantitative performance.
This paper is concerned with the construction, analysis and realization of a numerical method to approximate the solution of high dimensional elliptic partial differential equations. We propose a new combination of an Adaptive Wavelet Galerkin Method (AWGM) and the well known Hierarchical Tensor (HT) format. The arising HT-AWGM is adaptive both in the wavelet representation of the low dimensional factors and in the tensor rank of the HT representation. The point of departure is an adaptive wavelet method for the HT format using approximate Richardson iterations from [1] and an AWGM method as described in [13]. HT-AWGM performs a sequence of Galerkin solves based upon a truncated preconditioned conjugate gradient (PCG) algorithm from [33] in combination with a tensor-based preconditioner from [3]. Our analysis starts by showing convergence of the truncated conjugate gradient method. The next step is to add routines realizing the adaptive refinement. The resulting HT-AWGM is analyzed concerning convergence and complexity. We show that the performance of the scheme asymptotically depends only on the desired tolerance with convergence rates depending on the Besov regularity of low dimensional quantities and the low rank tensor structure of the solution. The complexity in the ranks is algebraic with powers of four stemming from the complexity of the tensor truncation. Numerical experiments show the quantitative performance.