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.
Download als_cross_parametric.zip and unpack it.
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.
There are 5 test scripts (the files you would normally run):
test_als_cross.mTests ALS-Cross algorithm
test_tt_descent.mTests the steepest descent iteration in the TT format, preconditioned by the mean-field deterministic operator
test_sparse_grids.mTests the spinterp algorithm
test_qmc.mTests single-level QMC
test_mlqmc.mTests 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_value2, and so on.
>> 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
evals_*number of deterministic solves
Lnumber 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…
The main routine is
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
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
qmcnodes.m produces “uniform” randomly shifted QMC nodes from a lattice vector.
check_qmc.m, and similar embedded functions in other scripts check prerequisites of the requested test and try to download missing parts.
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
spevalf.patchPatches for the corresponding files in spinterp. By default,
spadaptvals.mrefines 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.
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.