Numerical methods for high-dimensional problems

April 14, 2014 to April 18, 2014
Location : Ecole des Ponts Paristech, France


  • Virginie Ehrlacher (INRIA and Ecole des ponts Paristech, France)
  • Tony Lelievre (INRIA and Ecole des Ponts ParisTech, France)
  • Yvon Maday (UPMC and IUF, France)
  • Anthony Nouy (Ecole Centrale Nantes, France)


Labex Bezout


Labex MMCD



The aim of this tutorial on "Numerical methods for high-dimensional problems" is to give an overview of the different numerical strategies which were developped recently in different application fields to deal with computations involving a large number of variables. Actually, standard numerical methods often fail in this case, since the size of the resulting discretized problems scales exponentially with respect to the number of variates due to the so-called "curse of dimensionality" [1]. To circumvent this problem, a wide variety of methods have been developped recently in different application fields and we particularly aim at enhancing the potential breakthroughs such methods can bring to the field of ab initio electronic structure calculations.

Indeed, for large molecular systems, even in the framework of the Born-Oppenheimer approximation, the resolution of the electronic problem requires to compute the solution of the full many-body Schrödinger equation. The groundstate electronic wavefunction of such systems is an antisymmetric function defined over R^{3N} where N is the number of electrons of the molecule under consideration. The computation of this groundstate is often impossible in practice when N is too large. A full zoology of methods and models [2] have been developped in order to circumvent the curse of dimensionality inherent to ab initio simulations for electronic structure calculations. Density Functional Theory [3] and Hartree-Fock [4] models are among the first solutions which were proposed to deal with this difficulty. Later, post Hartree-Fock methods, such as Multi Configuration Self-Consistent Field (MCSCF) [5], Configuration Interaction (CI) [6], Coupled Clusters (CC) [7], Moller-Plesset (MP) [8], and more recently Density Matrix Renormalization Group (DMRG), tensor network states (TNS) [9] and Green's function [10] methods have also been developped to tackle with this problem. The study of entanglement in many-body systems [11] is also a way to get access to physical information about a given molecule, which may be composed of a large number of atoms, while avoiding the curse of dimensionality.

In this tutorial, we wish to invite people from other commmunities, who do not necessarily work in the field of quantum chemistry computations, but who encounter similar difficulties inherent to the high-dimensional character of the problems they have to solve. In mechanical engineering, uncertainty quantification, optimization and inverse problems, other approaches have recently been developped in order to find practical ways to solve problems involving a significant number of variables. Specific numerical methods are used in these contexts to circumvent the curse of dimensionality and produce accurate reduced-order models, such as sparse grids [12,13], reduced bases [14,15,16], Proper Orthogonal Decomposition (POD) [17], Proper Generalized Decomposition (PGD) [18, 19, 20] and special tensor formats such as Hierarchical Tensor Train (HTT) or Quantized Tensor Train (QTT) [21,22].

The wide variety of all these different approaches, which come from very different backgrounds, may make it very intricate for someone beginning in these fields to have a complete overview of the existing methods.

We propose therefore to organize an intensive 4.5 day tutorial on "numerical methods for high-dimensional problems" open to physicists, mechanists and mathematicians, students and researchers, who are interested in these issues. We would like that this tutorial offers the possibility to draw a picture as complete as possible of the different methods used in different application fields and mathematics to circumvent the curse of dimensionality. Our aim is to bring together people from very different communities, but who share the common point that they have to deal with the resolution of very high-dimensional PDEs in different contexts, in order to present comprehensive introduction to their methods. We hope that the diverse backgrounds of the lecturers will allow for the cross-fertilization of ideas coming from different fields and that discussions between the participants, researchers and students, tackling these kinds of problems with very different point of views might lead to new original ideas in any of these fields, especially for electronic structure computations. We expect to have around 60 participants.

So far, we would like to organize the lectures of the tutorial in thematic days as follows:
-Monday: quantum chemistry;
-Tuesday: mechanics;
-Wednesday: numerical analysis;
-Thursday and Friday: optimization, inverse problems and uncertainty quantification.

Long keynote introductory lectures (9 times 1h30) will be alternated with shorter talks (34 times 45 min). The full programm and more information can be found here.

A poster session will be organized for participants. A roundtable with Thomas Leurent from the Akselos company about "high-dimensional problems and industry" will also be organized.


[1] R.E. Bellman, "Dynamic Programming", Princeton University Press, 1957.
[2] A. Szabo and N.S. Ostlund, "Modern Quantrum Chemistry", Mineola, New York: Dover Publishing, 1996.
[3] P. Hohenberg and W. Kohn, "Inhomogeneous Electron Gas", Phys. Rev. 136 (1964), p B864-B871.
[4] J.C. Slater, "Simplification of the Hartree-Fock Method", Phys. Rev. 81 (1951), p 385-390.
[5] R. Shepard, "The Multiconfiguration Self-Consistent Field method, Ab Initio Methods in Quantum Chemistry - II", Adv. Chem. Phys. 69 (1987), p 63-200.
[6] I. Shavitt, "The method of configuration interaction", Methods of Electronic Structure Theory, Plenum Press, New York, 1977.
[7] R.J. Barlett, C.E. Dykstra and J. Paldus, "Coupled-cluster methods for molecular calculations", Advanced Theories and Computational Approaches to the Electronic Structure of Molecules, D. Reidel, Dordrecht (1984), p 127-159.
[8] S. Grimme, M. Parac and M. Waletzke, "On the importance of third- and fourth-order corrections in multi-reference Moller-Plesset theory", Chem. Phys. Lett. 334 (2001), p. 99-106.
[9] E.N. Economou, "Green's Functions in Quantum Physics", Springer, Berlin, 2006.
[10] K.H. Marti and M. Reiher, "New electron correlation theories for transition metal chemistry", Phys. Chem. Chem. Phys. 13 (2011), p 6750-6759.
[11] C.V. Kraus, N. Schuch, F. Verstraete and J.I. Cirac, "Fermionic projected entangles pair states", Phys. Rev. A 81 (2010), p 052338.
[12] H.J. Bungartz and M. Griebel, "Sparse grids", Acta Numerica (2004), p 1-123.
[13] A. Chkifa, A. Cohen, R. DeVore and C. Schwab, "Sparse adaptative Taylor approximation algorithms for parametric and stochastic elliptic PDEs", ESAIM
Mathematical Modelling and Numerical Analysis, 47 1 (2013), p 253-280.
[14] Y. Maday, "Reduced Basis Method for the Rapid and Reliable Solution of Partial Differential Equations", International Congress of Mathematicians, Vol. III,
Eur. Math. Soc., Zurich (2006), p 1255-1270.
[15] G. Rozza, D.B.P. Huynh and A.T. Patera, "Reduced Basis approximations and a posteriori error estimation for affinely parametrized elliptic coercive partial
differential equations", Archive of Computational Methods in Engineering 15 3 (2008), p 229-275.
[16] P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, P. Wojtaszczyk, "Convergence Rates for Greedy Algorithms in Reduced Basis Methods", SIAM Journal of Mathematical Analysis 43 (2011) p 1457-11472.
[17] F. Troltzsch and S. Volkwein, "POD a-posteriori error estimates for linear-quadratic optimal control problems", Computational Optimization and Applications 44 (2009), p 83-115.
[18] D. Néron and P. Ladevèze, "Proper Generalized Decomposition for Multiscale and Multiphysics Problems", Archives of Computational Methods in Engineering 17 (2012), p 351-372.
[19] A. Falco and A. Nouy, "Proper Generalized Decomposition for Nonlinear Convex Problems in Tensor Banach Spaces", Numerische Mathematik 121 3 (2012), p 503-530.
[20] E. Cancès, V. Ehrlacher and T. Lelièvre, "Greedy algorithms for high-dimensional eigenvalue problems", arxiv 1304.2631.
[19] W. Hackbusch, "Tensor spaces and numerical tensor calculus", Springer, 2012.
[21] V. Khoromskaia, B.N. Khoromskij and R. Schneider, "Tensor-structured Calculation of Two-electron Integrals in a General Basis", SIAM Journal of Scientific Computing, to appear.