Multivariate indices enumeration functions

Enumeration functions are bijections from \Nset to \Nset^{\inputDim}. We detail here some particular bijections:

  • Hyperbolic enumeration function,

  • Linear enumeration function,

  • Anisotropic hyperbolic enumeration function,

  • Infinity norm enumeration function.

All these enumeration functions are illustrated in Plot enumeration function.

A possible use is to build a multivariate basis as the tensorization of univariate basis: this is the case for example in the functional chaos expansion setting (refer to Functional Chaos Expansion and Tensorized multivariate basis enumeration functions).

Let \vect{\alpha} be a multi-index is defined by:

\vect{\alpha} = (\alpha_0, \dots, \alpha_{\inputDim-1}) \in \Nset^{\inputDim}

For any real number q > 0, we consider the q-hyperbolic norm (or q-norm for short) of a multi-index \vect{\alpha} be defined by:

(1)\|\vect{\alpha}\|_{q} \, \, = \, \, \left(\sum_{i=0}^{\inputDim-1} \; \alpha_i^q \right)^{1/q}

The operator \|\cdot\|_q is a norm if anf only if q \geq 1 and is a pseudo-norm if 0 < q < 1 since it does not satisfy the triangular inequality. However this abuse of language will be used in the following. Note that the case q=1 corresponds to the definition of the length of \vect{\alpha}.

An enumeration function \tau is a bijection from \Nset to \Nset^{\inputDim}, which creates a one-to-one mapping between an integer j and a multi-index \vect{\alpha}. The function \tau is defined by:

\begin{array}{llcl} \tau \, : & \Nset & \longrightarrow & \Nset^{\inputDim} \\ & j & \longmapsto & \vect{\alpha}(j) \end{array}

The enumeration function orders the elements according to the graded reverse lexicographic order ([sullivan2015]) as follows:

  • \tau(0) = \vect{0},

  • for any k \in \Nset^* and any j \in \left\{ 0, \dots, k-1 \right\} we have:

    \tau(j) < \tau(k)

which means that:

  • either \|\tau(j)\|_{q} < \|\tau(k)\|_{q},

  • or \|\tau(j)\|_{q} = \|\tau(k)\|_{q} and : either \alpha_0(j) > \alpha_0(k), or there exists m \in \{1,\dots,\inputDim-1\} such that:

    \begin{array}{lcl} \alpha_0(j) & = & \alpha_0(k) \\ & \vdots & \\ \alpha_{m - 1}(j) & = & \alpha_{m - 1}(k) \\ \alpha_m(j) & > & \alpha_m(k) \end{array}

    which means that in that case, either the first component of \tau(j) is greater than the first component of \tau(k), or all the components of \tau(j) and \tau(k) are equal until the component m-1 and the component m of \tau(j) is greater than the component m of \tau(k).

Hyperbolic enumeration function

Let \lambda be a real positive number. Let \cA_{\lambda} be the set of multi-indices with q-norm not greater than \lambda as follows:

(2)\cA_{\lambda} \, \, = \, \, \{\vect{\alpha} \in \Nset^{\inputDim} \, : \, \|\vect{\alpha}\|_q \, \leq \lambda \}.

Moreover, let the front of \cA_{\lambda} be defined by:

\partial \cA_{\lambda} \, \, = \, \, \left\{\vect{\alpha} \in \cA_{\lambda} \, : \, \exists \; i \; \in \; \{0,\dots,\inputDim-1\} \, , \, \, \vect{\alpha} \, + \, \vect{e_i} \, \notin \, \cA_{\lambda} \right\}

where \vect{e_i} is a multi-index with a unit i-entry and zero k-entries, k\neq i.

We also define the set of candidates from the elements of \cA_\lambda. The set of the candidates is denoted by \cC_\lambda and is defined by:

\cC_\lambda\, \, = \, \, \left\{\vect{\alpha} \, + \, \vect{e_i} \, : \, \vect{\alpha} \in \partial \cA_{\lambda} \, , \, \vect{\alpha} + \, \vect{e_i} \notin \cA_{\lambda} \, , \, 0 \leq i \leq \inputDim-1, \right\}

We note that for all \lambda, \cC_\lambda \neq \emptyset because for any \lambda \in \Rset^+, there exists \vect{\alpha} \in \Nset^\inputDim such that \|\vect{\alpha}\|_{q} > \lambda.

The principle consists in exploring the space \Nset^{\inputDim} through the q-norm of its elements. In this purpose, we define an appropriate increasing sequence (\lambda_n)_{n \in \Nset} as follows:

\left\{ \begin{array}{l} \lambda_0 = 0 \\ \lambda_{n+1} = \min_{\vect{\alpha} \in \cC_{\lambda_n}} \left\{ \|\vect{\alpha}\|_{q} \right\} \end{array} \right.

The sequence is well defined because by definition, all the elements of \cC_{\lambda_n} have a q-norm strictly greater than \lambda_n.

From the sequence (\lambda_n)_{n \in \Nset}, we call (\cA_{\lambda_n})_{n \in \Nset} the sequence of cumulated strata. The sequence (\Delta_n)_{n \in \Nset} of the strata is defined by:

\left\{ \begin{array}{l} \Delta_0 = \cA_{\lambda_{0}} \\ \Delta_{n+1} = \cA_{\lambda_{n+1}} \setminus \cA_{\lambda_n} \end{array} \right.

Note that we have \cA_{\lambda_{n+1}} \subset \cA_{\lambda_n} \cup \cC_n and that \Delta_n = \left\{ \vect{\alpha} \in \Nset^\inputDim, \|\vect{\alpha}\|_{q} = \lambda_n \right\}.

Based on this definition of strata \Delta_n, the elements are enumerated according to the graded reverse lexicographic order defined previously. Note that:

  • \|\tau(j)\|_{q} < \|\tau(k)\|_{q} means that \tau(j) is inside a strata of lower index than \tau(k),

  • \|\tau(j)\|_{q} = \|\tau(k)\|_{q} means that \tau(j) and \tau(k) are inside the same strata.

Linear enumeration function

The linear enumeration function is a hyperbolic enumeration function where q=1. It means that \|\vect{\alpha}\|_1 = \sum_{i=0}^{\inputDim-1} \alpha_i which is the length of the multi-index {\vect{\alpha}}.

In that case, the sequence (\lambda_n)_{n \in \Nset} is \lambda_n = n.

Anisotropic hyperbolic enumeration function

We consider enumeration functions based on an anisotropic hyperbolic norm defined by:

(3)\|\vect{\alpha}\|_{\vect{w},q} \, \, = \, \, \left(\sum_{i=0}^{\inputDim-1} \; w_i\; \alpha_i^q \right)^{1/q}

where the weights w_i are real positive numbers. They enable to weight some specific marginal indices.

In this setup, we consider both schemes outlined in the previous paragraph: it is only necessary to replace the isotropic q-norm in (2) with the (\vect{w},q)-anisotropic one.

This enumerate function emphasizes multi-indices whose components are larger when the associated weights are smaller.

Infinity norm enumeration function

We consider the enumeration function based on the infinite norm:

(4)\|\vect{\alpha}\|_{\infty} \, \, = \, \, \max_{0 \leq i \leq \inputDim-1} \; \alpha_i

In that case, we have \lambda_n = n.

If q \rightarrow 0, then \|\vect{\alpha}\|_{q} \rightarrow \|\vect{\alpha}\|_{\infty}.