\documentclass[10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[left=1.8cm,right=1.8cm,top=2cm,bottom=2cm]{geometry}
\usepackage{bm}
\usepackage{subfigure}
\usepackage[framed,numbered]{mcode}
% call usepackage mcode here, then lstsets like this to override possible settings of mcode that we don't like
\lstset{backgroundcolor = \color{lightgray}} %sets globally the background color of the code snippets
\lstset{captionpos = b} % the caption of the snippets (if available) is placed below the snippet (use "t" to put them above). 
\lstset{aboveskip={0.5\baselineskip}}  % overrides default def of mcode (1.5)
%\lstset{escapechar=|*} % code between |* and |* will be interpreted as latex, e.g. |* \label{xyz} |* , which can be used to label lines of code
\lstset{escapeinside={|*}{*|}} % same as above, but prettier. Now the code to be interpreted as latex is between |* and *|
\usepackage{dirtree}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{tablefootnote}
\usepackage{url}
\usepackage{xspace}



\newcommand{\hdot}[2][.2ex]{\dot{\raisebox{0pt}[\dimexpr\height+#1][\depth]{$#2$}}} 
\newcommand{\aalpha}{\bm{\alpha}}
\newcommand{\bbeta}{\bm{\beta}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\ii}{\mathbf{i}}
\newcommand{\jj}{\mathbf{j}}
\newcommand{\ee}{\mathbf{e}}
\newcommand{\dd}{\, \mathrm{d}}
\newcommand{\pp}{\mathbf{p}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\oone}{\mathbf{1}}
\newcommand{\Nset}{\mathbb{N}}
\newcommand{\Rset}{\mathbb{R}}
\newcommand{\mcI}{\mathcal{I}}
\newcommand{\mcU}{\mathcal{U}}
\newcommand{\SGK}{SGMK\xspace}

\DeclareMathOperator*{\argmin}{argmin}

\newtheorem{example}{Example}
\newtheorem*{remark}{Remark}

\definecolor{mygray}{gray}{0.85}

\renewcommand{\topfraction}{0.85}

\graphicspath{{./figures/}} 

\begin{document}

\title{The Sparse Grids Matlab Kit user manual \\ \Large{v. 23-5 Robert}}
\author[1,2]{Chiara Piazzola}
\author[1]{Lorenzo Tamellini}
\affil[1]{\small Istituto di Matematica Applicata e Tecnologie Informatiche “E. Magenes” - Consiglio Nazionale delle Ricerche, Via Ferrata, 5/A, 27100, Pavia, Italy}  
%%
\affil[2]{\small Department of Mathematics - Technical University of Munich, Boltzmannstra\ss e, 3, 85748, Garching bei M\"unchen, Germany}

\date{October 9, 2023}  

\maketitle

\begin{abstract}
  The Sparse Grids Matlab Kit provides a Matlab implementation of sparse grids, 
  and can be used for approximating high-dimensional functions and, in particular, for surrogate-model-based uncertainty quantification. 
  It is lightweight, high-level and easy to use, good for quick prototyping and teaching;
  however, it is equipped with some features that allow its use also in realistic applications.
  The goal of this paper is to provide an overview of the data structure and of the mathematical aspects
  forming the basis of the software, as well as comparing the current release of our package to similar available software.
\end{abstract}

\tableofcontents

\section{Introduction}

The Sparse Grids Matlab Kit (\SGK) implements the combination technique form of sparse grids for interpolation and quadrature of high-dimensional functions;
it is geared towards Uncertainty Quantification (UQ) problems but general enough for other purposes.
It is lightweight, high-level and (hopefully) easy to use, good for quick prototyping and teaching.
However, some functionalities (evaluation recycling, buffering strategy for adaptive sparse grid generation,
interface with Matlab parallelization and with other software by the \emph{UM-Bridge} protocol \cite{Seelinger2023:umbridge}) 
make it convenient also for realistic applications.
The \SGK is freely available under the BSD2 license at \url{https://sites.google.com/view/sparse-grids-kit}
  (releases, documentation, release-related material) as well as on Github at \url{https://github.com/lorenzo-tamellini/sparse-grids-matlab-kit} (source code):
the first version was released in 2014 (14-4 ``Ritchie''), and the current version was released in 2023 
(23-5 ``Robert'').
It is written in Matlab, and its compatibility with Octave has been tested. 
No installation is required, i..e, the \SGK folder just needs to be added to the working directory with the usual Matlab \mcode{addpath} command.
The package is organized as illustrated in the following tree diagram:
\medskip 
\dirtree{%
		.1 Sparse Grids Matlab Kit.
		.2 main.
		.2 tools.
		.2 src.
		.2 docs-examples.
              }
\medskip
\noindent
Roughly speaking, the folder \mcode{main} collects all the ``operative'' functions: those for generating sparse grids,
that will be discussed in Sect.\ \ref{sect:sparse_grid_data_struct}, as well as the main functionalities
(quadrature, interpolation, evaluation, plotting, computing derivatives, conversion to polynomial chaos expansions), that will be discussed in Sect.\ \ref{sect:main}.
The folder \mcode{tools} collects all the ``building block'' functions that are required to create a sparse grid
(knots generation, level-to-knots computation, multi-index generation, see Sects.\ \ref{sect:knots}, \ref{sect:lev2knots}, \ref{sect:multiidx-set} respectively),
as well as utility functions for e.g.\ evaluating polynomials, converting between data structures, and interfaces to Matlab parallel functions.
In general, functions in this folder are functions that are ancillary to the functions in \mcode{main} but that the standard user of the \SGK 
will have to use. Conversely, the folder \mcode{src} contains source files with low-level functions that typically are not of interest of the standard users,
but only for \SGK developers. Finally,
the folder \mcode{docs-examples} collects complementary materials, such as several tutorials, a few test examples and a testing unit.
The documentation provided in this user manual is further complemented by the additional documentation provided in the \mcode{help} of each function.
Additionally, a thorough description of the mathematical background of functions and algorithms is provided in the main paper % about the Sparse Grids Matlab Kit
\cite{piazzola.tamellini:SGK}. %\Lnote{da qualche parte andranno spiegate anche i file di testing}

This manual is organized as follows: Sect.\ \ref{sect:sg} introduces the minimal mathematical background necessary
to understand the entities implemented in the \SGK.
Then, Sect.\ \ref{sect:sgk} covers how sparse grids are generated in the \SGK,
how they are stored in memory (data structure) and what options are available for their generation.
Sect.\ \ref{sect:main} discusses the main functionalities made available by the \SGK, as well as how to interface the \SGK with
external software, either by file exchange or by using the \emph{UM-Bridge} protocol. 
Finally, Sect.\ \ref{sect:example} illustrates the usage of the \SGK over a simple (yet quite paradigmatic)
problem of forward and inverse UQ for partial differential equations (PDEs). 
This final example should hopefully convey that it is quite straightforward
to use the \SGK to perform a wide array of possible common tasks in UQ, with a relatively small number of lines of code.
All the code snippets discussed in the paper, as well as the complete code for the final PDE example are available on the \SGK webpage.

\section{A short overview on the basics of sparse grids}\label{sect:sg}
The aim of this section is to briefly recall the mathematical foundations of sparse grids, which guide the software implementation.
We consider the two problems of a) approximating and b) computing weighted integrals of
(the components of) a function $ f: \Rset^N \rightarrow \Rset^V$
given some samples of $f$ whose location we are free to choose. More specifically, we assume that $f$ depends on $N$
random variables $\yy = (y_1, \ldots,y_N) \in \Gamma$, with $\Gamma = \Gamma_1 \times \cdots \times \Gamma_N \subset \Rset^N$
being the set of all possible values of $\yy$. We denote by $\rho_n:\Gamma_n \rightarrow \Rset^+$
the probability density function (pdf) of each variable $y_n$, $n=1,\ldots,N$
and assume independence of $y_1,\ldots,y_N$, such that the joint pdf of $\yy$ is $\rho(\yy) = \prod_{n=1}^N \rho_n(y_n), \forall \yy \in \Gamma$.%

The first step to build a sparse grid is to define a set of collocation knots for each variable $y_n$. 
We thus introduce the univariate discretization level $i_n \in \Nset_+$ and a so-called ``level-to-knots function''
that specifies the number of collocation knots to be used for each random variable, i.e.,
\begin{equation}\label{eq:lev2knots}
	m:\Nset_+ \rightarrow \Nset_+, \ i_n \mapsto m(i_n).  % \text{ such that } m(i_n) = K_n.
\end{equation}  
Then, we denote by $\mathcal{T}_{n,i_n}$ the set of $m(i_n)$ discretization knots along $y_n$, i.e.,
\begin{equation}\label{eq:1d-nodes}
\mathcal{T}_{n,i_n} = \left\{y_{n,m(i_n)}^{(j_n)}: j_n=1, \ldots, m(i_n)\right\} \quad \text{ for } n=1,\ldots,N.  
\end{equation}
Such sequence is usually chosen according to the probability distribution of the random variables $\rho_n$ for efficiency reasons.
Furthermore, for efficiency purposes it is beneficial if the sequences of knots are  \emph{nested}, i.e.,
if $\mathcal{T}_{n,i_n} \subset \mathcal{T}_{n,j_n}$ when $j_n\geq i_n$. These aspects will be further discussed in Sect.\ \ref{sect:knots}.

Next, we introduce the $N$-dimensional tensor grids,
that are obtained by taking the Cartesian product of the $N$ univariate sets of knots just introduced.
For this purpose we collect the discretization levels $i_n$ in a multi-index
$\ii = [i_1,\ldots,i_N] \in \mathbb{N}^N_+$ and denote the corresponding tensor grid by $\mathcal{T}_{\ii} = \bigotimes_{n=1}^{N} \mathcal{T}_{n,i_n}$.
%, and its number of knots by $M_{\ii} = \prod_{n=1}^{N} m(i_n)$.
Using standard multi-index notation, we can {then} write 
\[
  \mathcal{T}_{\ii} = \left\{\yy_{m(\ii)}^{(\jj)}\right\}_{\jj \leq m(\ii)},
  \quad  \text{ with } \quad
  \yy_{m(\ii)}^{(\jj)} = \left[y_{1,m(i_1)}^{(j_1)}, \ldots, y_{N,m(i_N)}^{(j_N)}\right]
  \text{ and } \jj \in \mathbb{N}^N_+,
\]
where $m(\ii) = \left[m(i_1),\,m(i_2),\ldots,m(i_N) \right]$ and $\jj \leq m(\ii)$ means that $j_n \leq m(i_n)$ for every $n = 1,\ldots,N$.

A \textit{tensor grid approximation} of $f(\yy)$ based on global Lagrangian interpolants collocated at these grid knots can then be written in the following form  
\begin{equation} \label{eq:interp_tensor}
	\mathcal{U}_{\ii}(\yy) := \sum_{\jj \leq m(\ii)} f\left(\yy_{m(\ii)}^{(\jj)}\right) \mathcal{L}_{m(\ii)}^{(\jj)}(\yy),
\end{equation}
where $\left\{ \mathcal{L}_{m(\ii)}^{(\jj)}(\yy) \right\}_{\jj \leq m(\ii)}$ are the $N$-variate Lagrange basis polynomials, 
defined as tensor products of univariate Lagrange polynomials, i.e.\  
\begin{equation*}
	\mathcal{L}_{m(\ii)}^{(\jj)}(\yy) = \prod_{n=1}^{N} l_{n,m(i_n)}^{(j_n)}(y_n)
	\quad \text{ with } \quad
	l_{n,m(i_n)}^{(j_n)}(y_n) = \prod_{k=1, k\neq j_n}^{m(i_n)} \frac{y_n-y_{n,m(i_n)}^{(k)}}{y_{n,m(i_n)}^{(j_n)}-y_{n,m(i_n)}^{(k)}}.
\end{equation*}
Similarly, the \emph{tensor grid quadrature} of $f(\yy)$, i.e.\ the approximation of the weighted integral of its components,
can be computed by taking the integral of the Lagrangian {interpolant} in Eq.~\eqref{eq:interp_tensor}:
\begin{align}\label{eq:quad_tensor}
	\mathcal{Q}_{\ii} := \int_{\Gamma} \mathcal{U}_{\ii}(\yy) \rho(\yy) \dd \yy 
	& = \sum_{\jj \leq m(\ii)} f\left(\yy_{m(\ii)}^{(\jj)}\right) \left( \prod_{n=1}^{N} \int_{\Gamma_n} l_{n,m(i_n)}^{(j_n)}(y_n) \rho(y_n) \dd y_n\right) \nonumber \\
	& = \sum_{\jj \leq m(\ii)} f\left(\yy_{m(\ii)}^{(\jj)}\right)  \left( \prod_{i=1}^{N} \omega_{n,m(i_n)}^{(j_n)} \right)
	= \sum_{\jj \leq m(\ii)} f\left(\yy_{m(\ii)}^{(\jj)}\right) \omega_{m(\ii)}^{(\jj)},
\end{align}
where $\omega_{n,m(i_n)}^{(j_n)}$ are the standard quadrature weights obtained by computing the integrals of the associated univariate
Lagrange polynomials, and $\omega_{m(\ii)}^{(\jj)}$ are their multi-variate counterparts. 

Finally, building upon the concepts just introduced, the \emph{sparse grid approximation} of $f(\yy)$ and of its weighted integral
(cf.\ tasks a) and b) above), can be written as
(see e.g.\ \cite[Section 2]{piazzola.tamellini:SGK} for the full derivation of this formula):
\begin{align}
	f(\yy) & \approx \mathcal{U}_{\mathcal{I}} (\yy)
	= \sum_{\ii \in \mathcal{I}} c_{\ii} \, \mathcal{U}_{\ii}\,, \quad c_{\ii}: = \sum_{\substack{\jj \in \{0,1\}^N \\ \ii+\jj \in \mathcal{I}}} (-1)^{\lVert\jj\rVert_1} \label{eq:sg_interp} \\
	\int_\Gamma f(\yy) \rho(\yy) \dd \yy
	& \approx \mathcal{Q}_{\mathcal{I}} (\yy)
	= \sum_{\ii \in \mathcal{I}} c_{\ii} \mathcal{Q}_{\ii},  \label{eq:sg_quad}
\end{align}
with $\mathcal{I} \subset \mathbb{N}_+^{N}$ denoting the multi-index set collecting the multi-indices in the sum.
The \emph{sparse grid} is then defined as 
\begin{equation}\label{eq:sg_grid} 
	\mathcal{T}_\mathcal{I} =  \bigcup_{\substack{\ii \in \mathcal{I} \\ c_{\ii} \neq 0 }} \mathcal{T}_{\ii}.
\end{equation}
The equalities in Eqs.\ \eqref{eq:sg_interp} and \eqref{eq:sg_quad} are known as ``combination technique'' form
of the sparse grids approximation and quadrature, and are valid only if $\mathcal{I}$ is chosen as downward closed, i.e. 
\begin{equation}\label{eq:downward_closed}
	\forall \mathbf{k} \in \mathcal{I}, \quad \mathbf{k} - \ee_n \in \mathcal{I} \text{ for every } n=1,\ldots,N \text{ such that } k_n > 1.  
\end{equation}


\section{Generating sparse grids}\label{sect:sgk}
% \section{The Sparse Grids Matlab Kit}\label{sect:sgk}
Equations \eqref{eq:sg_interp}, \eqref{eq:sg_quad}, and \eqref{eq:sg_grid} are the formulas that constitute the backbone of the implementation of the \SGK.
%\Cchange{Indeed, the \SGK implements the combination technique version of the sparse grids construction.}{}
% \Cchange{The choice of implementing the combination technique instead of the multivariate detail operators \eqref{eq:details}
%   allows to keep the data structure to a minimum, and guarantees ease of use and high-level, ``close-to-the-math'' coding.}{}
We illustrate the package in two steps:
in this section we discuss the creation of the sparse grid data structure, whereas in the next section we describe
the main operations that can be done (interpolation, quadrature, etc). 

The basic creation of a sparse grid is as easy as the following code snippet (Listing \ref{lst:basic_sg_create}).
We report it and then spend the rest of the section dissecting these lines
and discussing the alternative options available for the same operations.%\Cnote{togliamo le opzioni nel plot cosi rimane la versione base?}
% \Lnote{se non li facciamo float, non ha senso cercare di non spezzarli su pagine, no? Si puo' comunque fare, basta
%   inserire lstlisting all'interno di una minipage con ampiezza linewidth. Pero' escono dei grossi pezzi bianchi nelle pagine, quindi e' peggio} 
%   The resulting sparse grid and the corresponding multi-index set are the ones shown in Fig. \ref{fig:sg_comb}
% on the right and \ref{fig:downward_closed_set} on the left, respectively.}
\begin{lstlisting}[label=lst:basic_sg_create,caption={Basic creation of a sparse grid.}]
knots = @(n) knots_uniform(n,0,1); |*\label{line:list1_knots}*|   % Gauss-Legendre knots on [0,1]
lev2knots = @lev2knots_doubling; |*\label{line:list1_lev2knots}*|
I = [1 1;   |*\label{line:list1_Istart}*|
     1 2;
     2 1;
     3 1];  |*\label{line:list1_Iend}*|
S = create_sparse_grid_multiidx_set(I,knots,lev2knots); |*\label{line:list1_construct_grid}*|
Sr = reduce_sparse_grids(S); |*\label{line:list1_reduce_grid}*|
plot_sparse_grid(S,[],'ok','LineWidth',3,'MarkerFaceColor','k','MarkerSize',12) |*\label{line:list1_plot}*| 
\end{lstlisting}
%
The first six lines declare the ``ingredients'' of the sparse grid, while the actual construction of the grid is delegated to Lines
\ref{line:list1_construct_grid} and \ref{line:list1_reduce_grid}. 
The command \mcode{plot_sparse_grids} at Line \ref{line:list1_plot} generates the plot of the sparse grid reported in Fig. \ref{fig:sg-example}.
Most of the lines have a one-to-one correspondence with the mathematical description of sparse grids presented in the previous section:
\begin{itemize}
\item \mcode{knots} is the function to generate the univariate set of collocation knots $\mathcal{T}_{n,i_n}$ in Eq.\ \eqref{eq:1d-nodes};
\item \mcode{lev2knots} is the level-to-knots function $m$ in Eq.\ \eqref{eq:lev2knots}; 
\item \mcode{I} is the multi-index set $\mathcal{I}$ in Eqs.\ \eqref{eq:sg_interp}, \eqref{eq:sg_quad}, \eqref{eq:sg_grid}; 
\item \mcode{S} contains the sparse grid understood as collection of tensor grids $\mathcal{T}_{\ii}$, $\ii \in \mathcal{I}$, $c_{\ii} \neq 0$;
\item \mcode{Sr} contains the sparse grid understood as the union of tensor grids without repetitions of knots in common,
  see Eq.\ \eqref{eq:sg_grid}. We discuss more the generation of \mcode{Sr} in Sec.\ \ref{sect:sg_apriori}.
\end{itemize}

\begin{figure}[tbp]
  \centering
  \includegraphics[width=0.25\textwidth]{SG_final}
  \caption{Sparse grid generated by Listing \ref{lst:basic_sg_create}.}
  \label{fig:sg-example}
\end{figure}

Next, we present and discuss the alternatives available in the \SGK for each of the operations in the listing above:
assignment of the function \mcode{knots} is discussed in Sect.\  \ref{sect:knots},
assignment of the function \mcode{lev2knots} is discussed in Sect.\ \ref{sect:lev2knots},
construction of the multi-index set \mcode{I} is discussed in Sect.\ \ref{sect:multiidx-set},
and finally construction of \mcode{S} and \mcode{Sr}, and the details of the respective data structure are discussed in Sect.\ \ref{sect:sparse_grid_data_struct}.
Note that the alternatives for the first three operations are provided in the \mcode{tools} folder
\medskip
\dirtree{%
.1 tools.
.2 knots\_functions.
.2 lev2knots\_functions.
.2 idxset\_functions.
}
\medskip
%(subfolders \mcode{knots_functions}, \mcode{lev2knots_functions}, and \mcode{idxset_functions}, respectively), 
\noindent whereas the functions for the sparse-grids generation are available in the \mcode{main} folder.

\subsection{Knots functions}\label{sect:knots}

\begin{table}[tb]
  \centering
  \begin{tabular}{llll}
    \hline
    & \textbf{domain} & \textbf{parameters} & \textbf{pdf} \\
    \hline 
    \textbf{uniform}  & $\Gamma = [a,b]$  & $a,b \in \Rset$ & $\rho(y) = \frac{1}{b-a}$  \\[2pt]
    % \hline
    \textbf{normal} & $\Gamma = \Rset$	& $\mu,\sigma \in \Rset$ & $\rho(y) =  \frac{1}{\sigma\sqrt{2\pi}}\mathrm{e}^{-\frac{(y-\mu)^2}{2\sigma^2}}$ \\[6pt]
    % \hline
    \textbf{exponential} & $\Gamma = [0,\infty)$ & $ \lambda \in \Rset, \ \lambda>0$ & $\rho(y) = \lambda \mathrm{e}^{-\lambda y}$ \\[2pt]
    % \hline
    \textbf{gamma} & $\Gamma = [0,\infty)$ & $ \alpha,\beta \in \Rset, \ \alpha>-1, \beta>0$& $\rho(y)= \frac{\beta^{\alpha+1}}{\Gamma(\alpha+1)}x^{\alpha} \mathrm{e}^{-\beta y}$\\[4pt]
    % \hline
    \textbf{beta} & $\Gamma = [a,b]$ & $a,b,\alpha,\beta \in \Rset, \ \alpha,\beta>-1$ & $\rho(y)=\frac{\Gamma(\alpha+\beta+2)}{\Gamma(\alpha+1)\Gamma(\beta+1)(b-a)^{\alpha+\beta+1}}(y-a)^{\alpha}(b-y)^{\beta}$ \\ [5pt]
     \textbf{triangular} & $\Gamma = [a,b]$ & $a,b \in \Rset$ & $\rho(y)= \frac{2}{(b-a)^2} (b-y)$ \\[4pt]
    \hline
  \end{tabular}
  \caption{Random variables and corresponding pdfs. }
  \label{tab:pdf}
\end{table}

We begin by addressing the different types of collocation knots that are implemented in the \SGK,
i.e., the possible options to replace the assignment
in Line \ref{line:list1_knots} of Listing \ref{lst:basic_sg_create}, \mcode{knots = @(n) knots_uniform(n,0,1)}.
As already hinted, the knots should be chosen according to the pdf of the corresponding random variables $y_n$;
in Tab.\ \ref{tab:pdf} we report the random variables that are considered in the \SGK, along with the expression of the respective pdf,
as well as the parameters on which the pdfs depend.

The \SGK provides two families of knots (Gauss-type knots and Leja-type knots)
that can be used to construct collocation knots for almost all the random variables listed in Tab.\ \ref{tab:pdf},
and some additional choices that are available only for certain random variables:
specifically, Clenshaw--Curtis, equispaced knots, and midpoint knots for uniform random variables,
and Genz--Keister knots for normal random variables. We give details on all these families of knots in the next paragraphs,
but we mention already that one big distinction is that some of these families of knots are nested whereas others are not,
and one should in general favor knots of the former class, as stated already in Sect.\ \ref{sect:sg}.
More specifically, Gauss-type knots are not nested, whereas all the other choices are nested.
The full list of knots available in the \SGK and the corresponding commands to generate them are reported in Tab.\ \ref{tab:nodes},
together with a flag to indicate whether a specific choice is nested or not.

\begin{table}[tb]
	\centering
	\begin{tabular}{llll}
		\hline 
		 & \textbf{knots} & \textbf{function} &  \textbf{nestedness} \\
		\hline 
		\textbf{uniform}  & Gauss--Legendre & \mcode{knots_uniform} &  No  \\
		& Clenshaw--Curtis &  \mcode{knots_CC} & Yes for suitable $m$  \\
		& Leja (standard, symmetric, P-disk) &  \mcode{knots_leja} & Yes \\
                 & Equispaced &  \mcode{knots_trap} & Yes for suitable $m$ \\
                 & Midpoint &  \mcode{knots_midpoint} & Yes for suitable $m$ \\          
                \hline
		\textbf{normal} & Gauss--Hermite & \mcode{knots_normal} & No  \\
		& Genz--Keister  & \mcode{knots_GK} &Yes  \\
		& weighted Leja (standard, symmetric) & \mcode{knots_normal_leja} & Yes  \\
		\hline
		\textbf{exponential} & Gauss--Laguerre  &  \mcode{knots_exponential} &No  \\
		& weighted Leja  & \mcode{knots_exponential_leja} & Yes  \\
		\hline
		\textbf{gamma} & Gauss--generalized Laguerre  &  \mcode{knots_gamma} & No  \\
		& weighted Leja &  \mcode{knots_gamma_leja} & Yes  \\
		\hline
		\textbf{beta} & Gauss--Jacobi & \mcode{knots_beta} & No \\
		& weighted Leja (standard, symmetric) & \mcode{knots_beta_leja} & Yes  \\
		\hline
		\textbf{triangular} & weighted Leja & \mcode{knots_triangular_leja} & Yes  \\
		\hline
	\end{tabular}
	\caption{Different type of collocation knots, corresponding function of the \SGK and a flag on the nestedness property.}
	\label{tab:nodes}
\end{table}


\paragraph{Gauss-type knots} Given a pdf, Gauss-type collocation knots are defined as the zeros of the corresponding orthogonal polynomials: 
\begin{itemize}
	\item Legendre polynomials for uniform random variables;
	\item Hermite polynomials for normal (gaussian) random variables;
	\item Laguerre polynomials for exponential random variables;
	\item generalized Laguerre polynomials for gamma random variables;
	\item Jacobi polynomials for beta random variables.
\end{itemize}
The weights can be formally computed by taking the integral of the corresponding Lagrange polynomials. 
However, in practice, knots and weights are more conveniently derived from the eigenvalue decomposition of a suitable matrix,
see e.g.\ \cite{gautschi:orthogonal} for further details.
Note that Gauss-type quadrature rules employing $k$ knots have degree of exactness $2k-1$. 
In Fig.\ \ref{fig:gauss_knots} we display the first 8 Gauss-type knots for the different random variables listed above.

\begin{figure}
	\centering
	\subfigure[Gauss--Legendre knots for uniform variables on {$[0,1]$}]{\includegraphics[width=0.18\textwidth]{legendre}}\hfill
	\subfigure[Gauss--Hermite knots for standard normal variables]{\includegraphics[width=0.18\textwidth]{hermite}}\hfill
	\subfigure[Gauss--Laguerre knots for exponential variables with $\lambda=1$]{\includegraphics[width=0.18\textwidth]{laguerre}}\hfill
	\subfigure[Gauss--generalized Laguerre knots for gamma variables with $\alpha=2$ and $\beta=1$]{\includegraphics[width=0.18\textwidth]{generalized_laguerre}}\hfill
	\subfigure[Gauss--Jacobi knots for beta variables on {$[0,1]$} with $\alpha = \beta = 0.5$]{\includegraphics[width=0.18\textwidth]{jacobi}}
	\caption{Gauss-type knots with the corresponding pdfs.}
	\label{fig:gauss_knots}
\end{figure}


\paragraph{Leja knots} 
Leja knots were first introduced for unweighted interpolation on univariate and bivariate domains, see e.g.\ \cite{marchi:leja}, and are
therefore a suitable choice when $y_n$ are uniform random variables on the interval $[a,b]$. They are built recursively as
\begin{equation}\label{eq:leja}
t^{(1)}=b, \; t^{(2)}=a, \;t^{(3)}=\frac{a+b}{2}, \; \text{and} \; t^{(j)}= \mbox{argmax}_{t \in [a\,b]} \prod_{k=1}^{j-1} \lvert t-t^{(k)}\rvert,  
\end{equation}
and the corresponding quadrature weights are obtained by evaluating the integrals of the Lagrangian polynomials in Eq.\ \eqref{eq:quad_tensor} by Gauss-type quadrature rules with appropriate degree of exactness.  % with appropriate degree of exactness (i.e.\ the first $n$ weights are obtained with Gauss-type quadrature with $\lceil n/2 \rceil $ knots to ensure accuracy of order $n-1$ that is the accuracy of the interpolant).
Observe that by construction Leja knots are nested. 
%\rev{Moreover, Leja sequences are not unique, since the function to be maximized at each iteration might have more than
%  one maximum; this fact is well-known in literature, see e.g. \cite{Chkifa:leja,narayan:Leja}.
%  In our implementation, at each iteration $j$ the maximization problem is solved by a ``brute--force zooming'' algorithm:
%  we look for the maximum over a grid in $[a,b]$ with increasingly small step-size $\Delta x$, over a window that narrows around the location of the current maximum;
%  note that the initial $\Delta x$ is chosen small enough that the maximum is always guaranteed to be the global maximum and not a local one.
%  This computation is only performed once and then collocation points are saved on file (in ASCII format, which we found to be faster to load than \mcode{.mat} files)\Cnote{necessario specificare??},
%  therefore its computational cost is not an issue.
%  When multiple global maxima are present, the implemented algorithm selects the smallest one (with sign). % (as returned by the function \mcode{max} of Matlab).
%  The function that computes the Leja points is \emph{not} released as a \mcode{function} per se in the \SGK
%  but can be found at the beginning of the tutorial \mcode{docs-examples/test_compute_normal_leja_and_convergence_test.m}
%  (with minor variations due to the fact that such tutorial is discussing \emph{weighted Leja} points -- more about these points in a moment).}

A limitation of Leja knots is that they are not symmetric with respect to the mid-point $\frac{a+b}{2}$ of the interval. However, sequences of symmetric knots
can be constructed generating only the even elements of the sequence with the standard formula in Eq.\ (\ref{eq:leja}) and then symmetrizing them to obtain the odd elements, i.e.\
\begin{align}  \label{eq:sym-leja}
& t^{(1)}=b, \; t^{(2)}=a, \;t^{(3)}=\frac{a+b}{2}, \; \nonumber \\
& t^{(2j)}= \mbox{argmax}_{t \in [a\,b]} \prod_{k=1}^{2j-1} \lvert t-t^{(k)}\rvert, \; \nonumber \\
& t^{(2j+1)}= \frac{a+b}{2} - \left(t^{(2j)} - \frac{a+b}{2}\right).  
\end{align}

Another class of Leja-type knots, called P-disk knots, can be obtained projecting on the real axis the Leja knots generated on the complex unit ball.
P-disk knots are then naturally defined on $[-1,1]$, and they amount to:
\begin{align}
  & t^{(j) }= \cos \phi_j\,, \quad 
   \text{ where }
    \begin{cases}
    \phi_1 = 0, \,\,\, \phi_2 = \pi, \,\,\, \phi_3 = \frac{\pi}{2}, \\ \phi_{2j+2} = \frac{\phi_{j+2}}{2},\\  \phi_{2j+3} =\phi_{2j+2}+\pi.    
    \end{cases} \label{eq:pdisk-leja} 
\end{align}
Of course, a linear transformation needs to be applied for random variables on the general interval $[a,b]$.
For more details on this family of knots we refer to \cite{nobile.etal:leja}.
The first 9 knots of the three classes just described are plotted in Fig.\ \ref{fig:uniform_knots}a.

\begin{remark}
	Leja sequences are not unique, since the function to be maximized at each iteration might have more than
	one maximum; this fact is well-known in literature, see e.g.\ \cite{Chkifa:leja,narayan:Leja}.
	In our implementation, at each iteration $j$ the maximization problem is solved by a ``brute--force zooming'' algorithm:
	we look for the maximum over a grid in $[a,b]$ with increasingly small step-size, over a window that narrows around the location of the current maximum;
	note that the initial step-size is chosen small enough that the maximum is always guaranteed to be the global maximum and not a local one.
	This computation is only performed once and then collocation knots are saved on file,
	therefore its computational cost is not an issue.
	When multiple global maxima are present, the implemented algorithm selects the smallest one (with sign). % (as returned by the function \mcode{max} of Matlab).
	The function that computes the Leja knots is \emph{not} released as a \mcode{function} per se in the \SGK
	but can be found at the beginning of the tutorial \mcode{docs-examples/test_compute_normal_leja_and_convergence_test.m}
	(with minor variations due to the fact that such tutorial is discussing \emph{weighted Leja} knots -- more about these knots in the following).
\end{remark}

\begin{figure}[tb]
	\centering
	\subfigure[]{\includegraphics[width = 0.22\textwidth]{leja_uniform}}\hspace{1em}
	\subfigure[]{\includegraphics[width = 0.22\textwidth]{cc_nested}}\hspace{1em}
	\subfigure[]{\includegraphics[width = 0.22\textwidth]{nodes_comparison_uniform}}\hspace{0.5em}
        \subfigure[]{\includegraphics[width = 0.22\textwidth]{nodes_comparison_gaussian}}
	\caption{(a)-(c): Collocation knots for uniform random variables on $[0,1]$:
            (a) Leja knots;
            (b) nested Clenshaw--Curtis (CC) knots;
            (c) comparison of the different types of knots.
            (d): Collocation knots for standard normal random variables.}
	\label{fig:uniform_knots}
\end{figure}

\paragraph{Weighted Leja knots}
It is possible to extend the construction of Leja knots to the case when $y_n$ are
random variables with a probability distribution other than uniform, see \cite{narayan:Leja}.
These knots are the so-called weighted Leja knots and can be computed again recursively,
by suitably introducing a weight in Eq.\ \eqref{eq:leja}, i.e., solving 
\[
t^{(j)}= \mbox{argmax}_{t\in \Gamma} \sqrt{\rho(t)} \prod_{k=1}^{j-1} (t-t^{(k)}),
\] 
where $\rho$ is the pdf of the random variable and $\Gamma$ its domain. The same computational considerations discussed
  for the standard (non-weighted) Leja knots are valid for the weighted Leja knots as well.
As for standard Leja sequences, weighted sequences can be symmetrized, extending analogously Eq.\ \eqref{eq:sym-leja}.
In the \SGK, weighted Leja knots are available for all supported random variables, whereas
symmetric weighted Leja knots are available only for random variables with symmetric pdfs, namely for normal and beta random variables
(in the latter case, only when the pdf parameters $\alpha,\beta$ are identical, cf. Tab.\ \ref{tab:pdf}). 

\paragraph{Clenshaw--Curtis knots} Besides the variants of Leja knots, the so-called Clenshaw--Curtis knots are
another nested alternative to Gauss-type knots
in case of uniform random variables. They are computed on $[-1,1]$ as 
\[
t_K^{(j)} =\cos\left(\frac{(j-1) \pi}{K-1}\right), \quad 1\leq j \leq K,
\]
and then linearly transformed to any generic interval $[a,b]$;
the corresponding weights can be efficiently computed by Fast Fourier Transform, see \cite{trefethen:comparison}.
Quadrature formulas based on this family of knots result to be as accurate as the Gauss-type quadrature.
Moreover, two sets of Clenshaw-Curtis knots with $K_1$ and $K_2$ knots are nested if $(K_2 - 1)/(K_1 -  1) = 2^l$ for some integer $l$.
Such sequences are obtained e.g.\ for $K=1,3,5,9,17$, see Fig.\ \ref{fig:uniform_knots}b.

\paragraph{Equispaced and midpoint knots} 
These two sequences of knots are provided for uniform random variables only.
  They provide classical low-order quadrature formulas \cite{quarteroni.sacco.eal:numerical}
  and can therefore be useful for quadrature of functions with low regularity. In particular:
  \begin{itemize}
    \item Equispaced knots in $[a,b]$ are provided by the function \mcode{knots_trap} that implements the trapezoidal quadrature rule
    with knots $t^{(j)}_K$ and weights $\omega_K^{(j)}$
      \[
        \begin{cases}
          t_K^{(j)} = a + h(j-1) & 1\leq j \leq K \\[4pt]
          \omega_K^{(1)} = \omega_K^{(K)} = h/2\\[4pt]
          \omega_K^{(j)} = h & 2 \leq j \leq K-1
        \end{cases}
        \quad 
        \mbox{ with }
        h = \frac{1}{K-1}.
      \]
      Similarly to Clenshaw--Curtis knots, two sets of equispaced knots with $K_1$ and $K_2$ knots are nested if $(K_2 - 1)/(K_1 -  1) = 2^l$ for some integer $l$.
    \item Midpoint knots are provided by the function \mcode{knots_midpoint}, that implements the midpoint quadrature rule:
      \[
        \begin{cases}
          \displaystyle t_K^{(j)} = a + \frac{h}{2} + h(j-1) & 1\leq j \leq K \\[4pt]
          \omega_K^{(j)} = h & 1\leq j \leq K 
        \end{cases}
        \quad \mbox{ with } h = \frac{1}{K}.
      \]
      Two sets of midpoint knots with $K_1$ and $K_2$ knots are nested if $K_2/K_1 = 3^l$ for some integer $l$.
    \end{itemize}
  Observe that these two rules depart a bit from the general framework of the package, in that they do not derive quadrature weights as integral
  of global Lagrange polynomials, but rather as integrals of \emph{piecewise} Lagrange polynomials (linear and constant, respectively).
  However, we remark that the package does \emph{not} provide piecewise interpolation, but only global interpolation.
  Therefore, if one were to use these knots to build a sparse grid \emph{interpolant} of a function, Runge phenomena
  can be expected, leading to poor approximations. These knots are thus to be intended essentially as quadrature knots only.
To summarize, in Fig.\ \ref{fig:uniform_knots}c we give a comparison of the types of collocation knots available for uniform random variables.


\paragraph{Genz--Keister knots}
The sequence of Genz--Keister knots is obtained by modifying the sequence of Gauss--Hermite knots to enforce nestedness,
see \cite{genz.keister:kpnquad}.  
The knots and the corresponding weights are tabulated and available for $K = 1,3,9,19,35$. 
In Fig.\ \ref{fig:uniform_knots}d %\ref{fig:gaussian_knots}
we display the first 9 Genz--Keister knots, together with Gauss-type and symmetric weighted Leja knots for normal random variables.


\subsection{Level-to-knots functions}\label{sect:lev2knots}
The above list of knots can be used in conjunction with different types of level-to-knots functions (see Eq.\ \eqref{eq:lev2knots})
that associate the discretization levels collected in the multi-index $\ii$ to the number of collocation knots to be used;
of course, some choices are smarter than others, such as those that guarantee nestedness. 
For example, in the case of Clenshaw--Curtis knots, any number of knots can be used,
but a specific relation must hold between the cardinality of the sequences of knots such that they are nested (see discussion above).
In the case of symmetric Leja knots instead, it is natural to use a level-to-knots function
that adds two knots (or, more generally, an even number of knots) at each level,
to make sure that sequences that are constructed by symmetrization are actually used as such.

In Tab.\ \ref{tab:lev2knots} we list the level-to-knots functions that are implemented in the \SGK,
which are the possible options to replace the assignment in Line \ref{line:list1_lev2knots} of Listing \ref{lst:basic_sg_create}, \mcode{lev2knots = @lev2knots_doubling}.
The function \textit{linear} can be used for Gauss-type and Leja knots:
however, as already pointed out, in case of symmetric Leja knots it is convenient to resort to the functions of type \textit{2-step} or \textit{doubling}.
The function of type \textit{doubling} is essential for the generation of sequences of nested Clenshaw--Curtis and equispaced knots;
the function \textit{tripling} must be used to obtain nested midpoint knots,
and the tabulated function \textit{Genz--Keister} is specific for the case of Genz--Keister knots. 
Table \ref{tab:recap_nested} gives an overview on the possible combination of knots and level-to-knots functions that generate sequences of nested collocation knots. 

\begin{table}[tb]
	\centering
	\begin{tabular}{lll}
		\hline 
		& \textbf{definition} & \textbf{function} \\
		\hline
		\textbf{linear}  	& $m(i_n) = i_n$ & \mcode{lev2knots_lin} \\
		\textbf{2-step}  	& $m(i_n) = 2(i_n-1)+1$ & \mcode{lev2knots_2step}  \\
		\textbf{doubling} 	& $m(1) = 1$, $m(i_n) = 2^{i_n-1}+1$ &  \mcode{lev2knots_doubling} \\
		\textbf{tripling}   & $m(i_n) = 3^{i_n-1}$ &  \mcode{lev2knots_tripling} \\
          	\textbf{Genz--Keister} 	& $m(1)=1, m(2)=3, m(3)= 9$, $m(4) =19$, $m(5) = 35$ & \mcode{lev2knots_GK}\\
		\hline
	\end{tabular}
	\caption{Types of level-to-knots functions and corresponding function of the \SGK.}
	\label{tab:lev2knots}
\end{table}


\begin{table}
	\centering
	\begin{tabular}{lll} 
		\hline
		    & \textbf{knots} & \textbf{level-to-knots functions for nestedness} \\
		\hline
		\textbf{uniform} & Leja - standard   & linear, 2-step, doubling \\
			& Leja - symmetric  & linear, 2-step, doubling\\
			& Leja - P-disk     & linear, 2-step, doubling\\
                        & Clenshaw--Curtis  & doubling \\
                        & equispaced & doubling \\
          		& midpoint   & tripling \\	
		\hline
		\textbf{normal} & weighted Leja - standard & linear, 2-step, doubling \\
		         & weighted Leja - symmetric & linear, 2-step, doubling\\
		         & Genz--Keister  & Genz--Keister \\
		\hline
		\textbf{exponential} & weighted Leja  & linear, 2-step, doubling \\
		\hline
		\textbf{gamma} & weighted Leja & linear, 2-step, doubling\\
		\hline
		\textbf{beta} & weighted Leja - standard  &  linear, 2-step, doubling \\
               	      & weighted Leja - symmetric & linear, 2-step, doubling \\
        \hline
        \textbf{triangular} & weighted Leja - standard  &  linear, 2-step, doubling \\
        \hline
	\end{tabular}
	\caption{Families of knots with the corresponding level-to-knots functions to ensure nestedness.}
	\label{tab:recap_nested}
\end{table}


\subsection{Multi-index sets}\label{sect:multiidx-set}
As discussed in \cite[Section 2]{piazzola.tamellini:SGK}, the quality of the sparse grid approximations \eqref{eq:sg_interp} and \eqref{eq:sg_quad}
depends on the choice of the multi-index set $\mathcal{I}$.
% Roughly speaking, we can think that the larger the multi-index set, the more terms the approximation includes and the better the approximation,
% but also the larger the number of knots where $f$ has to be evaluated and hence the cost: therefore, some trade-off between accuracy and cost must be found.
One approach to this end is to design the set based on some knowledge on the problem at hand, such as the smoothness of the function to be approximated;
an alternative ``a-posteriori''/adaptive approach will be discussed later on.

Note that multi-indices are always stored in the \SGK as \emph{row vectors} with $N$ components, and multi-index sets are correspondingly stored as
matrices, each row being a multi-index; moreover, it is required that such matrices are in \emph{lexicographic order} by row.
%\Lchange{(i.e., the multi-indices are listed in the multi-index set in lexicographic order).}{}
This check is of course \emph{not} delegated to the user (\SGK functions operating on multi-index sets will check ordering and throw an error if a set is not sorted).

Another requirement on multi-index sets is the already mentioned downward-closedness property, see Eq.\ (\ref{eq:downward_closed}):
to this end, the \SGK provides the function \mcode{check_set_admissibility(I)}, which in case of non-downward-closedness of the set \mcode{I}
also returns the smallest downward-closed set that includes \mcode{I}. For visualization purposes, the \SGK also provides
the function \mcode{plot_multiidx_set} (which supports only the cases $N=2,N=3$). 
 

Small multi-index sets can be typed in ``manually'',
such as in Lines \ref{line:list1_Istart}-\ref{line:list1_Iend} of Listing \ref{lst:basic_sg_create},
but of course dedicated functions are available. In particular \mcode{multiidx_box_set(jj)}, where \mcode{jj} is a multi-index,
generates the hyper-rectangular (a.k.a. ``box'') set $\mathcal{I} = \{ \ii \in \Nset_+^N : \ii \leq \jj\}$.
Furthermore, most multi-index sets that can be written as $\mathcal{I} = \{ \ii \in \Nset_+^N : r(\ii) \leq w \}$
for $r:\Nset_+^N\rightarrow \Rset_+$ and $w \in \Nset_+$
%\Cnote{togliamo o aggiungiamo qualcosa su r}
can be created invoking the function \mcode{multiidx_gen} as follows
\begin{lstlisting}[label=lst:multiidx_gen,caption={Creation of a multi-index set.}]
N = 2;
rule = @(ii) sum(ii-1);
w = 4; 
base = 1;
I = multiidx_gen(N,rule,w,base); 	
\end{lstlisting}
where \mcode{rule} is a \mcode{@}-function such that \mcode{rule(ii)} evaluates $r(\ii)$, and the integer value $w$ defines the size of the multi-index set,
and hence controls the quality of the associated sparse grid approximation. In the following, we refer to
$r$ as \textit{rule of the approximation} and to $w$ as \textit{level of the approximation}.
The implementation of \mcode{multiidx_gen} is recursive over $n$, $n=1, \ldots, N$.
This is a flexible solution that can accommodate for a wide range of rules $r$ (although admittedly not the most efficient speed-wise):
the only requests are that $r$ is non-decreasing in each argument, and that $r(\jj) > w \Rightarrow r([\jj, 1]) > w, \forall \jj \in \Nset^n_+, n < N$.

A list of multi-index sets $\mathcal{I}$ commonly found in literature and the
implementation of the corresponding \mcode{rule} in Matlab is available in Tab.\ \ref{tab:idxset}. 
The vectors $\mathbf{g} \in \Rset_+^N$ {appearing in the definitions in Tab.\ \ref{tab:idxset}}\footnote{The peculiar writing \mcode{g(1:length(ii))} is due to fact that \mcode{multiidx_gen} works recursively on the directions $n=1$ to $N$,
  and therefore we need to be able to call the \mcode{@}-function also when the length of \mcode{g} and \mcode{ii} do not match.}
  are the so-called \textit{anisotropy weights},
whose purpose is to tune the shape of the multi-index set in such a way that more collocation knots are placed in the random variables deemed
to be more important; in particular, the larger the weight, the more penalized the corresponding variable, i.e.\ the lower the number of collocation knots
placed on that random variable. Whenever $g_1=\ldots=g_N$, the resulting grid is named \textit{isotropic}, and \textit{anisotropic} otherwise.
Finally, we clarify the role of the line \mcode{base=1} in Listing \ref{lst:multiidx_gen}:
its purpose is to specify that the smallest entry of each multi-index is $1$
(another option would be \mcode{base=0}; multi-index sets like these will be needed later on, in Sect.\ \ref{sec:PCE_and_sobol}).
We further illustrate the use of \mcode{multiidx_gen} with the help of the following example.

\begin{table}[tb]
	\centering
	\begin{tabular}{ll} 
		\hline
		\textbf{definition} & \textbf{function} \\
		\hline 
		$\mathcal{I}_{\text{max}}(w) = \left\{ \ii \in \Nset^N_+ : \max_{n} g_n (i_n-1) \leq w  \right\}$ & \mcode{rule = @(ii) max(g(1:length(ii)).*(ii-1))} \\
                $\mathcal{I}_{\text{sum}}(w) = \left\{ \ii \in \Nset^N_+ : \sum_{n=1}^N g_n (i_n-1) \leq w  \right\}$
                                    & \mcode{rule = @(ii) sum(g(1:length(ii)).*(ii-1))}  \\
		$\mathcal{I}_{\text{prod}}(w) = \left\{ \ii \in \Nset^N_+ : \prod_{n=1}^N i_n^{g_n} \leq w  \right\}$ &  \mcode{rule = @(ii) prod((ii).^g(1:length(ii)))} \\
		\hline
	\end{tabular}
	\caption{Multi-index sets and corresponding definitions in Matlab.}
	\label{tab:idxset}
\end{table}

\begin{example}[Multi-index sets]\label{ex:multi-index_sets}
The two-dimensional isotropic multi-index set $\mathcal{I}_{\text{sum}}(4)$ can be generated as in Listing \ref{lst:multiidx_gen}. 
For the case of anisotropic sets we have to further specify the vector of weights $\mathbf{g}$:%\Cnote{togliamo le opzioni del plot?}
\begin{lstlisting}
N = 2; 
g = [1,2]; 
rule = @(ii) sum(g(1:length(ii)).*(ii-1));  |*\label{line:list_set_define_shape}*|
w = 4; 
base = 1; 
I_aniso = multiidx_gen(N,rule,w,base); 
plot_multiidx_set(I_aniso,'sk','LineWidth',2,'MarkerSize',22,'MarkerFaceColor','b')
\end{lstlisting}
Figure \ref{fig:spaces} (top-row) shows the isotropic and anisotropic version of the index sets, together with the corresponding sparse grids,
generated using symmetric Leja knots and level-to-knots function of type 2-step. The code to generate such grids
is almost identical to the one in Listing \ref{lst:basic_sg_create} and  will be discussed in details later on.

The following rows of the figure show multi-index sets and grids for the other choices of sets introduced
in Tab.\ \ref{tab:idxset}, i.e., $\mathcal{I}_{\text{max}}$ (mid-row of the figure) and $\mathcal{I}_{\text{prod}}$ (bottom-row of the figure), again in their isotropic and anisotropic
versions (left and right part of the figure, respectively).
The code to generate these multi-index sets is identical to the listing above (other than changing Line \ref{line:list_set_define_shape} with the appropriate definition from Tab.\ \ref{tab:idxset}).%\Cchange{, therefore we do not report it}{}.
Note that $\mathcal{I}_{\text{max}}$ sets can be equivalently generated with the command
\mcode{multiidx_box_set}.
Finally, we also mention that for faster generation of $\mathcal{I}_{\text{sum}}$, the function \mcode{fast_TD_set} is available - the reason for this naming will be clearer later on.
% \Ch{Finally, note that the listing above also reports how to use the function \mcode{plot_multiidx_set} to plot a multi-index set.}
\end{example}

\begin{figure}[t]
	\centering
	\subfigure[Isotropic $\mathcal{I}_{\text{sum}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{TD_iso} % \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_TD_iso}} \hfill
	\subfigure[Anisotropic $\mathcal{I}_{\text{sum}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{TD_aniso} % \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_TD_aniso}} \\
	\subfigure[Isotropic $\mathcal{I}_{\text{max}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{TP_iso} % \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_TP_iso}} \hfill
	\subfigure[Anisotropic $\mathcal{I}_{\text{max}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{TP_aniso} % \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_TP_aniso}} \\
        \subfigure[Isotropic $\mathcal{I}_{\text{prod}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{HC_iso} % \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_HC_iso}} \hfill
	\subfigure[Anisotropic $\mathcal{I}_{\text{prod}}(4)$ (left) and corresponding grid (right)]{\includegraphics[width=0.22\textwidth]{HC_aniso}% \hspace{1em}
	\includegraphics[width=0.235\textwidth]{SG_HC_aniso}}
      \caption{Isotropic and anisotropic multi-index sets and corresponding sparse grids of symmetric Leja knots on $\Gamma = [0,1]^2$
        generated using level-to-knots function of type 2-step.}
	\label{fig:spaces}
\end{figure}

Typing rules of Tab.\ \ref{tab:idxset} might be inconvenient, especially if anisotropic rules are needed. To this end, 
the \SGK provides the convenience function \mcode{define_functions_for_rule} 
that takes as input a string (``the name of the sparse grid'') and returns the associated rule and level-to-knots function
for a number of common cases (see Tab.\ \ref{tab:presets}): 
\begin{lstlisting}
[lev2knots,rule] = define_functions_for_rule(<string-name>)
\end{lstlisting}
%
% The names of the sparse grids, together with the cre and level-to-knots functions needed to generate them, are reported in Tab.\ \ref{tab:presets}.
The first three names (\mcode{'TP','TD','HC'}) are borrowed from the literature on polynomial approximation spaces,
and refer to the Tensor Product, Total Degree, and Hyberbolic Cross spaces, respectively, see \cite[Section 2]{piazzola.tamellini:SGK}.
% Indeed, each sparse grid approximation is a polynomial approximation,
% and it can be shown that the polynomial approximations generated by these pre-sets belong to the above-mentioned polynomial spaces \cite{back.nobile.eal:comparison}.
The fourth name \mcode{'SM'} refers to one of
the most used type of sparse grid, the so-called \textit{Smolyak} grid, which is obtained combining $\mathcal{I}_{\text{sum}}$
with the level-to-knots function of type \textit{doubling} (the complete example will be given in Listing \ref{lst:smolyak_grid}).
\begin{table}[tb]
  \centering
  \begin{tabular}{lcc}
    \hline
    \textbf{name} & \textbf{set generated by the rule} & \textbf{level-to-knots functions} \\
    \hline
    \mcode{'TP'}& $\mathcal{I}_{\text{max}}$	& \mcode{linear} \\
    \mcode{'TD'}& $\mathcal{I}_{\text{sum}}$	& \mcode{linear} \\
    \mcode{'HC'}& $\mathcal{I}_{\text{prod}}$	& \mcode{linear} \\
    \mcode{'SM'}& $\mathcal{I}_{\text{sum}}$	& \mcode{doubling} \\
    \hline
  \end{tabular}
  \caption{Pre-sets available in \mcode{define_function_for_rule}. Rules are defined in Tab.\ \ref{tab:idxset}, level-to-knots functions in Tab.\ \ref{tab:lev2knots}.}
  \label{tab:presets}
\end{table}


\subsection{Sparse grid generation and data structure}\label{sect:sparse_grid_data_struct}

We are finally ready to discuss Lines \ref{line:list1_construct_grid} and \ref{line:list1_reduce_grid} of Listing \ref{lst:basic_sg_create},
that are responsible of generating the sparse grid.
The approach reported in the snippet can be called \textit{a-priori}, since it requires to specify the
multi-index set $\mathcal{I}$ \textit{before} sampling the function $f$.
In this section we detail this approach first, and then discuss also the ``dual'' approach, i.e.\ the \textit{adaptive} algorithm
to generate sparse grids, in which the multi-index set $\mathcal{I}$ is computed \textit{simultaneously} to the sampling of the function $f$ (Sect.\ \ref{sect:adaptive_sg}).
Note that regardless of the way in which sparse grids are generated, they are eventually stored with the same data structure, that we describe below
while discussing the \textit{a-priori} approach.

\subsubsection{A-priori sparse grids}\label{sect:sg_apriori}
Listing \ref{lst:basic_sg_create} shows a first way to generate a sparse grid with the multi-index set determined a-priori: directly typing in the set,
(or using the functions \mcode{multiidx_box_set}, \mcode{multiidx_gen}, or \mcode{define_functions_for_rule}),
and then using the function \mcode{create_sparse_grid_multiidx_set}.
Another possibility is to call the command \mcode{create_sparse_grid},
that takes care of generating both the multi-index set given the rule and the associated sparse grid in one call, as shown in the following snippet.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{lstlisting}[label=lst:smolyak_grid,caption={{Basic creation of a sparse grid given a multi-index set defined by a rule.}}]
N = 2;
w = 3; 
knots = @(n) knots_CC(n,0,1);
lev2knots = @lev2knots_doubling;
rule = @(ii) sum(ii-1); 
S = create_sparse_grid(N,w,knots,lev2knots,rule);
\end{lstlisting}

The output of \mcode{create_sparse_grid} (and of \mcode{create_sparse_grid_multiidx_set}) is a sparse grid
in the so-called \emph{extended format}, that stores separately the information of each tensor grid
composing the sparse grid (more precisely, of those grids whose coefficient in the combination technique formula is non-zero, see Eqs.\ \eqref{eq:sg_interp}, \eqref{eq:sg_quad}, and \eqref{eq:sg_grid}).
The data structure chosen to this end is a structure array, where each structure identifies one of the tensor grids: \newpage
\begin{lstlisting}
>> S
S = 

1x7 struct array with fields:

knots
weights
size
knots_per_dim
m
coeff
idx
\end{lstlisting}
Each tensor grid structure contains the following fields:
\begin{itemize}
  \item \mcode{idx}: the multi-index {$\ii \in \mathcal{I}$} corresponding to the current tensor grid; 
  \item \mcode{knots}: matrix collecting the knots {$\mathcal{T}_{\ii}$}, each knot being a column vector;
  \item \mcode{weights}: vector of the quadrature weights {$\omega_{m(\ii)}^{(\jj)}$} corresponding to the knots; 
  \item \mcode{size}: size of the tensor grid, i.e.\ the number of knots {$M_{\ii} = \prod_{n=1}^{N} m(i_n) $};
  \item \mcode{knots\_per\_dim}: cell array with $N$ components, each component collecting {in an array} the set of one-dimensional knots {$\mathcal{T}_{n,i_n}$}
    used to build the tensor grid;
  \item \mcode{m}: vector collecting the number of knots used in each of the $N$ directions {$m(\ii) = \left[m(i_1),\,m(i_2),\ldots,m(i_N) \right]$};
  \item \mcode{coeff}: the coefficients {$c_{\ii}$} of the sparse grid in the combination technique formulas \eqref{eq:sg_interp} and \eqref{eq:sg_quad}. 
  \end{itemize}
  Note in particular that sparse grid knots (and in general knots $\yy \in \Gamma$) are always stored in the \SGK as column-vectors
  (and sets of knots such as \mcode{S.knots} are stored as matrices where knots are columns). 

The structure array above has seven components,
since seven tensor grids are used in the construction of the sparse grid.
% {(cf. the} right plot of Fig. \ref{fig:sg_final}, {where seven multi-indices are reported with non-zero coefficient).} 
We report below the first component of the structure array:
%\Lchange{, i.e. the structure describing the first tensor grid.}{} 
\begin{lstlisting}
>> S(1)
ans = 

struct with fields:

knots: [2x5 double]
weights: [-0.0333 -0.2667 -0.4000 -0.2667 -0.0333]
size: 5
knots_per_dim: {[0.5000]  [1 0.8536 0.5000 0.1464 0]}
m: [1 5]
coeff: -1
idx: [1 3]
\end{lstlisting}
In Fig.\ \ref{fig:sg_structure}a we plot the sparse grid generated in Listing \ref{lst:smolyak_grid},
and in Fig.\ \ref{fig:sg_structure}b--h the seven tensor grids that explicitly contribute to it.
\begin{figure}[t]
	\centering
	\subfigure[$\mathcal{T}_{\mathcal{I}_{\text{sum}}(3)}$]{\includegraphics[width = 0.22\textwidth]{ex_SG_final}}\hspace{0.3em}
	\subfigure[$\mathcal{T}_{[1,3]}$ with $c_{[1,3]}= -1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_1}} \hspace{0.3em}
	\subfigure[$\mathcal{T}_{[1,4]}$ with $c_{[1,3]}= 1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_2}} \hspace{0.3em}
	\subfigure[$\mathcal{T}_{[2,2]}$ with $c_{[1,3]}= -1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_3}} \\
	\subfigure[$\mathcal{T}_{[2,3]}$ with $c_{[1,3]}= 1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_4}}  \hspace{0.3em}
	\subfigure[$\mathcal{T}_{[3,1]}$ with $c_{[1,3]}= -1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_5}} \hspace{0.3em}
	\subfigure[$\mathcal{T}_{[3,2]}$ with $c_{[1,3]}= 1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_6}} \hspace{0.3em}
	\subfigure[$\mathcal{T}_{[4,1]}$ with $c_{[1,3]}= 1$]{\includegraphics[width = 0.22\textwidth]{ex_SG_7}}	\hspace{0.3em}
	\caption{The sparse grid generated by Listing \ref{lst:smolyak_grid} and the seven tensor grids that generate it.}
	\label{fig:sg_structure}
\end{figure}
We can easily observe that some knots appear in multiple tensor grids, and therefore
the sparse grids structure \mcode{S} contains redundant information. 
This is a general fact, happening not only when nested knots are used, but also (to a smaller extent) in the case of non-nested knots.
Hence, it is convenient to generate a structure containing only the non-repeated knots and a list of corresponding weights,
that can be computed taking the linear combination of the quadrature weights of each instance of the repeated knot
with the combination coefficient weights in Eq.\ (\ref{eq:sg_interp}).
This can be done calling the function \mcode{Sr = reduce_sparse_grid(S)}, that outputs a unique structure containing the following fields:
\begin{itemize}
  \item \mcode{knots}: matrix collecting the list of non-repeated knots, i.e., the set $\mathcal{T}_{\mathcal{I}}$ in Eq.\ \eqref{eq:sg_grid}; 
  \item \mcode{weights}: vector of quadrature weights corresponding to the knots {above}; 
  \item \mcode{size}: size of the sparse grid, i.e.\ the number of non-repeated knots;  
  \item \mcode{m}: index array that maps each knot of {\mcode{Sr.knots}} {to their original position in} {\mcode{[S.knots]}
      (if they have been retained as unique representative of several repeated knots)};
  \item \mcode{n}: index array that maps each knot of {\mcode{[S.knots]}} to {\mcode{Sr.knots}}.
\end{itemize}
%In practice, the list of unique knots is created by detecting (up to a certain tolerance, tunable by the user) the identical knots and deleting the possible repetitions. 
%The quadrature weights of the repeated knots are obtained 
%taking the linear combination of the quadrature weights of each instance of the repeated knot with the combination coefficient weights in Eq.\ (\ref{eq:sg_interp}).
For instance, the sparse grid {\mcode{S} above} consists of 67 knots
\begin{lstlisting}[]
>> size([S.knots])
ans =

2    67
\end{lstlisting} 
%most of them repeated in multiple tensor grids {(cf. Fig.\ \ref{fig:sg_structure}b--h)}.
and the corresponding reduced sparse grid results in 29 non-repeated knots:  
\begin{lstlisting}[]
>> Sr = 

struct with fields:

knots: [2x29 double]
m: [29x1 double]
weights: [1x29 double]
n: [67x1 double]
size: 29
\end{lstlisting}
%Note that obeying to the storing convention of \SGK, the knots in the reduced set are stored as columns of the matrix \mcode{Sr.knots}.
%%\Lnote{add details on how in the paper and report here}
Both extended and reduced formats are useful for working with sparse grids and should always be stored in memory,
although this implies a certain redundancy in memory storage;
see \cite[Section 3]{piazzola.tamellini:SGK} for some considerations and numerical tests about the performance of \mcode{reduce_sparse_grid}.
% This implies a certain redundancy in memory storage, and reducing a sparse grid takes a non-negligible computational time,
% see \cite{piazzola.tamellini:SGK}.
% However, having the two structures at hand considerably simplifies coding operations
% on sparse grids such as interpolation or conversion to Polynomial Chaos Expansion (more on these operations later on),
% and hides a lot of complexity from the final user. \Cnote{togliere le ultime due frasi? Lo scriviamo gia' nel paper.}

Finally, for quick generation of a sparse grid (both extended and reduced formats), the \SGK provides also the convenience function
\mcode{create_sparse_grid_quick_preset}, which generates Smolyak grids of level $w$ with Clenshaw--Curtis knots
in the default interval $[-1,1]^N$, and only takes as inputs $N$ and $w$
\begin{lstlisting}[]
>> [S,Sr] = create_sparse_grid_quick_preset(N,w);
\end{lstlisting}

\subsubsection{Adaptive sparse grids} \label{sect:adaptive_sg}
The \SGK provides also the possibility to construct adaptive sparse grids, i.e.\ sparse grids where the multi-index set,
and hence the approximations in Eqs.\ \eqref{eq:sg_interp} and \eqref{eq:sg_quad}, are constructed in an
iterative way, relying on some heuristic criteria (called profit indicators in the following)
based on the values of the function currently being interpolated/integrated. 
The function provided to this end is called \mcode{adapt_sparse_grids} and a minimal working example of its use is provided in Listing \ref{adapt_grid}.

\begin{lstlisting}[label=adapt_grid,caption={{Basic creation of an adaptive sparse grid.}}]
f = @(y) exp(sum(y)); % @-function, takes as input a column vector for y and returns a scalar
                      % or column-vector
N = 2;
knots = @(n) knots_CC(n,0,1);
lev2knots = @lev2knots_doubling;
controls = struct('nested',true);|*\label{line:list_adapt_controls}*| % each field of this struct specifies an optional argument
                                  % to control the algorithm
Ad = adapt_sparse_grids(f,N,knots,lev2knots,[],controls);
\end{lstlisting}

The implemented adaptive algorithm for sparse grid generation is
an extension of the classical Gerstner--Griebel dimension-adaptive algorithm \cite{gerstner.griebel:adaptive}
(see \cite[Section 3.1]{piazzola.tamellini:SGK} for the mathematical background),
and can accommodate for non-nested knots, vector-valued functions, several profit definitions, and the so-called ``dimension-buffering''.
% \Lchange{(the two latter aspects are discussed below).
% Here we briefly recall just the basic structure of the algorithm and then mostly discuss 
% the various options of our implementation.}{}
In the following, we discuss the options available in the \SGK, % and refer to the above-mentioned references for the theoretical background.
which can be passed to the code in the typical Matlab way
by suitably setting the fields of a structure, i.e.\ \mcode{controls = ('option-name',<option-value>,..)}
and then passing such structure as input to  \mcode{adapt_sparse_grids}, cf. Listing \ref{adapt_grid}.
The available options are reported in Tab.\ \ref{tab:options}; we discuss the main ones below
and refer readers to the help of \mcode{adapt_sparse_grids} for a full discussion on the other ones.%\Cnote{riga 6,8,11 cambio carattere}

\begin{table}[tb]
	\centering
	\begin{tabular}{p{2.8cm}p{8cm}p{4.5cm}} 
		\hline
		\textbf{name}       & \textbf{short description} &  \textbf{default value}\\
		\hline
        \mcode{'nested'} 	& Specifies nestendess of knots & none (must always be set)\\
        \mcode{'max_pts'} 	& Maximum number of evaluations of $f$ allowed & $1000$ \\
		\mcode{'prof_tol'} 	& Stops algorithm when all profits are below this threshold & $10^{-14}$ \\
		\mcode{'paral'} 	& Controls interaction with Matlab parallel toolbox & \mcode{NaN} (i.e.\ serial computations)\\
		\mcode{'recycling'} & Can speed up computations when non-nested knots are used 	& \mcode{'priority_to_evaluations'}\\
		\mcode{'prof'} 		& Sets the profit to be used (see Tab.\ \ref{tab:profits}) & \mcode{'Linf/new_points'} \\
        \mcode{'op_vect'} 	& In case of vector-valued $f$, specifies the vector norm to be used
                              in the computation of the profits to account for the different components of $f$ & Euclidean norm \\
        \mcode{'pts_tol'} 	& Tolerance to detect identical knots when calling \mcode{reduce_sparse_grid} internally & 1e-14 \\ 
        \mcode{'pdf'} 		& Needed for certain profits (see Tab.\ \ref{tab:profits}) &  none (must be set if required by profit)\\
        \mcode{'var_buffer_size'} & Controls buffer size & $N$ (i.e., no buffer) \\
        \mcode{'plot'} 		& Plots current multi-index set and candidate set at each iteration ($N=2$ only) & \mcode{false}\\
		\hline
	\end{tabular}
	\caption{Main control options of the implementation of \mcode{adapt_sparse_grids} and their default value.}
	\label{tab:options}
\end{table}


% \Lchange{Let us recall briefly that the algorithm is guided by a so-called profit indicator that balances error reduction and additional
%   computational costs brought in by each multi-index. It is is computed by dividing the error contribution of each multi-index $\ii$
%   by the appropriate work definition (see \Ch{our paper, Section XXX}).
%   Table \ref{tab:profits} summarizes the discussion above and lists of the profits implemented in the \SGK, with 
% }{}
The algorithm iteratively explores the set of multi-indices and at each iteration adds one multi-index to the current multi-index set $\mathcal{I}$, choosing from a set of candidate multi-indices (the so-called \emph{reduced margin} of $\mathcal{I}$) the one with the largest profit.
  % More specifically, at each iteration the algorithm:
  % \begin{itemize}
  %  \item computes the so-called profit indicator for a set of candidate multi-indices
  %    (the so-called \emph{reduced margin} of $\mathcal{I}$, see \cite{nobile.eal:adaptive-lognormal,piazzola.tamellini:SGK});
  %  \item adds to the current multi-index set the candidate multi-index with the largest profit;
  %  \item updates the set of candidates and repeats, until a stop criterion is met.
  % \end{itemize}
  The profit indicator of a given multi-index $\ii$ quantifies the ``net contribution'' of $\ii$ to the sparse grid and is computed by dividing an ``error contribution'' estimator
  $\mathcal{E}_{\ii}$ (i.e., how much the sparse grid approximation / quadrature of $f$ would improve if $\ii$ was added to $\mathcal{I}$)
  by a ``work contribution'' $\mathcal{W}_{\ii}$ (i.e., how many new evaluations $f$ would be needed if $\ii$ was added to $\mathcal{I}$).
  Of course, several error indicators are possible, and the work contribution depends on whether the knots used are nested or not, which means that
  several profit definitions are possible.
  The profits implemented in the \SGK are listed in Tab.\ \ref{tab:profits}%
\footnote{Note that some profit indicators actually do not consider the work contribution and therefore are not profits, strictly speaking.},
  where:
  % \Ladd{Assuming for a moment that $f$ is scalar-valued for simplicity, i.e., $V=1$ (we'll generalize the formulas later on), the quantities in Tab.\ \ref{tab:profits}
  % are defined as:}
\begin{align}
	% \mathcal{E}^{\mathcal{Q}}_{\ii} & = \lvert \mathcal{Q}_{\mathcal{I} \cup \{\ii\}} - \mathcal{Q}_{\mathcal{I}} \rvert, \label{eq:err_quad}\\[4pt]
	% \mathcal{E}^{\mathcal{U},{\xi}}_{\ii} & = \max_{\mathbf{y}\in \mathcal{H}} \, \left( \lvert \mathcal{U}_{\mathcal{I} \cup \{\ii\}}(\mathbf{y}) - \mathcal{U}_{\mathcal{I}}(\mathbf{y})\rvert {\xi(\yy)} \right), \label{eq:err_u} \\
  \mathcal{E}^{\mathcal{Q}}_{\ii} & = \lVert \mathcal{Q}_{\mathcal{I} \cup \{\ii\}} - \mathcal{Q}_{\mathcal{I}} \rVert_V, \label{eq:err_quad}\\[4pt]
  \mathcal{E}^{\mathcal{U},{\xi}}_{\ii} & = \max_{\mathbf{y}\in \mathcal{H}} \,
      \left( \lVert \mathcal{U}_{\mathcal{I} \cup \{\ii\}}(\mathbf{y}) - \mathcal{U}_{\mathcal{I}}(\mathbf{y})\rVert_V {\xi(\yy)} \right), \label{eq:err_u} \\
  \mathcal{W}_{\ii} & = 
	\begin{cases}
		\prod_{n=1}^N \left(m(i_n) - m(i_n-1)\right) & \text{ for nested knots} \\[4pt] %\label{eq:work_nested}\\
		\prod_{n=1}^N m(i_n)                         & \text{ for non-nested knots} %\label{eq:work_non-nested} \\    
	\end{cases} 
\end{align}
with $\lVert \cdot \rVert_V$ the Euclidean norm in $\Rset^V$ (see below for other choices) and
\begin{align}
		\xi(\yy) & =
	\begin{cases}
		1                    & \text{for $\yy$ distributed as uniform random variables} \\
		\xi(\yy) = \rho(\yy) & \text{for the other supported random variables},
	\end{cases} \\
	\mathcal{H} & =
	\begin{cases}
		\mathcal{T}_{\mathcal{I} \cup \{\ii\}} \setminus  \mathcal{T}_{\mathcal{I}} & \text{ for nested knots, i.e. the new knots added by $\ii$, cf. Eq.\ (\ref{eq:sg_grid}) } \\[4pt] %\label{eq:work_nested}\\
		\mathcal{T}_{\ii} & \text{ for non-nested knots, i.e., the tensor grid generated by $\ii$. } %\label{eq:work_non-nested} \\    
	\end{cases} \label{eq:H-adaptive-grid-def}
\end{align}
% where $\xi(\yy)$ is either $1$ (for $\yy$ distributed as uniform random variables) or $\xi(\yy) = \rho(\yy)$ (for the other supported random variables)
% and the set $\mathcal{H} \in \Gamma$ is a suitable set of ``testing points'' (we refer to the discussion in \Ch{our paper, Section XXX} for the choice of these points).
% Note that the error contributions defined above in Eqs.\ \eqref{eq:err_quad} and \eqref{eq:err_u} actually require
% \Lchange{adding the multi-index to $\mathcal{I}$
% and then measuring the difference between the two corresponding grids in a suitable way: therefore, this algorithm is usually referred to as \emph{a-posteriori}.
% This is a sub-optimal procedure in the sense that a certain computational work is invested in assessing the profit of multi-indices which might
% then turn out to be ``useless''.}{}
% \Ladd{evaluating $f$ at the new points required by $\ii$.}

As already hinted, the profit to be used can be specified as a field of the structure array \mcode{controls}
(Line \ref{line:list_adapt_controls} of Listing \ref{adapt_grid}),
such as \mcode{controls = struct(..,'prof','Linf')}. 
The weight $\xi$ in Eq.\ \eqref{eq:err_u} can be provided as a function handle \mcode{controls = struct(..,'pdf',@(y) ..)},
% Note that we have presented Eqs. \eqref{eq:err_quad} and \eqref{eq:err_u} assuming that $f$ is scalar-valued ($V=1$) for simplicity,
 %  but the code actually implements their vector-valued counterpart
 % \begin{align}
 %   \mathcal{E}^{\mathcal{Q}}_{\ii} & = \lVert \mathcal{Q}_{\mathcal{I} \cup \{\ii\}} - \mathcal{Q}_{\mathcal{I}} \rVert_V, \label{eq:err_quad_V} \\
 %   \mathcal{E}^{\mathcal{U},{\xi}}_{\ii} & = \max_{\mathbf{y}\in \mathcal{H}} \, \left( \lVert \mathcal{U}_{\mathcal{I} \cup \{\ii\}}(\mathbf{y}) - \mathcal{U}_{\mathcal{I}}(\mathbf{y})\rVert_V {\xi(\yy)} \right),  \label{eq:err_u_V}
 % \end{align}
and the default norm $\lVert \cdot \rVert_V$ can also be changed (e.g. to an $\ell^p$ norm or a Mahalanobis distance),
by specifying a suitable \mcode{@}-function in the field \mcode{'op_vect'} of \mcode{controls}.
The formula for the work contribution and the testing set $\mathcal{H}$ are automatically selected based on the
field \mcode{'nested'} of the structure array, which can take value \mcode{<true/false>} and is the only mandatory field to be provided.


\begin{table}[tb]
	\centering
	\begin{tabular}{p{6cm}l} 
		\hline
		\textbf{profit name} & \textbf{Definition} \\
		\hline 
		\mcode{deltaint} & $\mathcal{E}^{\mathcal{Q}}$ \\
		\mcode{deltaint/new_points} & $\mathcal{E}^{\mathcal{Q}} / \mathcal{W}$ \\
		\mcode{Linf} & $\mathcal{E}^{\mathcal{U},{1}}$  \\
		\mcode{Linf/new_points} (default) & $\mathcal{E}^{\mathcal{U},{1}} / \mathcal{W}$ \\
		\mcode{weighted Linf} (requires \mcode{'pdf'} option to be set) & $\mathcal{E}^{\mathcal{U},\rho}$  \\
		\mcode{weighted Linf/new_points} (requires \mcode{'pdf'} option to be set) & $\mathcal{E}^{\mathcal{U},\rho} / \mathcal{W}$ \\
		\hline
	\end{tabular}
	\caption{Profits and corresponding names, cf. Eqs. \eqref{eq:err_quad}--\eqref{eq:H-adaptive-grid-def}.} 
	\label{tab:profits}
\end{table}

The adaptive algorithm terminates when one or more suitable stopping criterion is met.
Common choices are checking that the computational work or the profits of the multi-indices in the reduced margin are respectively above or below a certain tolerance. 
These termination criteria can be controlled by setting further fields in the \mcode{controls} structure array: 
\mcode{controls = struct(..,'max_pts',<value>,} \mcode{'prof_tol',<value>)}.

Finally, the so-called \emph{buffering} of dimensions %, see \cite{nobile.eal:adaptive-lognormal,piazzola.tamellini:SGK},
is a way to speed up the computations when $f$ depends on a large number of random variables,
$N \gg 1$, in which  case the set of candidates to be examined is very large.
In this scenario,
%\Lchange{if the user knows that the random variables $y_n$ are ordered decreasingly in terms of impact on the variability of $f$,}{}
% \footnote{This situation arises e.g. when $y_n$ are the random variables of a Karhunen--Lo\`eve
% expansion of a random field and $f(\yy)$ is a functional of such random field.}
it is possible to start the adaptive algorithm considering a reduced set of random variables, and gradually including the remaining ones as the algorithm evolves.
In particular, the algorithm is forced to consider at most $N_{buf}$ ``non-activated''/``buffered'' random variables
at each iteration, % instead% \Lchange{(see \cite{nobile.eal:adaptive-lognormal,piazzola.tamellini:SGK} for a precise definition),}{}
whereas the non-buffered version would always consider the whole set of random variables.
This behavior is obtained by setting to $N_{buf}$ the field \mcode{'var_buffer_size'} of the \mcode{controls} structure,
\mcode{controls = struct(..,'var_buffer_size',<value>)}. 
% i.e., of variables for which the algorithm has computed the profit of the first non-trivial multi-index
% without having added it to the multi-index set $\mathcal{I}$ yet.}%, \cite{nobile.eal:adaptive-lognormal,piazzola.tamellini:SGK},
% More specifically, calling $N_{cur}$ the number of random variables actually contributing the the sparse grids at the current iteration
% (i.e., only $N_{cur}$ columns of the matrix \mcode{I} contain entries larger than \mcode{1}),
% the \emph{buffered} version of the algorithm considers as candidates only multi-indices that propose new grid points in the first $N_{curr} + N_{buf}$ variables only
% (i.e., their entries beyond component $N_{cur} + N_{buf}$ are \mcode{1}); in other words the algorithm is forced to explore candidates with 
% at most $N_{buf}$ ``non-activated''/``buffered'' random variables.


%\Lchange{consider only a part of the random variables $\yy$ , see \Ch{our paper, Section XXX} can be activated
% by setting a field in the \mcode{controls} structure array, namely setting the number $N_{\textrm{buff}}$ of ``non-activated'' random variables 
% (``\emph{buffered} random variables'') as \mcode{controls = struct(..,'var_buffer_size',<value>)}.}{}
% \Lchange{The options discussed so far are summarized in Table \ref{tab:options} and we refer readers to the help of \mcode{adapt_sparse_grids} for a full list of options.}{}

The output of the function \mcode{adapt_sparse_grids} is a structure, which contains in separate fields
both the extended and the reduced version of the grid, as well as additional information such as the values of the function $f$ evaluated at the collocation knots,
the current index set, the reduced margin and others. 
\begin{lstlisting}
>> Ad
Ad = 

struct with fields:

N: 2
S: [1x7 struct]
Sr: [1x1 struct]
f_on_Sr: [1x257 double] % values of f at the sparse grid knots
nb_pts: 257 % nb. of knots in Sr 
nested: 1
nb_pts_visited: 257 % number of knots considered during the construction.
                    % For nested knots, this is equal to nb_pts; for non-nested knots,
                    % this will be larger than nb_pts, because some knots enter and then exit
                    % the grid when the corresponding idx exits from the combination technique.
num_evals: 257 % actual nb of evaluations of f required to build the sparse grid.
               % This is not necessarily equal to nb_pts_visited because for speed reasons
               % some function evaluations might be taken more than once (e.g. when
               % if evaluating f is faster than checking whether the point has been
               % already evaluated)
intf: 2.9525 % expected value of f
private: [1x1 struct] % contains more detailed info on the status of the adaptive algorithm
\end{lstlisting}


\subsubsection{Grid recycling}\label{sect:grid_recycling}
%\Cnote{Questo aspetto viene discusso anche nel paper, aggiungere riferimenti!}
We close this section pointing out a useful feature of the functions
%\mcode{create_sparse_grid}, \mcode{create_sparse_grid_multiidx_set}, and \mcode{adapt_sparse_grids}
to build sparse grids. For efficiency reasons, all these
functions can take as optional input another grid already available in memory and recycle as many computations as possible from there,
in terms of  e.g.\ generating the multi-index set,
computing the coefficients of the combination technique, and generating the tensor grids needed for the the \emph{extended} version of their storage.
The mechanisms implemented to this end are a bit different depending whether one is working with a-priori or adaptive sparse grids:
\begin{enumerate}
\item the commands \mcode{create_sparse_grid} and \mcode{create_sparse_grid_multiidx_set} take as input an \emph{extended} version of a previous grid:
\begin{lstlisting}[]
I = [1 1;
     1 2;
     2 1;
     3 1];
S = create_sparse_grid_multiidx_set(I,knots,lev2knots); 
I_new = [I;
		 1 3;
		 2 2;
		 4 1]; 
I_new = sortrows(I_new); % multi-indices must be sorted in lexicographic order
S_new = create_sparse_grid_multiidx_set(I_new,knots,lev2knots,S); 
\end{lstlisting}
\item \mcode{adapt_sparse_grids} takes as input the result of a previous computation, to resume the computation where the previous one stopped:
\begin{lstlisting}
% stop the adaptive algorithm when profits < 1e-5 
controls = struct('nested',true,'prof_tol',1e-5);  
Ad = adapt_sparse_grid(f,N,knots,lev2knots,[],controls);
% run the algorithm up to default tolerance
controls_next = struct('nested',true); % default tolerance 1e-14
Next = adapt_sparse_grid(f,N,knots,lev2knots,Ad,controls_next);
\end{lstlisting}
\item When the new grid differs from the previous one by just one multi-index, the code can be further optimized, and an ad-hoc function in this case is available:
    %(this happens e.g.\ while running the adaptive algorithm, where multi-indices are tested adding them one by one to $\mathcal{I}$):
\begin{lstlisting}
I_in = [1 1;
		1 2;
		2 1;
		3 1];
S_in = create_sparse_grid_multiidx_set(I_in,knots,lev2knots); 
coeff_in = combination_technique(I_in); 
new_idx = [4 1];
S_new = create_sparse_grid_add_multiidx(new_idx,S_in,I_in,coeff_in,knots,lev2knots);  
\end{lstlisting}
\end{enumerate}

\section{Operating on sparse grids}\label{sect:main}
After having discussed how to generate a sparse grid, the aim of this section is to present the main functionalities of the \SGK.
In Sect.\ \ref{sect:main_functions} we first discuss basic tasks,
i.e.\ evaluation, quadrature and interpolation of the function $f$, as well as plotting of the sparse grid approximation.
The following Sect.\ \ref{sect:enhancing_perf} covers
some advanced features that can be optionally activated to save computational time (evaluation recycling, parallelization).
We then move to tools to manipulate the sparse grid approximation:
Sect.\ \ref{sect:derivatives} covers computation of gradients and Hessians,
and Sect.\ \ref{sec:PCE_and_sobol} computation of Sobol indices by conversion to polynomial chaos expansion.
Most of these functions work for vector-valued $f:\Gamma \subset \Rset^N \rightarrow \Rset^V$, in which case the function is applied component-wise to $f$.
Finally, in Sect.\ \ref{sect:interface} we discuss how to interface the \SGK with external software, either by saving grids on file
or using the \emph{UM-Bridge} protocol.

\subsection{Basic operations: function evaluation, quadrature, interpolation, and plotting}\label{sect:main_functions}\label{sect:sg_operations}
Once a sparse grid is built, the basic operations of interest are: 
evaluating a function $f$ for each point of the grid, $f(\yy_j)$, $\forall \yy_j \in \mathcal{T}_{\mathcal{I}}$,
approximating the integral (expected value) $\int_\Gamma f(\yy) \rho(\yy) \textrm{d}\yy$, evaluating and plotting
the sparse grid approximation $\mathcal{U}_{\mathcal{I}}(\yy)$ for $\yy \in \Gamma$;
cf. Eqs.\ \eqref{eq:sg_interp}, \eqref{eq:sg_quad}, and (\ref{eq:sg_grid}). The corresponding functions of the \SGK are: 
\begin{itemize}
	\item \mcode{evaluate_on_sparse_grid}, that evaluates the function $f$ at the sparse grid knots; 
	\item \mcode{quadrature_on_sparse_grid}, that computes integrals of $f$ by quadrature formulas collocated at the sparse grid knots, cf. Eq.\ \eqref{eq:sg_quad};
	\item \mcode{interpolate_on_sparse_grid}, that evaluates the sparse grids approximation as defined in Eq.\ \eqref{eq:sg_interp}
          %\Lchange{(the standard form of Lagrange polynomials is implemented to this end in the \SGK)}{};
    \item \mcode{plot_sparse_grids_interpolant}, that plots such sparse grids approximation. %  (different visualization formats are used for $N=2,N=3,N>3$).
\end{itemize} 
We illustrate them with the help of the following snippets. % , where we consider a Smolyak-type grid of Clenshaw--Curtis points 
% with level of approximation $w=3$ (cf.\ Listing \ref{lst:smolyak_grid}).
First, the values of $f$ at the sparse grid knots are obtained as follows: 
\begin{lstlisting}[backgroundcolor = \color{lightgray}]
f = @(y) exp(sum(y)); 
% S as in Listing 3
Sr = reduce_sparse_grid(S); 
f_on_Sr = evaluate_on_sparse_grid(f,Sr); 
\end{lstlisting}
We plot the result in Fig.\ \ref{fig:sg_val_interp}a. 
Once the values of $f$ at the sparse grid knots are available we can
compute the approximated value of the integral of $f$ (see Eq.\ \eqref{eq:sg_quad}), as well as
construct and evaluate the sparse grid approximation defined in Eq.\ \eqref{eq:sg_interp}. 
The snippet below shows how to compute approximated integrals of $f$ and of $f^2$:
\begin{lstlisting}
q = quadrature_on_sparse_grid(f_on_Sr,Sr);
q2= quadrature_on_sparse_grid(f_on_Sr.^2,Sr); 
\end{lstlisting}
%It is also possible to condense the calls of \mcode{evaluate_on_sparse_grids} and \mcode{quadrature_on_sparse_grid} in a single call
%(note that the first argument this time is \mcode{f}, \mcode{@}-function):
%\begin{lstlisting}
%[q,f_on_Sr] = quadrature_on_sparse_grid(f,Sr);
%\end{lstlisting}\Cnote{tolgo del tutto?}
% \Ladd{Alternatively, if the values \mcode{f_on_Sr} of $f$ at the points of the reduced sparse grid are available, the previous command can be modified to \mcode{quadrature_on_sparse_grid(f_on_Sr,Sr)}. 
% This instruction is particularly useful for the computation of higher order integrals of $f$. E.g.\ the second integral (i.e.\ $\int_{\Gamma} f^2$) is estimated calling
% \mcode{quadrature_on_sparse_grid(f_on_Sr.^2,Sr)}, where the first argument is the vector of the second powers of the values of $f$ at the grid points. }{}
Finally, the following piece of code shows how to evaluate the sparse grid approximation at a uniform cartesian grid of $15 \times 15$ points.
The resulting surface is reported in Fig.\ \ref{fig:sg_val_interp}b. 
Note that for this operation both the \emph{extended} and \emph{reduced} versions of the sparse grid are needed
(see \cite[Section 4.4]{piazzola.tamellini:SGK} for a discussion on why this is the case).
% This is because in pratice
% the implementation works tensor grid by tensor grid, creating the Lagrange interpolants of $f$ on each tensor grid and then finally summing up everything.
% \Ladd{To this end, note that the values of $f$ are stored in a vector \mcode{f_on_Sr} whose length is the number of uniqued knots, \mcode{Sr.knots},
%   therefore in a compressed format.
%   To compute the Lagrange interpolant on each tensor grid, one then needs to know where the value of $f$ at each node of each tensor grid is stored in \mcode{f_on_Sr},
%   which is where we need to use the vectors \mcode{Sr.m} and \mcode{Sr.n}.
% }
\begin{lstlisting}[backgroundcolor = \color{lightgray}]
% building the cartesian grid of 15x15 equispaced points
y = linspace(0,1,15);
[Y1,Y2] = meshgrid(y,y);
% rearrange the points such that each point is a column 
eval_points = [Y1(:)';Y2(:)']; % matrix of dim. 2x15
% S, Sr and f_on_Sr as above  
f_vals = interpolate_on_sparse_grid(S,Sr,f_on_Sr,eval_points); 
surf(Y1,Y2,reshape(f_vals,15,15))
\end{lstlisting}
The snippet above is actually very close to the implementation for the case $N=2$ of the last function mentioned at the beginning of this section, i.e.\
\mcode{plot_sparse_grids_interpolant}, that plots the sparse grids approximation. For $N=3$, this function would instead plot a number of
contour lines colored according to the value of the interpolant, stacked over the same axis; finally, when $N>3$ a number of
bi-dimensional cuts of the domain $\Gamma$ are considered, and for each of them the surface (i.e., the plot for $N=2$) will be generated, keeping all
other $y_n$ constant to their mid-value. Examples for cases $N=3$ and $N=4$ are reported in the listing below, and the corresponding plots are shown
in Fig.\ \ref{fig:plot_interpolant_N3} and \ref{fig:plot_interpolant_N4}, respectively.  
We refer the readers to the help of \mcode{plot_sparse_grids_interpolant} for the full description of the optional controls to generate plots like these.
Of course, the \SGK contains also functions to plot the knots of a sparse grid: \mcode{plot_sparse_grid} (that we have already used multiple times
  in previous snippets) and \mcode{plot3_sparse_grid} (see snippet below). The former can be used to plot two-dimensional sparse grids, or
  two-dimensional projections of a higher-dimensional sparse grid; the latter can be used instead to plot three-dimensional sparse grids, or three-dimensional projections.
\begin{lstlisting}
N = 3; 
f = @(x) exp(sum(x));
% S as in Listing 3 with N = 3, Sr its reduced version
plot3_sparse_grid(S)
f_on_Sr = evaluate_on_sparse_grid(f,Sr); 
domain = [0 0 0; 1 1 1]; % domain where to plot 
plot_sparse_grids_interpolant(S,Sr,domain,f_on_Sr,'nb_contourfs',5,'nb_countourf_lines',10);

N = 4; 
f = @(x) exp(x(1,:)+0.5*x(2,:)+1.5*x(3,:)+2*x(4,:))
% S as in Listing 3 with N=4, Sr its reduced version
f_on_Sr = evaluate_on_sparse_grid(f,Sr); 
domain = [0 0 0 0; 1 1 1 1]; % domain where to plot
plot_sparse_grids_interpolant(S,Sr,domain,f_on_Sr,'two_dim_cuts',[1 2 3 4 1 4])
% cut for (y1,y2),(y3,y4),(y1,y4)
\end{lstlisting}

\begin{figure}[tp]
	\centering
	\subfigure[Values of $f$ at the sparse grid knots]{\includegraphics[width=0.35\textwidth]{sg_evals}} \hspace{2em}
	\subfigure[Sparse grid approximation of $f$ evaluated at the points of a uniform cartesian grid(the values are marked in red)]{\includegraphics[width=0.35\textwidth]{sg_interp}}
	\caption{Evaluations of $f(\yy)=\exp(y_1+y_2)$ at the sparse grid knots and corresponding sparse grid approximation.}
	\label{fig:sg_val_interp}
\end{figure}

\begin{figure}[tp]
  \centering
  \subfigure[Sparse grid]{\includegraphics[width=0.35\textwidth]{sg_grid_N_3}} \hspace{2em}
  \subfigure[Sparse grid approximation]{\includegraphics[width=0.35\textwidth]{sg_interp_N_3}}
  \caption{Sparse grid and corresponding approximation of $f(\yy) = \exp(y_1+y_2+y_3)$.}
  \label{fig:plot_interpolant_N3}
\end{figure}

\begin{figure}[tp]
	\centering
	\subfigure[Cut for $(y_1,y_2)$]{\includegraphics[width=0.31\textwidth]{sg_interp_N_4_1} }
	\subfigure[Cut for $(y_3,y_4)$]{\includegraphics[width=0.31\textwidth]{sg_interp_N_4_2} }
	\subfigure[Cut for $(y_1,y_4)$]{\includegraphics[width=0.31\textwidth]{sg_interp_N_4_3} }
	\caption{Sparse grid approximation of $f(\yy) = \exp(y_1+\frac{1}{2} y_2+ \frac{3}{2}y_3+2y_4)$.}
	\label{fig:plot_interpolant_N4}
\end{figure}

%\end{example}

\subsection{Enhancing computational performance}\label{sect:enhancing_perf}
%The functions \mcode{evaluate_on_sparse_grids} and \mcode{quadrature_on_sparse_grids} are in practice wrappers for
%a) looping through the points of a sparse grid and calling the evaluation of $f$ and
%b) computing the sum of the values of $f$, each weighted by the corresponding quadrature weight.
%These wrappers are also convenient since they implement a couple of advanced features that can be used to
%improve the computational efficiency: evaluation recycling and parallelization.
The function \mcode{evaluate_on_sparse_grids} is in practice a wrapper for
looping through the knots of a sparse grid and calling the evaluation of $f$. It is convenient especially because it implements a couple of advanced features that can be used to improve the computational efficiency: evaluation recycling and parallelization. We discuss them below.

\subsubsection{Evaluation recycling}
When multiple grids have to be built and the function $f$ evaluated at the corresponding knots
(for instance, when the user would like to refine the current sparse grid approximation of $f$
adding more collocation knots to the grid, or when several sparse grids are being compared),
significant computational savings can be achieved by recycling the evaluations of $f$ that have been already performed.
This can be obtained by passing to \mcode{evaluate_on_sparse_grids}
the previous grids and the corresponding evaluations as additional inputs,
as shown in the next listing where we generate a sequence of grids with increasing $w$ in a for loop.

\begin{lstlisting}[]
N = 2; 
f = @(y) exp(sum(y)); 
knots = @(n) knots_CC(n,0,1);
lev2knots = @lev2knots_doubling;
rule = @(ii) sum(ii-1);
% consider a sequence of grids with increasing level
w_vec = 1:6; 
S_old = []; % initialize the grid 
Sr_old = []; % initialize the reduced grid
evals_old = []; % initialize the set of evaluations
for w = w_vec
  % recycle tensor grids from S_old
  S = create_sparse_grid(N,w,knots,lev2knots,rule,S_old); 
  Sr = reduce_sparse_grid(S); 
  % recycle evaluations on S_old
  f_evals = evaluate_on_sparse_grid(f,S,Sr,evals_old,S_old,Sr_old);
  ..
  % do something with f_evals
  ..
  % then update the containers
  S_old = S; 
  Sr_old = Sr; 
  evals_old = f_evals; 
end
\end{lstlisting}
%
Note that it is also possible to pass as input a generic list of points (i.e.\ not a sparse grid): 
\begin{lstlisting}[]
f_evals = evaluate_on_sparse_grid(f,S,Sr,evals_old,[],M)
\end{lstlisting}
 where \mcode{M} is a matrix containing the list of points at which the
  evaluations of $f$ are available, and \mcode{evals_old} contains such evaluations.
  As discussed in \cite[Section 4.1]{piazzola.tamellini:SGK}, the computational overhead to
  detect the evaluations that can be recycled is larger in this case than in the previous snippet,
  where the evaluations are recycled from another sparse grid.

\subsubsection{Parallelization of evaluations by Matlab \mcode{parpool}}\label{sect:parallel}
The function \mcode{evaluate_on_sparse_grids} 
also acts as wrapper to calls of the Matlab parallel toolbox construct \mcode{parfor},
to speed-up the evaluations of $f$ by running the evaluations on multiple cores.
This functionality is activated by first opening a Matlab parallel session
(\mcode{parpool} command) and then specifying one further input in the call to the function:
\begin{lstlisting}[]
f_evals =   evaluate_on_sparse_grid(f,S,Sr,evals_old,S_old,Sr_old,paral);
\end{lstlisting}
where \mcode{Sr,evals_old,S_old,Sr_old} can be set to \mcode{[]} if no grid / point recycling is required.
Here \mcode{paral} is an integer number that specifies the minimum number of evaluations of $f$ above which \mcode{parfor}
should replace the regular \mcode{for} when looping over the knots of the sparse grid. This apparently cumbersome
call is due to the fact that communication between workers of a \mcode{parpool} takes some time. Therefore,
unless a sufficient number of evaluations of $f$ are requested, serial evaluation might be faster,
depending on the time it takes to perform one evaluation of $f$. The default value of \mcode{paral} is \mcode{NaN},
which means that no parallel is used.
Note that \mcode{evaluate_on_sparse_grid} will not open a \mcode{parpool} session, but will check if one is open and throw an error if not.

\begin{remark}
Note that recycling and paralllelization of evalutions are available also for \mcode{quadrature_on_sparse_grid}. Indeed, the quadrature function can also take as input a \mcode{@}-function (instead of the evaluations of $f$ as explained in Sect.\ \ref{sect:sg_operations})
\begin{lstlisting}
[q,f_on_Sr] = quadrature_on_sparse_grid(f,Sr);
\end{lstlisting}	
% \Cchange{In this way the calls of \mcode{evaluate_on_sparse_grids} and \mcode{quadrature_on_sparse_grid} are condensed in a single call, and all the functionalities of the former are inherited by the latter.}{
  In this way, the call to \mcode{quadrature_on_sparse_grid} embeds the one to  \mcode{evaluate_on_sparse_grids} and, as such, all the functionalities of the latter are inherited by the former.
\end{remark}

\subsection{Gradients and Hessian}\label{sect:derivatives}

Computing gradients and Hessians of the sparse grids approximation of $f$ can be useful in applications, such as the inverse UQ problem
discussed in Sect.\ \ref{sect:inversion}, optimization or local sensitivity analysis studies. To this end, the \SGK provides
the functions \mcode{derive_sparse_grid} and \mcode{hessian_sparse_grid}, that respectively
compute gradients and Hessians of the sparse grid approximation of a \emph{scalar-valued} function $f: \mathbb{R}^N \rightarrow \mathbb{R}$
by centered finite differences schemes; gradients and Hessians of vector-valued functions must be computed component-wise calling repeatedly the functions
\mcode{derive_sparse_grid} and \mcode{hessian_sparse_grid}.
More specifically, \mcode{derive_sparse_grid} returns the gradient of $f$ evaluated at \emph{multiple points} as a matrix, each column being the gradient in one point;
\mcode{hessian_sparse_grid} conversely computes the Hessian matrix at a \emph{single point}. The step-size $h$ of the computation along each variable $y_k$ is defaulted
to $(b-a)/10^5$ (other values can be specified if needed), where $a,b$ are the boundaries of $\Gamma$ along $y_k$ (or of the subset of $\Gamma_k$ where derivatives are needed, in case of unbounded domains).

\subsection{Polynomial chaos expansion and Sobol indices computation}\label{sec:PCE_and_sobol}


\begin{table}[t]
	\centering
	\begin{tabular}{lll}
		\hline
		\textbf{name} 	& \textbf{orthonormal pdf}  	&  \textbf{function} \\
		\hline 
		Legendre 		& uniform  			& \mcode{lege_eval_multidim}   	\\
		Hermite 		& normal 			& \mcode{herm_eval_multidim} 	\\
		Laguerre 		& exponential 			& \mcode{lagu_eval_multidim} 	\\
		generalized Laguerre & gamma 			& \mcode{generalized_lagu_eval_multidim} 	\\
          probabilistic Jacobi\tablefootnote{These polynomials are slightly different from the classical Jacobi polynomials:
          the former are orthonormal with respect to the beta pdf, cf. Tab.\ \ref{tab:pdf}, whereas the latter
          are orthonormal with respect to the weight function $w(y) = (y-a)^{\beta}(b-y)^{\alpha}$ -- note the switch in the
          role of the parameters $\alpha,\beta$.}		   
		               & beta 				& \mcode{jacobi_prob_eval_multidim}	\\
		Chebyshev ($1^{\textrm{st}}$ kind) & Chebyshev	& \mcode{cheb_eval_multidim}   	\\
		\hline
	\end{tabular}
	\caption{Orthonormal polynomials, corresponding pdfs, and function name. }
	\label{tab:orthopol}
\end{table}


The generalized Polynomial Chaos Expansion (gPCE) %\cite{ghanem:UQbook}
is the expansion of a function $f$ over multi-variate $\rho$-orthonormal polynomials, that in practice gets truncated as follows: 
\[
  f(\yy) \approx \sum_{\pp \in \Lambda} d_{\pp} \mathcal{P}_{\pp}(\yy),
\]
where $\Lambda \subset \Nset^N$ is a multi-index set, %(note that here multi-indices can have entries with value zero),
and $\mathcal{P}_{\pp} = \prod_{n=1}^N P_{p_n}(y_n)$ are products of $N$ univariate $\rho_n$-orthonormal polynomials of degree $p_n$.
%An example of a situation when having the gPCE expansion of $f$ is helpful
%is the computation of the Sobol indices for global sensitivity analysis of $f$:
%an efficient way to compute such Sobol indices is indeed to perform some algebraic manipulations on the coefficients of the gPCE, $d_{\pp}$, see \cite{feal:compgeo}.   
The \SGK provides functions to evaluate a number of different orthonormal polynomials %$\mathcal{P}_{\pp}$ 
in the folder 
\medskip
\dirtree{%
.1 tools.
.2 polynomials functions.
}
\medskip
\noindent The available polynomials with the corresponding orthonormal pdf and the associated function names are listed in Tab.\ \ref{tab:orthopol}.
%\Lchange{The evaluation of the orthonormal polynomials is obtained by means of the corresponding three-term recursive formulas, see \cite{gautschi:orthogonal}.}{}
%


%\Lchange{These functions implement the point-wise evaluation of orthogonal polynomials by the three-term recursive formula, cf. e.g. \cite{gautschi:orthogonal}.}{}
%\Cchange{All these functions have the same interface: they take as input the list of points where their evaluation is requested
%(stored as columns of a matrix as usual), a multi-index $\pp$ denoting their degree along each direction $y_1,y_2,\ldots,y_N$,
%and one or more shape parameters.}{}
Thus, a gPCE is completely determined upon prescribing a multi-index set $\Lambda$ %\Cchange{(stored as rows of a matrix as usual)}{}
and the vector containing the corresponding expansion coefficients $d_{\pp}$:
\begin{itemize}
\item the multi-index set $\Lambda$ can be constructed with the same procedures detailed in Sect.\ \ref{sect:multiidx-set}:
  the only difference is that now the entries of each multi-index indicate a polynomial degree, therefore entries with value zero are allowed.
  This can be obtained e.g.\ by means of the option \mcode{base=0} in the function \mcode{multiidx_gen}.
\begin{lstlisting}
N = 2;
rule = @(ii) sum(ii);
w = 3;
base = 0;
Lambda = multiidx_gen(N,rule,w,base);
 \end{lstlisting}
\item The coefficients $d_{\pp}$ can be computed in several ways, e.g.\ by quadrature,  %\cite{xiu:compute.gPC.coeff.with.sc},
  least squares fitting %\cite{sudret:adaptive.PCE.with.reg},
  or compressed sensing approaches. % \cite{hampton.doostan:compressed}.
  The strategy provided by the \SGK is briefly described below.
\end{itemize}
%
\begin{figure}[tb]
	\centering
	\subfigure[Sparse grid multi-index set $\mathcal{I}$]{\includegraphics[width=0.26\textwidth]{PCE_I}}\hspace{2em}
	\subfigure[PCE multi-index set $\Lambda$]{\includegraphics[width=0.26\textwidth]{PCE_Lambda}}
	\caption{Sparse grid multi-index set and corresponding PCE multi-index set.}
	\label{fig:PCE_multiidx}
\end{figure}
%
Once the multi-index set is defined and gPCE coefficients are available,
the gPCE can be evaluated in a straightforward way as follows: %\Cnote{non si possono usare intervalli diversi nelle varie direzioni vero?} 
\begin{lstlisting}
PCE_coeffs = [..]; % a vector of coefficients obtained e.g. by least square or quadrature
eval_points = rand(N,10); % points where to evaluate the gPCE of f
PCE_vals = zeros(1,size(eval_points,2));
for i = 1:length(PCE_coeffs)
	PCE_vals = PCE_vals+PCE_coeffs(i)*lege_eval_multidim(eval_points,Lambda(i,:),0,1);
    % 0,1 are shape param and indicate that the Legendre polynomials are defined over [0,1]^N
end
\end{lstlisting}

Coming to the computation of the gPCE coefficients, the \SGK provides a function to compute them given the evaluations of $f$
over a sparse grid. Such function is called \mcode{convert_to_modal} and it supports transformation to all polynomials listed in Tab.\ \ref{tab:orthopol},
and, roughly speaking, works by converting the sparse-grid surrogate model into its equivalent gPCE by performing a change of polynomial basis.
%\Lchange{(i.e., the actual approximation of $f$ does not change switching from the sparse grid to the gPCE representation),}{}
%see \cite{feal:compgeo,piazzola.tamellini:SGK}.
%\Lchange{The algorithm that performs the conversion is based on a change of basis from the Lagrange polynomials to a $\rho$-orthogonal basis,
%which is performed by solving a Vandermonde-like linear system for each tensor grid in the sparse grid, see \cite{feal:compgeo}.}{}
% Note that the multi-index set of the PCE, $\Lambda$, is completely determined by the choice of the multi-index set of the sparse grid from which
% the conversion procedure begins. 
%\Lchange{We remark that the resulting gPCE approximation of $f$ is actually identical to the original sparse grid approximation:  
%it is the same polynomial approximation of $f$, just expressed over a different basis.}{}
The function \mcode{convert_to_modal} returns a vector containing the gPCE coefficients \mcode{PCE_coeffs} and a matrix \mcode{Lambda} containing the multi-index set of the gPCE:
\begin{lstlisting}
f = @(y) exp(sum(y)); 
w = 3;
base = 1; 
knots = @(n) knots_CC(n,0,1);
lev2knots = @lev2knots_doubling;
rule = @(ii) sum(ii-1);
I = multiidx_gen(N,rule,w,base);
S = create_sparse_grid_multiidx_set(I,knots,lev2knots);
Sr = reduce_sparse_grid(S); 
f_on_Sr = evaluate_on_sparse_grid(f,Sr); 
domain = [0 0; 1 1]; 
[PCE_coeffs,Lambda] = convert_to_modal(S,Sr,f_on_Sr,domain,'legendre');
\end{lstlisting}

Note that the multi-index set of the PCE is completely determined by the choices of the level-to-knots
function and of the multi-index set of the sparse grid from which the conversion procedure begins.
In Fig.\ \ref{fig:PCE_multiidx} we plot both multi-index sets from the snippet above. 
% : the sparse grids multi-index set \mcode{I} and the resulting PCE multi-index set \mcode{Lambda}).}
%\Lchange{the multi-index set $\mathcal{I}$ in conjunction with the level-to-knots function implies the shape of $\Lambda$, see \cite{feal:compgeo}.}{} 
% dictates the degree of the polynomial approximation in each direction, 
% which 
% in turn is determined by the number of knots prescribed by the multi-indices in the sparse grid multi-index set $\mathcal{I}$. 
  
The conversion to gPCE is useful e.g.\ to compute the indices of the Sobol decomposition of $f$: % \cite{sudret:sobol}:
to this end, the \SGK provides a wrapper function \mcode{compute_sobol_indices_from_sparse_grid} which calls 
\mcode{convert_to_modal} and performs some algebraic manipulations of the gPCE coefficients of $f$ to compute the Sobol indices of $f$;
%(see \cite{feal:compgeo});
we give an example of its usage in Sect.\ \ref{sect:forward}.

\subsection{Interfacing the \SGK with other software}\label{sect:interface}

Interfacing the \SGK with other software implementing the evaluation of $f$ can be done in (at least) two ways: %\Lnote{add this to intro and to summary of section 4} %
by saving sparse grids on file and then using external tools to evaluate $f$ at each point, or through the interface
provided by the software UM-Bridge \cite{Seelinger2023:umbridge}, available at \url{https://um-bridge-benchmarks.readthedocs.io/en/docs/}.

\subsubsection{Saving grid on file}
Saving a grid (reduced format) on file can be obtained by the command
\mcode{export_sparse_grid_to_file(Sr,filename)},
which generates a ASCII file (default name \mcode{points.dat}) that has the following format
\begin{lstlisting}[numbers=none]
<Nb of points of Sr>  N
<coord 1 of point 1> <coord 2 of point 1> <coord 3 of point 1> ..
<coord 1 of point 2> <coord 2 of point 2> <coord 3 of point 2> ..
..
\end{lstlisting}
Optionally, one additional column with the quadrature weight of each collocation point can be added.

\subsubsection{Using the UM-Bridge interface}
The software UM-Bridge provides a means to interfacing UQ software 
with complex software for evaluating $f(\yy)$ (e.g.\ when $f(\yy)$ is the numerical solution of a PDE)
by providing a standardized protocol between two layers:
\begin{enumerate}
\item the first one (\emph{client} side) converts requests of evaluations of $f$ at collocation points
  from, e.g., the \SGK, such as those occurring when \mcode{evaluate_on_sparse_grids} is called, into HTTP messages;
  \item the second one (\emph{server} side) converts back the client requests to actual calls to the software that implements the evaluation of $f(\yy)$. 
\end{enumerate}
The fact that communication is via HTTP messages opens the way to several possibilities on the server side: the software implementing
the evaluation of $f(\yy)$ can be an executable running either on the same machine of the client, or 
on a remote server. %\footnote{In practice containerization of the executables through Docker (\url{https://www.docker.com/}) is a  }.
UM-Bridge clients are currently available in Python, C++, Matlab, R, while servers are available only in Python and C++.
In particular, the UM-Bridge Matlab client is fully compatible with the \SGK. For instance, the following snippet 
evaluates over a sparse grid the function $f(\yy)$ provided by a service running on a remote server:
\begin{lstlisting}
% uri of the service running the server
uri = 'http://xxx.xxx.xx.xxx';
% HTTPModel is an object provided by the UM-Bridge Matlab client.     
model = HTTPModel(uri,'forward');
% model.evaluate(y) sends a request to the server to evaluate the model at y.
% Wrap it in an @-function
f = @(y) model.evaluate(y);
N=2;
w=5;
[S,Sr]=create_sparse_grid_quick_preset(N,w);
f_evals = evaluate_on_sparse_grid(f,Sr); 
\end{lstlisting}
Note that once the call to \mcode{HTTPModel.evaluate} is encapsulated in an anonymous function, UM-Bridge is fully transparent
to \SGK, and it would be e.g.\ possible to enable parallel evaluations of \mcode{f} as discussed in Sect.\ \ref{sect:parallel},
without any change to the snippet above, beside activating a \mcode{parpool} session and passing a value for \mcode{paral} to \mcode{evaluate_on_sparse_grid}
(of course, the server machine must be able to process parallel requests).
% The paper \cite{seelinger.eal:kubernetes} shows a more complex example of combining the \SGK with UM-Bridge to solve
% a naval engineering problem, whose solver runs remotely in parallel on the Google Cloud Platform.
 

\section{Working example}\label{sect:example}

The aim of this section is to give a comprehensive overview on the functionalities of the \SGK for forward and inverse UQ problems.
To this end we consider the following PDE:
\begin{equation}\label{eq:PDE}
\begin{cases}
-\partial_x(a(x,\yy) \partial_xu(x,\yy)) = 1, \quad \text{ for }x\in (0,1) \\  
u(0, \cdot) = u(1, \cdot) = 0 \\
\end{cases}
\end{equation}
with piecewise constant diffusion coefficient $a(x,\yy): [0,1] \times \Gamma \rightarrow \mathbb{R}$, $\Gamma = [-\sqrt{3}, \sqrt{3}]^N$ 
of the following form 
\begin{equation}\label{eq:unif_rf}
a(x,\yy) = \mu + \sum_{n=1}^N s_n\,y_n \chi_{[\bar{x}_{n-1}, \bar{x}_n]}(x), 
\end{equation}
where $\mu = 1$, $ \bar{x}_n = \frac{n}{N} $ for $0\le n \le N$, $y_n$ are independent uniform random variables $y_n \sim \mathcal{U}(-\sqrt{3}, \sqrt{3})$
with zero mean and unit variance, and $s_n>0$ such that $\mu - \sqrt{3} s_n> 0$.
 


\subsection{Forward UQ analysis}\label{sect:forward}
We focus first on the forward UQ analysis, i.e.\  the study of the propagation of the randomness in the diffusion coefficient $a(x,\yy)$
to a functional of the solution of Eq.\ \eqref{eq:PDE}, often called \textit{quantity of interest}, that we denote in the following by $I(\yy)$. 
In this example we consider as quantity of interest the spatial integral of the solution $u$, i.e. 
\begin{equation}\label{eq:QoI}
I(\yy) = \int_0^1 u(x,\yy) \,\mathrm{d}x, 
\end{equation}
and aim to estimate its expected value $\mathbb{E}[I] = \int_{\Gamma} I(\yy) \rho(\yy) \dd \yy$, its variance $\text{Var}[I] = \mathbb{E}[I^2] -  \mathbb{E}[I]^2$, and its pdf. 
In the following we choose $N=2$ (which allows plotting the sparse grid approximation as a surf plot),
and set the coefficients $s_1$ and $s_2$ in Eq.\ \eqref{eq:unif_rf} to  0.5 and 0.1, respectively. 

Both the estimation of the moments and of the pdf of $I$ require evaluations of the quantity of interest at
the sparse grids knots. %specific instances of $\yy$. \Lnote{stiamo valutando la PDE anche su ptunti random?}
It is then convenient to define a wrapper for the call to the PDE solver and the estimation of $I$.
Note that we use here a piece-wise linear finite element solver using 200 elements, but of course any other solver can be used.
\begin{lstlisting}
mu = 1; %  mean of the diffusion coefficient, cf. Eq. |*(\ref{eq:unif_rf})*|
s = [0.5, 0.1]; % s_1, s_2 in Eq. |*(\ref{eq:unif_rf})*|
PDE_rhs = @(x) ones(size(x)); % PDE right-hand side, cf. Eq. |*(\ref{eq:PDE})*|
N_el = 200; % number of FEM elements
xx = linspace(0,1,N_el+1); % discretization of the physical domain 
I = @(y) QoI(xx,y,mu,s,PDE_rhs); 
\end{lstlisting}

To perform the UQ analysis we choose to work with Smolyak grids of Clenshaw--Curtis knots, since the random variables $y_n$ are uniform.
As the level of approximation $w$ determines the accuracy of the sparse grid approximation and quadrature, we test $w=2,\ldots,8$
and compare the corresponding estimates of the expected value with respect to a very accurate result obtained with $w=10$ (see Fig.\ \ref{fig:forward_example}a).
\begin{lstlisting}
N = 2; 
knots = @(n) knots_CC(n,-sqrt(3),sqrt(3));
lev2knots = @lev2knots_doubling;
rule = @(ii) sum(ii-1);
% initializations for recycling 
S_old = []; Sr_old = []; evals_old = []; 
for w = 2:8 % testing different values of w
	S = create_sparse_grid(N,w,knots,lev2knots,rule,S_old);
	Sr = reduce_sparse_grid(S);
	[exp_I,evals] = quadrature_on_sparse_grid(I,S,Sr,evals_old,S_old,Sr_old);
	S_old = S; Sr_old = Sr;  evals_old = evals; 
end
\end{lstlisting}
The plot shows that $w=4$ gives already very accurate results in terms of expected value, and we expect
errors in the other quantities (variance, pdf) to be roughly of the same size, due to the ``simple'' structure of the problem at hand.
%\Lchange{a similar convergence plot for the error in the variance and in the sparse grid approximation, due to the ``simple'' structure of the problem at hand. }{}
Hence, for the following numerical results we consider $w=4$. The expected value is estimated to
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{lstlisting}
>> exp_I
exp_I =

0.0935
\end{lstlisting}
For the computation of the variance of $I$ we proceed as follows 
\begin{lstlisting}
I_on_Sr = evaluate_on_sparse_grid(I,Sr); 
int_I2 = quadrature_on_sparse_grid(I_on_Sr.^2,Sr); % computing E[I^2]
var_I = int_I2-exp_I^2;
\end{lstlisting}
and obtain 
\begin{lstlisting}
>> var_I
var_I =

0.0010
\end{lstlisting}
%
%\begin{figure}[tp]
%	\centering
%	\includegraphics[width = 0.4\textwidth]{forward_conv_mean}
%	\caption{Forward UQ. Convergence of the estimates of the expected value for increasing values of $w$.}
%	\label{fig:conv_mean}
%\end{figure}
%
Further, the sparse grid approximation of $I$ (cf.\ Eq.\ \eqref{eq:sg_interp}) is plotted in Fig.\ \ref{fig:forward_example}b.
\begin{lstlisting}
domain = [-sqrt(3),-sqrt(3);sqrt(3),sqrt(3)];
plot_sparse_grids_interpolant(S,Sr,domain,I_on_Sr) % we recall that this command embeds the
% call to interpolate_on_sparse_grid that actually constructs the sparse grid approximation
\end{lstlisting}

Then, the estimate of the pdf of $I$ can be done sampling such sparse grid approximation:
we evaluate the sparse grid approximation at $M=5000$ uniformly distributed samples of $\Gamma$ and estimate the pdf by means of an histogram or a kernel density estimator. 
The results are reported in Fig.\ \ref{fig:forward_example}c.
\begin{lstlisting}
M = 5000; 
y_samples = -sqrt(3)+2*sqrt(3)*rand(N,M); % map the uniform samples on [0,1]^2 
										  % generated by rand to [-sqrt(3),sqrt(3)]^2   
I_vals_rand = interpolate_on_sparse_grid(S,Sr,I_on_Sr,y_samples); 
H = histogram(I_vals_rand,'Normalization','pdf');  
[pdf_vals,pdf_pts] = ksdensity(I_vals_rand);
plot(pdf_pts,pdf_vals,'LineWidth',2) 
\end{lstlisting}

\begin{figure}[tp]
	\centering
	\subfigure[Error in the estimate of $\mathbb{E}\lbrack I\rbrack$ for increasing values of $w$]{\includegraphics[width = 0.27\textwidth]{forward_conv_mean}}\hspace{2em}
	\subfigure[Sparse grid surface for $w=4$]{\includegraphics[width = 0.33\textwidth]{forward_surrogate}}\hspace{2em}
	\subfigure[pdf estimation by histogram and kernel density estimation (curve in red)]{\includegraphics[width = 0.3\textwidth]{forward_pdf}}
	\caption{Forward UQ. Sparse grid approximation of $I$.}
	\label{fig:forward_example}
\end{figure}

Finally, we check the principal and total Sobol indices of $I$.
The principal Sobol indices are two values between 0 and 1 which quantify the variability of $I$ due to $y_1$ and $y_2$ alone, respectively. 
The total Sobol indices quantify instead the variability of $I$ due to each random variable considering both its individual contributions as well as 
its contributions in combination with any other variable, and are again numbers between 0 and 1 (note that, on the contrary, their sum can be larger than 1).
In other words, the first total Sobol index quantifies the variability of $I$ due to $y_1$ alone and combined with $y_2$, and vice versa for the second one.
\begin{lstlisting}
domain = [-sqrt(3) -sqrt(3);sqrt(3) sqrt(3)];
[Sob_idx, Tot_Sob_idx]=compute_sobol_indices_from_sparse_grid(S,Sr,I_on_Sr,domain,'legendre'); 
\end{lstlisting}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
They result to be
\begin{lstlisting}[backgroundcolor = \color{lightgray}]
>> Sob_idx
Sob_idx =

	0.9709
	0.0244

>> Tot_Sob_idx
Tot_Sob_idx = 

	0.9756
	0.0291 
\end{lstlisting}
This clearly shows that the first random variable is more influential on $I$ than the second one. This could also be inferred from the plot of the sparse grid approximation in Fig.\ \ref{fig:forward_example}b, where we can observe that the variability of $I$ with respect to $y_1$ is larger than with respect to $y_2$.  


\subsection{Inverse UQ analysis}\label{sect:inversion}


In this section we address inverse UQ analysis, i.e.\ ``adjusting'' the pdf of the stochastic input $\yy$ given a set of
noisy measurements (data) of the solution of Eq.\ (\ref{eq:PDE}), or of functionals thereof.
Such pdf is usually called \textit{data-informed} or \textit{posterior} pdf, $\rho_{post}$,
and can be derived using the Bayes theorem, which can be informally stated as 
\begin{equation}\label{eq:bayes_formula}
\textrm{pdf($\yy$ given data)} = \textrm{pdf(data given $\yy$)} \times \textrm{pdf($\yy$)}  \times \frac{1}{\textrm{ pdf(data)}},
\end{equation}
where ``pdf($\yy$ given data)'' is the posterior pdf $\rho_{post}$ that we aim at computing,
``pdf(data given $\yy$)'' is the so-called \textit{likelihood function}, which is denoted in the following by $\mathcal{L}(\yy)$,
and ``pdf($\yy$)'' is the pdf of the random variables based only on a-priori information on them, denoted by $\rho_{prior}$.
The ``pdf(data)'' can be simply considered to be the normalization constant
such that the posterior pdf is actually a pdf (i.e., its integral is equal to 1).
Thus, we can write in more formal terms that
  \begin{equation}
    \label{eq:bayes_formula_no_const}
    \rho_{post}(\yy) \propto \mathcal{L}(\yy) \rho_{prior}(\yy).
  \end{equation}
Then, let us consider as data a set of values $\widetilde{u}_k$, $k = 1,\ldots,K$ of the solution of the PDE  in Eq.\ \eqref{eq:PDE}
at different measurement points $x_1,x_2,\ldots,x_K$, for an unknown value of the inputs $\yy^*$.
Moreover, we assume that these observations are corrupted by additive random errors $\varepsilon_1, \ldots, \varepsilon_K$ (noise),
which we assume for simplicity to be independent, identically distributed normal random variables with zero mean and variance $\sigma_\varepsilon^2$, i.e. 
%We denote these values by $\widetilde{u}_k$, $k = 1, \ldots, K$, i.e.,
  \begin{equation}
    \label{eq:model_error}
    \begin{cases}
      \widetilde{u}_k = u(x_k,\yy^*) + \varepsilon_k, \quad k=1,\ldots,K \\
      \varepsilon_k \sim \mathcal{N}(0,\sigma_\varepsilon^2). 
    \end{cases}    
  \end{equation}
We also introduce the misfits between such data and the values obtained by the PDE model in Eq.\ \eqref{eq:PDE} for any value of $\yy$, i.e.\ 
\[
\mathcal{M}_k(\yy) : = \widetilde{u}_k - u(x_k,\yy), \quad k =1,\ldots, K.
\] 
% \Lchange{To keep the problem ``simple enough'' we assume that the misfits are independent and 
% distributed as $\mathcal{M}_k(\yy) \sim \mathcal{N}(0,\sigma_{\text{misfit}}^2)$, i.e.\ the values $\widetilde{u}_k$ are affected by additive Gaussian noise.}{}
%
The next step for the computation of the posterior pdf of $\yy$
%\Lchange{we need first of all to write the pdf of the data given $\yy$, which is usually called \textit{likelihood function} and we denote by $\mathcal{L}(\yy)$.}{}
is to write a computable expression for the likelihood function $\mathcal{L}(\yy)$ in Eq.\ \eqref{eq:bayes_formula_no_const}. Due to the assumptions on the
measurement errors $\varepsilon_k$, we can write
%\Lchange{Note that in this case the probability of observing the data $\widetilde{u}_k$ given $\yy$ is equivalent to the one of the above misfits and we can write }{}
\[
\mathcal{L}(\yy) =
\prod_{k=1}^{K} \frac{1}{\sqrt{2\pi\sigma_\varepsilon^2}}\mathrm{e}^{-\frac{\left(\widetilde{u}_k - u(x_k,\yy)\right)^2}{2\sigma_\varepsilon^2}}
= \prod_{k=1}^{K} \frac{1}{\sqrt{2\pi\sigma_\varepsilon^2}}\mathrm{e}^{-\frac{\mathcal{M}_k^2(\yy)}{2\sigma_\varepsilon^2}}.
\] 
Finally, we make the quite strong (but often reasonable) assumption that the posterior pdf $\rho_{post}$ can be well approximated by a normal distribution.
This assumption is reasonable in presence of numerous data with small measurement noise, and when the observation functional (in this case the evaluation of
$u$ at $x_k$) is adequately sensitive to the input variables, such that the actual posterior is unimodal
and well peaked. In case any of these requirements is not valid, a more appropriate approach would be to apply e.g.\
Markov-Chain Monte Carlo methods, which are agnostic with respect to the shape of $\rho_{post}$,
see e.g.\ \cite{piazzola.eal:SIR} and references therein.
Under normality assumption of the posterior, we only have to choose its mean and covariance matrix, see again e.g.\ \cite{piazzola.eal:SIR}:
\begin{itemize}
\item The mean can be taken as the mode of the posterior pdf (i.e., its maximum),
  which we denote as $\yy_{\text{MAP}}$ (Maximum A-Posteriori); 
  note that $\yy_{\text{MAP}}$ can be interpreted as a reasonable approximation of the true value of $\yy$ that generated the data,
  i.e., $\yy^* \approx \yy_{\text{MAP}}$, cf. Eq.\ (\ref{eq:model_error}).

  From a computational point of view, it is convenient to compute $\yy_{\text{MAP}}$ by 
  taking the negative logarithm of Eq.\ (\ref{eq:bayes_formula_no_const}) and computing the minimum of such quantity.
  Moreover, since we assumed a uniform prior pdf for $\yy$,
  the operation just described finally amounts to computing the minimum of the so-called \emph{negative log-likelihood} function (NLL):
  \begin{align}
    \text{NLL}(\yy) & := -\log\left(\mathcal{L}(\yy)\right)
    = \sum_{k=1}^K \frac{\mathcal{M}_k^2(\yy)}{2 \sigma_\varepsilon^2} + K \log \sigma_\varepsilon^2  + K \log \sqrt{2\pi}, \label{eq:NLL} \\
    \yy_{\text{MAP}} & : = \argmin_{\yy \in \Gamma} \text{NLL}(\yy).  \label{eq:min_NLL}  
  \end{align}
  Note that this minimization is actually independent of $\sigma_\varepsilon^2$, and it is in practice equivalent to the classical least-squares approach for calibrating $\yy$,
  i.e.\ to the minimization of the sum of the squared errors:
  \begin{align}
    \text{LS}(\yy) & = \sum_{k=1}^K \mathcal{M}_k^2(\yy),  \label{eq:ls_func}   \\
    \yy_{\text{MAP}} & = \argmin_{\yy \in \Gamma} \text{LS}(\yy).     \label{eq:sum_square_errors}
  \end{align}
  An approximation of $\sigma_\varepsilon^2$ can actually be recovered after having determined $\yy_{\text{MAP}}$, by using the standard sample variance estimator:
  \[
    \sigma_\varepsilon^2 \approx \frac{1}{K}\sum_{k=1}^K \mathcal{M}_k^2(\yy_{\text{MAP}}).
  \]
  %We remark that, in case the measurement errors are not assumed independent, additive normal random variables with constant variance, the expression of the NLL is different from the one in Eq.\ \eqref{eq:NLL} and its minimization does would not result in the classic least-squares method.\Cnote{serve dirlo?}
\item The covariance matrix $\Sigma_{\text{post}}$ can be taken as the inverse of the Hessian of the NLL at $\yy_{\text{MAP}}$.
  A convenient approximation for $\Sigma_{\text{post}}$ is
  \[
    \Sigma_{\text{post}} \approx \sigma_{\varepsilon}^2 (J_{\yy} u^\mathrm{T} J_{\yy} u)^{-1},
  \]
  where $J_{\yy} u$ is the Jacobian matrix of $u(x_1,\yy),\ldots, u(x_K,\yy)$ with respect to $\yy$, i.e.
  $(J_{\yy} u)_{k,\ell} = \frac{\partial}{\partial y_\ell} u(x_k,\yy)$.
%, $(J_{\yy} \mathcal{M})_{k,2} = \frac{\partial \mathcal{M}_k}{\partial y_2}$, $k=1,\ldots,K$
% , and\Lnote{move up?}
% \[
% \sigma_{\text{MAP}}^2 = \sum_{k=1}^K \frac{\left(\widetilde{u}_k- u(\cdot,\yy_{\text{MAP}})\right)^2}{K}
% \]
% which is an approximation of $\sigma_\varepsilon^2$. 
\end{itemize}

For the numerical tests reported in this section we fix $s_1 = s_2 = 0.5$ in Eq.\ \eqref{eq:unif_rf}. We
consider a FEM discretization with $K+2=82$ knots, and generate a set of $K$ synthetic data (one for each internal knot of the mesh), 
i.e., we use Eq.\ (\ref{eq:model_error}) with $x_k = k\frac{1}{K+1}$, $k = 1,\ldots,K$, 
$\yy^* = [0.9, -1.1]$ and $\sigma_\varepsilon = 0.01$. 
\begin{lstlisting}
K = 80;
x_k = linspace(0,1,K+2); 
s = [0.5, 0.5]; 
y_star = [0.9,-1.1];
sigma_eps = 0.01;
u_star = PDE_solver(x_k,y_star,mu,s,PDE_rhs);
u_star = u_star(2:end-1); % select the values at the internal knots of the mesh
u_tilde = u_star + sigma_eps*randn(K,1); 
\end{lstlisting}
The data thus generated are plotted in Fig.\ \ref{fig:inverse_example}a. 
The negative log-likelihood function is defined as 
\begin{lstlisting}
u = @(y) PDE_solver(x_k,y,mu,s,PDE_rhs);
misfits = @(y) [0;u_tilde;0] - u(y); % misfits are computed also at the boundary to keep
									 % the code compact, but their contribution is zero
NLL = @(y) sum(misfit(y).^2/(2*sigma_eps^2))+(K-2)*log(sigma_eps^2)+(K-2)*0.5*log(2*pi);
\end{lstlisting}
A plot of NLL in a neighborhood of $\yy^*$ is given in Fig.\ \ref{fig:inverse_example}b,c.
Its isolines are approximately ellipses, which indicates that the normal approximation of $\rho_{post}$ is appropriate in this case.
%Note that in realistic scenarios, where we deal with real data instead of synthetic ones, at this point one would not be able to
%plot the NLL, since $\sigma_\varepsilon$ is in general unknown. \Cnote{serve dirlo?}
%The shape of the isolines of the NLL however does not depend on $\sigma_\varepsilon$,
%and a plot of the least squares functional of Eq.\ (\ref{eq:ls_func}) would convey the same information.

%\begin{figure}[tb]
%	\centering
%	\includegraphics[width = 0.4\textwidth]{inverse_data} 
%	\caption{Inverse UQ. Data and ``true'' values.}
%	\label{fig:inverse_data}
%\end{figure}

\begin{figure}[tb]
	\centering
	\subfigure[Data and ``true'' values]{\includegraphics[width = 0.26\textwidth]{inverse_data}} \hspace{2em}
	\subfigure[Contour of the NLL in a neighborhood of $y^*$]{\includegraphics[width = 0.29\textwidth]{inversion_NLL_contour}} \hspace{2em}
	\subfigure[NLL in a neighborhood of $y^*$]{\includegraphics[width = 0.32\textwidth]{inversion_NLL}}
	\caption{Inverse UQ.}
	\label{fig:inverse_example}
\end{figure}

The minimization in Eq.\ \eqref{eq:min_NLL} or (\ref{eq:sum_square_errors}) can be computationally expensive, especially when sampling the values $u(\cdot,\yy)$ calls a complex model (this is actually not the case for our current example, but we illustrate this step nonetheless for the sake of generality). Hence, the exact quantity of interest $u$ can be replaced in Eq.\ \eqref{eq:NLL} by its sparse grid approximation, which is in general cheaper to evaluate. 
We consider here the sparse grid built in Sect.\ \ref{sect:forward} (third snippet) corresponding to $w=5$  and proceed as follows %\Lnote{non va cambiato misfits qui?}
\begin{lstlisting}
u_on_Sr = evaluate_on_sparse_grid(u,Sr); % u_on_Sr has dimension (K-2) x Sr.size:
                                         % the ith row contains u(x_i,Sr.knots)
u_approx = @(y) interpolate_on_sparse_grid(S,Sr,u_on_Sr,y); 
% redefine misfits to use u_approx instead of u
misfits = @(y) [0;u_tilde;0] - u_approx(y); 
% note that interpolate_on_sparse_grids supports vector-valued functions,
% so in one call we get the values of u at all nodes x_i
LS = @(y) sum(misfits(y).^2); 
\end{lstlisting}
For the minimization we resort to the Matlab function \mcode{fminsearch}
\begin{lstlisting}
% initial guess of the minimization: center of Gamma 
y_start = [0; 0];
y_MAP = fminsearch(LS,y_start);
sigma_eps_approx = sqrt(mean(misfits(y_MAP).^2)); 
\end{lstlisting}
which returns
\begin{lstlisting}
>> y_MAP
y_MAP =

	0.8787
	-1.0581

>> sigma_eps_approx
sigma_eps_approx = 

	0.0084
\end{lstlisting}
They are reasonably good approximations of $\yy^*$ and $\sigma_\varepsilon^2$.%, as expected.\Cnote{??}
Now, for the computation of an approximation of the covariance matrix we need the Jacobian matrix of $u$ with respect to $\yy$. 
Each row of the Jacobian matrix can then be computed by the function \mcode{derive_sparse_grid} as shown in the following 
\begin{lstlisting}
Jac_at_MAP = zeros(K-2,N); 
domain = [-sqrt(3), -sqrt(3); sqrt(3), sqrt(3)]; 
for i = 1:(K-2)
	Jac_at_MAP(i,:) = derive_sparse_grid(S,Sr,u_on_Sr(i,:),domain,y_MAP)'; 
end
Sigma_post = sigma_eps_approx^2*inv(Jac_at_MAP'*Jac_at_MAP);	
\end{lstlisting}
which returns
\begin{lstlisting}
>> Sigma_post

Sigma_post =

	0.0036   -0.0013
	-0.0013    0.0009
\end{lstlisting}
The resulting normal approximation of the posterior distribution of $\yy$ is plotted in Fig.\ \ref{fig:inverse_laplace_posterior}. 
 
\begin{figure}[tb]
	\centering
	\subfigure[Contour]{\includegraphics[width = 0.4\textwidth]{contour_post_pdf}}\hspace{2em}
	\subfigure[Surface]{\includegraphics[width = 0.45\textwidth]{surf_post_pdf}}
	\caption{Inverse UQ. Gaussian approximation of the posterior distribution of $\yy$.}
	\label{fig:inverse_laplace_posterior}
\end{figure}


\begin{figure}[tb]
	\centering
	\subfigure[Prior-based pdf]{\includegraphics[width = 0.3\textwidth]{inverse_pdf_prior}}\hspace{2em}
	\subfigure[Posterior-based pdf]{\includegraphics[width = 0.3\textwidth]{inverse_pdf_post}}
	\caption{Inverse UQ. Prior and data-informed pdf of $I$. Note the difference in the support of the two pdfs.}
	\label{fig:inverse_distributions}
\end{figure}

Finally, having the posterior distribution of $\yy$ at hand, we can perform the forward UQ analysis of the quantity of interest $I$ defined in Eq.\ \eqref{eq:QoI} based on such pdf.
The procedure is analogous to what done in Sect.\ \ref{sect:forward}, but the sparse grid generation needs to be further discussed due to the fact that this time
$y_1$ and $y_2$ are no longer independent. A possible solution is to introduce the transformation 
\begin{equation}\label{eq:change_of_var}
\yy = \yy_{\text{MAP}} + H^{\mathrm{T}}{\bf{z}}  
\end{equation}
with $H$ being the Choleski factor of $\Sigma_{\text{post}}$ (i.e. $H^{\mathrm{T}}H = \Sigma_{\text{post}}$) and ${\bf{z}} \sim \mathcal{N}(0,I)$, which allows to move from independent variables $z_1,z_2$ to $y_1,y_2$ dependent random variables.  
Hence, we first construct a sparse grid according to the distribution of $\bf{z}$, for example
\begin{lstlisting}
N = 2;
w = 4; 
knots = @(n) knots_normal(n,0,1); 
rule = @(ii) sum(ii-1); 
lev2knots = @lev2knots_lin; 
S = create_sparse_grid(N,w,knots,lev2knots,rule);
Sr = reduce_sparse_grid(S);
\end{lstlisting}
and then apply the change of variables in Eq.\ (\ref{eq:change_of_var}) to the sparse grid knots before calling the PDE solver: 
\begin{lstlisting}
H = chol(Sigma_post);
I = @(z) QoI(xx,H'*z+y_MAP,mu,s,PDE_rhs); % moving from z to y
I_on_Sr = evaluate_on_sparse_grid(I,Sr); 
\end{lstlisting}
Similarly, for the estimation of the distribution of $I$ we have to draw samples according to the distribution of ${\bf{z}}$.
This time we do not need to apply the change of variables in Eq.\ (\ref{eq:change_of_var}),
since it is embedded in the definition of \mcode{I} in the previous snippet:
\begin{lstlisting}
M = 5000; 
z_samples = randn(N,M); 
I_vals_randn = interpolate_on_sparse_grid(S,Sr,I_on_Sr,z_samples); 
[pdf_vals,pdf_pts] = ksdensity(I_vals_randn); 
\end{lstlisting}
In Fig.\ \ref{fig:inverse_distributions} we compare the posterior-based and prior-based pdfs of $I$.
We can immediately observe that the variability of $I$ is strongly reduced in the posterior-based case
(note the support of the posterior-based pdf of $I$, which is much smaller than the prior-based one).

%\subsubsection{\Ladd{Markov-Chain Monte Carlo}}
%
%\Ladd{As an alternative...}
%
%\begin{lstlisting}
%N_MCMC_samples = 1000; % number of samples to generate
%% Metropolis-Hasting
%std = 0.5;
%proprnd = @(x) randn(1,dim)*std*eye(dim)+x;
%s0 = rand(1,dim); 
%[samples,accept_rate] = mhsample(s0,N_MCMC_samples,';logpdf',@(y) -NLL(y',sigma_noise),...
%   'proprnd',proprnd,'symmetric',1,'thin',1,'burnin',10); % use 'nchain' to run n chains in parallel
%% Slice Sampling
%[MCMC_samples,neval] = slicesample(s0,N_MCMC_samples,'logpdf',@(y) -NLL(y',sigma_noise),...
%   'thin',1,'burnin',0);
%\end{lstlisting}

%\newpage 
\bibliographystyle{unsrt}
\bibliography{biblio}

\end{document}
