# 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.