23. - 27.08.2010
Zürich summer school


expand all | collapse all

Lars Grasedyck

Tensor Decomposition and Approximation in Tucker Format   [Abstract]

The Tucker format is one of the common and best analysed tensor formats. It corresponds to the multilinear subspace representation of a multidimensional vector or function. The complexity for the storage of an order d tensor in Tucker format scales exponentially in the order d. However, by use of the higher order singular value decomposition (HOSVD) one can obtain almost best approximations (up to a factor squareroot of d) in this format. In this lecture we will review the format, basic algorithms and theoretical results.

The Hierarchical Tucker Format: Definition   [Abstract]

The hierarchical Tucker format (H-Tucker) is a straight-forward generalisation of the Tucker format. It corresponds to a nested multilinear subspace representation of a multidimensional vector or function. The complexity for the storage of an order d tensor in H-Tucker format scales linearly in the order d. In this lecture we consider the definition and the projection of general tensors into the H-Tucker format.

Hierarchical Singular Value Decomposition   [Abstract]

The hierarchical singular value decomposition in H-Tucker format allows us to find almost best approximations of order d tensors in H-Tucker format (up to a factor squareroot of 2d-3). Moreover, the complexity of the H-SVD is linear in the order d of the tensor and thus can be computed even in very high dimensions. We will prove the main result and relate it to similar results in the literature.

Solution of Linear Systems in Tensor Structure   [Abstract]

The solution of linear systems in tensor form, i.e. both the system and the right-hand side (respectively solution) are given (sought) in low rank tensor format, is of interest for matrix equations (order d=2) and higher order d>2. We will review methods and theory based on matrix exponentials, multigrid methods and Krylov subspace iterations. Most of these methods rely on a reliable approximation of iterates in low rank tensor format.

Michael Griebel

Sparse grids: Part 1  [Abstract]

Efficient approximations for multivariate functions can be derived from a one-dimensional multilevel representation of a function (hierarchical basis, generating system, (pre)wavelet system, Fourier series, eigenfunction series or simuilar) by a product construction to obtain a multilevel system for the many-dimensional case and a subsequent proper truncation of the resulting series expansion. This leads to so-called sparse grids which promise to cope with the curse of dimension of conventional product discretizations, at least to some extent. We discuss regular sparse grids and their approximation and cost complexities.

Sparse grids: Part 2  [Abstract]

Besides regular sparse grids, we can construct specific problem-dependent sparse grids by means of an optimization process which exhibit optimal asymptotic complexity estimates for various situations, error norms and regularity assumptions. We present such methods in detail. Furthermore we discuss the dependence of the constants on the dimension in the related complexity estimates.

Ralf Hiptmair

Sparse Adaptive Tensor-Product Finite Elements for Radiative Transfer   [Abstract]

The monochromatic linear radiative transfer equation is a kinetic equation of for the radiation intensity I(x,s), where the independent variable x is from a three-dimensional spatial (physical) domain, whereas s stands for a point on the unit 3-sphere. Hence, I is defined on a five-dimensional tensor product phase space.

Direct Galerkin discretization based on the tensor product of, e.g., piecewise linear finite element functions on a triangulation of the spatial domain and piecewise constants in s, faces formidable computational costs, the well-known "curse of dimensionality".

It can be overcome by an adaptive multilevel Galerkin finite element method that relies on

  1. a stabilized variational formulation of the transport operator,
  2. so-called sparse tensor products of two hierarchic families of Finite Element spaces built on triangulations of the spatial domain and the sphere, respectively,
  3. on the local use of full tensor product spaces for the resolution of influx boundary conditions,
  4. on a posteriori thresholding techniques to adapt the discretization to the solution,
  5. on subspace correction preconditioning of the resulting large linear system of equations.

An a-priori error analysis shows, under strong regularity assumptions on the solution, that the sparse tensor product method is clearly superior to a discrete ordinates method, as it converges with essentially optimal asymptotic rates while its complexity grows essentially only as that for a linear transport problem on the spatial domain. Numerical experiments for two spatial dimensions on a set of example problems agree with the convergence and complexity analysis of the method and show that introducing adaptivity can improve performance in terms of accuracy vs. number of degrees even further.

An efficient implementation of the method can be achieved by sophisticated tree-type data structures. Subspace preconditioning relying on the solution of several transport problems in space paves the way for fast iterative solution of the resulting linear system of equations.

Martin Mohlenkamp

Computing in High Dimensions with Sums of Separable Functions   [Abstract]

A basic need in numerical analysis is the ability to represent and manipulate functions on a computer. Numerical methods developed for functions of one variable do extend to functions of many variables, but their computational complexity grows exponentially with the dimension, a phenomenon dubbed the ``Curse of Dimensionality.'' I will present a method to bypass this curse, based on approximating functions of many variables by sums of separable functions. We will consider the theoretical question of when this representation gives a good approximation and the algorithmic question of how to compute using it.

Multivariate Regression and Machine Learning with Sums of Separable Functions  [Abstract]

To learn (regress) a function, one needs some way to represent it. If the function has many variables, then the curse of dimensionality applies, and one needs a representation that avoids the curse. I will present an algorithm for learning a function of many variables from scattered data. The function is approximated by a sum of separable functions, which has linear complexity in the number of variables. The central fitting algorithm is linear in both the number of data points and the number of variables, and thus is suitable for large data sets in high dimensions. I will then discuss an application to learning material properties.

Approximating the Wavefunction of the Multiparticle Schrodinger Equation   [Abstract]

The multiparticle Schrodinger equation is the basic governing equation in Quantum Mechanics. Its solution, called a wavefunction, is a function of many variables and is constrained to be antisymmetric under exchange of these variables. I will show an abstract Green's function iteration to produce an approximate wavefunction, and then consider how to perform it using a representation of the wavefunction as a sum of separable functions. I will then show how to incorporate the antisymmetry condition and the potential operators into the inner products.

Pain and Beauty in Quantum Mechanics  [Abstract]

If the multiparticle Schrodinger equation was easy to solve, then chemistry would be to boring to support life. I will discuss some painful aspects of the multiparticle Schrodinger equation that make it difficult to solve, and some beautiful mathematics that arises in addressing them.

Christoph Schwab

Sparse Tensor Discretizations of PDEs with random and multiscale data   [Abstract]

We report on recent work on the numerical analysis of several discretization schemes for PDEs with random inputs.

Three lectures will address

  1. Sparse adaptive tensor FEM for elliptic and parabolic PDEs with random loadings.

    We present the problem of elliptic PDEs with random loadings. After a brief review of the necessary mathematical background on random fields as well as on variational formulation of elliptic problems and their Finite Element Discretization, we present basic convergence results on Monte Carlo Finite Element Methods and of sparse tensor discretizations of deterministic, non-hypoelliptic equations for the k-point correlation functions of the random solutions.

  2. Sparse adaptive gpc FEM for elliptic and parabolic PDEs with random coefficients.

    We address the mathematical formulation of elliptic operator equations with random coefficients. We prove representation results of the random solutions by so-called ``polynomial chaos'' expasions in a countable number of variables. We present recent results on regularity of such solutions as well as computational approaches for the adaptive numerical approximation of the infinite dimensional solution.

  3. Sparse adaptive tensor FEM for elliptic problems with multiple scales and random coefficients.

    We review classical results on two- and multiscale homogenization, detailing in particular that multiple scales can traded for high dimension.

    We apply sparse tensor techniques to obtain efficient FE solutions of k-scale elliptic homogenization problems, with error vs. complexity essentially being that the (adaptive) solution of an elliptic one-scale problem. We extend to random coefficients by combining with 1. and 2.