Tensor Train ALS-Cross algorithm and experiments

This repository contains the extended TT-Cross and ALS-Cross algorithms from [arXiv: 1707.04562], FEM discretization of the Fruitfly elliptic diffusion equation, and numerical experiments for comparing with (ML)QMC and sparse grid methods.

Installation

Download als_cross_parametric.zip and unpack it.
The als_cross_parametric directory contains Matlab scripts for running numerical experiments and auxiliary files. Each test script should normally download its dependencies automatically. If it fails, the error message will point out what external package must be installed for that test to proceed.

TT algorithms depend on the TT-Toolbox, the sparse grid test uses spinterp, and QMC tests use a lattice vector from F. Kuo http://web.maths.unsw.edu.au/~fkuo/lattice/index.html. Moreover, the Gauss-Hermite rule for normally distributed parameters is taken from SGLIB, and the Gauss-Legendre rule from MatlabCentral.

Usage

Tests

There are 5 test scripts (the files you would normally run):

  • test_als_cross.m Tests ALS-Cross algorithm
  • test_tt_descent.m Tests the steepest descent iteration in the TT format, preconditioned by the mean-field deterministic operator
  • test_sparse_grids.m Tests the spinterp algorithm
  • test_qmc.m Tests single-level QMC
  • test_mlqmc.m Tests multi-level QMC

Each test must be initialized with model/discretization parameters. If a test is run without arguments, the user will be asked to enter all parameters one by one (default values are provided). For a batch run, parameters can be passed in pairs of inputs 'param_name1', param_value1, 'param_name2', param_value2, and so on.
For example,

>> test_qmc('sigma', 1, 'corr_length', 1, 'nu', 3, 'ydist', 'normal', 'coeff', 'exp', 'n_moments', 10, 'runs', 4, 'lvls', 1:4);

will run the QMC test with all default parameters.
Only a subset of parameters can be given, e.g.

>> test_tt_descent('coeff', 'affine', 'ydist', 'uniform');

will apply the corresponding changes (such that the steepest descent converges faster) silently, and ask for all remaining parameters.

Each test tries to plot the error-cost dependence and its linear fit. The reference solution is taken from the finest level (i.e. at least 2 levels are needed to produce the final error estimate, and at least 3 levels to produce a plot). Moreover, it saves the computed Quantities of Interest and other data into files ScriptName_meshlevel.mat and the main Matlab workspace.
Commonly used variables are:

  • Q_* a (vector/matrix/tensor) of QoI
  • ttimes_* CPU times
  • evals_* number of deterministic solves
  • L number of KLE components (may differ from level to level!)
  • err_* final error estimate (w.r.t. the finest-level solution)
  • var_* inner error estimate (empirical standard deviation computed from different runs on the same level and tolerance)

The default run of test_als_cross should complete in 3-5 minutes on a contemporary desktop. The performance for other methods and/or parameters may be significantly different…

TT methods

The main routine is als_cross_parametric.m. Moreover, amen_cross_s.m implements an improved version of TT-Cross (with the residual enrichment). Individual descriptions are provided in the head of each file.

Space discretization and solution

The file build_grid_and_kle.m constructs all data related to the spatial discretization and the KL expansion of the affine field. The direct deterministic solver is implemented in assem_solve_deterministic.m.

QMC

The file qmcnodes.m produces “uniform” randomly shifted QMC nodes from a lattice vector.

Aux files

  • check_tt.m, check_qmc.m, and similar embedded functions in other scripts check prerequisites of the requested test and try to download missing parts.
  • project_blockdiag_mex.* and solve_blockdiag_mex.* MEX libraries for block-diagonal reduction and solution within als_cross_parametric. Unfortunately, even today Matlab loops are quite an overhead… Tested on 64bit Linux and Win, compiled via
>> mex -largeArrayDims -lmwlapack -lmwblas project_blockdiag_mex.c
>> mex -largeArrayDims -lmwlapack -lmwblas solve_blockdiag_mex.c
  • spadaptvals.patch and spevalf.patch Patches for the corresponding files in spinterp. By default, spadaptvals.m refines the parametric grid by estimating the worst relative error among the quantities of interest. This is superfluous for moments of the solution. The first patch replaces max in the error estimate by norm.
    The second patch changes the input format of the deterministic solver function from a list of parameter values to a single matrix, which is more convenient to work with.

Caution!
Sparse Grids experiments are tested only with spinterp version 5.1.1 and GNU patch. spevalf.patch is essential and should be applied manually if the automated procedure fails.