Abstract
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 and an AWGM for elliptic problems. HT-AWGM performs a sequence of Galerkin solves based upon a truncated preconditioned conjugate gradient (PCG) algorithm in combination with a tensor-based preconditioner. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bachmayr, M., Dahmen, W.: Adaptive near-optimal rank tensor approximation for high-dimensional operator equations. Found Comput. Math. 15(4), 839–898 (2015)
Bachmayr, M., Dahmen, W.: Adaptive low-rank methods for problems on Sobolev spaces with error control in L2. ESAIM Math. Model. Numer Anal. 50(4), 1107–1136 (2016)
Bachmayr, M., Dahmen, W.: Adaptive low-rank methods: problems on Sobolev spaces. SIAM J. Numer. Anal. 54(2), 744–796 (2016)
Bachmayr, M., Schneider, R.: Iterative methods based on soft thresholding of hierarchical tensors. Found Comput. Math. 17(4), 1037–1083 (2017)
Bachmayr, M., Schneider, R., Uschmajew, A.: Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations. Found. Comput. Math., pp 1–50 (2016)
Ballani, J., Grasedyck, L.: A projection method to solve linear systems in tensor format. Numer Linear Algebra Appl. 20(1), 27–43 (2013)
Billaud-Friess, M., Nouy, A., Zahm, O.: A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems. ESAIM: Mathematical Modelling and Numerical Analysis 48 (6), 1777–1806 (2014)
Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods for elliptic operator equations: convergence rates. Math. Comp. 70(233), 27–75 (2001)
Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods. II. Beyond the elliptic case. Found. Comput. Math. 2(3), 203–245 (2002)
Dahmen, W., DeVore, R., Grasedyck, L., Süli, E.: Tensor-sparsity of solutions to high-dimensional elliptic partial differential equations. Found Comput. Math. 16(4), 813–874 (2016)
D’Aspremont, A.: Smooth optimization with approximate gradient. SIAM Journal on Optimization 19, 1171–1183 (2008)
Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming 146(1-2), 37–75 (2013)
DeVore, R.A.: Nonlinear approximation. In: Acta Numerica. Cambridge Univ. Press, Cambridge, 1998, vol. 7, pp 51–150 (1998)
Dolgov, S., Khoromskij, B.: Simultaneous state-time approximation of the chemical master equation using tensor product formats. Numer. Linear Algebra Appl. 22(2), 197–219 (2015)
Dolgov, S.V., Savostyanov, D.V.: Alternating minimal energy methods for linear systems in higher dimensions. SIAM Journal on Scientific Computing 36(5), A2248–A2271 (2014)
Fischer, B.: Polynomial Based Iteration Methods for Symmetric Linear Systems. Wiley-Teubner Series Advances in Numerical Mathematics. Wiley, Chichester (1996). B.G. Teubner, Stuttgart
Gantumur, T., Harbrecht, H., Stevenson, R. : An optimal adaptive wavelet method without coarsening of the iterands. Math Comp. 76 (258), 615–629 (2007)
Hackbusch, W.: Iterative Lösung Groß Er Schwachbesetzter Gleichungssysteme, vol. 69. B. G. Teubner, Stuttgart (1991)
Hackbusch, W., calculus, numerical tensor: Tensor Spaces Vol. 42 of Springer Series in Computational Mathematics. Springer, Heidelberg (2012)
Hackbusch, W., Kühn, S.: A new scheme for the tensor representation. J Fourier Anal. Appl. 15(5), 706–722 (2009)
Holtz, S., Rohwedder, T., Schneider, R.: The alternating linear scheme for tensor optimization in the tensor train format. SIAM J. Sci. Comput. 34(2), A683–A713 (2012)
Jarre, F., Stoer, J.: Optimierung. Springer, Berlin (2004)
Kestler, S.: On the Adaptive Tensor Product Wavelet Galerkin Method with Applications in Finance. PhD thesis, Ulm University (2013)
Khoromskij, B.N.: Tensor-structured preconditioners and approximate inverse of elliptic operators in ℝd. Constr. Approx. 30(3), 599–620 (2009)
Khoromskij, B.N., Oseledets, I.: Quantics-TT collocation approximation of parameter-dependent and stochastic elliptic PDEs. Comput. Methods Appl Math. 10(4), 376–394 (2010)
Khoromskij, B.N., Schwab, C.: Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs. SIAM J. Sci. Comput. 33(1), 364–385 (2011)
Kressner, D., Tobler, C.: Low-rank tensor Krylov subspace methods for parametrized linear systems. SIAM J. Matrix Anal. Appl. 32(4), 1288–1316 (2011)
Nochetto, R.H., Siebert, K.G., Veeser, A.: Theory of adaptive finite element methods: an introduction. In: Multiscale, Nonlinear and Adaptive Approximation, pp 409–542. Springer, Berlin (2009)
Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295–2317 (2011)
Oseledets, I.V., Dolgov, S.V.: Solution of linear systems and matrix inversion in the TT-format. SIAM J. Sci. Comput. 34(5), A2718–A2739 (2012)
Rupp, A.: High Dimensional Wavelet Methods for Structured Financial Products. PhD thesis, Ulm University (2013)
Schmidt, M., Roux, N.L., Bach, F.R.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Shawe-Taylor, J, Zemel, R.S., Bartlett, P.L., Pereira, F., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 24, pp 1458–1466. Curran Associates, Inc. (2011)
Schneider, R., Uschmajew, A.: Approximation rates for the hierarchical tensor format in periodic Sobolev spaces. J. Complexity 30(2), 56–71 (2014)
Stevenson, R.: Optimality of a standard adaptive finite element method. Found Comput. Math. 7(2), 245–269 (2007)
Stevenson, R.: Adaptive wavelet methods for solving operator equations: an overview. In: Multiscale, Nonlinear and Adaptive Approximation, pp 543–597. Springer, Berlin (2009)
Urban, K.: Wavelet Methods for Elliptic Partial Differential Equations. Numerical Mathematics and Scientific Computation. Oxford University Press, Oxford (2009)
Acknowledgments
We would like to thank Markus Bachmayr, Rob Stevenson, and Wolfgang Dahmen for their very helpful comments on this work. This paper was partly written when Mazen Ali was a visiting researcher at Centrale Nantes in collaboration with Anthony Nouy. We acknowledge Anthony Nouy for the helpful discussions and financial support.
Funding
This study was financially supported by the European Model Reduction Network (TD COST Action TD1307).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Alexander Barnett
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ali, M., Urban, K. HT-AWGM: a hierarchical Tucker–adaptive wavelet Galerkin method for high-dimensional elliptic problems. Adv Comput Math 46, 59 (2020). https://doi.org/10.1007/s10444-020-09797-9
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-020-09797-9
Keywords
- High dimensional
- Hierarchical Tucker
- Low-rank tensor methods
- Adaptive wavelet Galerkin methods
- Partial differential equations