expand all | collapse all
Tensor Decomposition and Approximation in Tucker Format
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
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
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
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.
Sparse grids: Part 1
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
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.
Sparse Adaptive Tensor-Product Finite Elements for Radiative Transfer
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
- a stabilized variational formulation of the transport operator,
- so-called sparse tensor products of two hierarchic families of Finite Element
spaces built on triangulations of the spatial domain and the sphere,
- on the local use of full tensor product spaces for the resolution of influx
- on a posteriori thresholding techniques to adapt the discretization to the solution,
- on subspace correction preconditioning of the resulting large linear system
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.
Computing in High Dimensions with Sums of Separable Functions
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
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
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
Pain and Beauty in Quantum Mechanics
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
Sparse Tensor Discretizations
of PDEs with random and multiscale
We report on recent work on
the numerical analysis of several
discretization schemes for PDEs
with random inputs.
Three lectures will address
- 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
- 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.
- Sparse adaptive tensor FEM for
elliptic problems with multiple
scales and random coefficients.
We review classical results on two- and
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
We extend to random coefficients by combining with
1. and 2.