Make a Multi-Index Set Downward-Closed

import minterpy as mp
import numpy as np

A multi-index set is said to be downward-closed if the set does not contain any lexicographical “holes”. For a more rigorous definition of downward-closedness, please refer to the relevant section in the docs.

This guide shows how to check a given MultiIndexSet instance for downward-closedness and make the corresponding set of exponents downward-closed.

Motivating example

Consider a non-downward-closed two-dimensional multi-index set with two elements:

\[ A = \{ (1, 0), (1, 2) \}. \]

This set is not downward-closed because it contains lexicographical “holes” between \((0, 0)\) and the lexicographically largest element \((1,2)\) (e.g., \((0, 0)\) itself, \((0, 1)\)).

This multi-index set can be created in Minterpy as follows:

mi = mp.MultiIndexSet(np.array([[1, 0], [1, 2]]), lp_degree=1.0)

Note

As noted in Create a Multi-Index Set, creating a MultiIndexSet instance from the default constructor requires the parameter lp_degree (i.e., the \(l_p\)-degree) to be specified. Here the value of \(1.0\) is chosen arbitrarily.

print(mi)

MultiIndexSet(m=2, n=3, p=1.0)
[[1 0]
 [1 2]]

Check for downward-closedness

The property is_downward_closed of a MultiIndexSet instance returns True if the set of exponents in the instance is downward-closed and False otherwise.

mi.is_downward_closed

False

Make downward-closed

The method make_downward_closed() creates a downward-closed multi-index set from a given instance of MultiIndexSet.

mi.make_downward_closed()

MultiIndexSet(
  array([[0, 0],
         [1, 0],
         [0, 1],
         [1, 1],
         [0, 2],
         [1, 2]]),
  lp_degree=1.0
)

The method returns a new instance of MultiIndexSet and can be stored in a variable for further use:

mi_downward_closed = mi.make_downward_closed()

And indeed, the resulting multi-index set is downward-closed:

mi_downward_closed.is_downward_closed

True

Downward-closedness vs completeness

All complete multi-index sets (see Make a Multi-Index Set Complete) are downward-closed. A downward-closed multi-index set, however, may or may not be complete. A complete set must be defined with respect to the corresponding polynomial degree and the chosen \(l_p\)-degree.

In the example above, the downward-closed multi-index set has the following polynomial degree with respect to the chosen \(l_p\)-degree (\(1.0\)):

mi_downward_closed.poly_degree

3

Note

This polynomial degree corresponds to the minimum degree \(n\) such that all elements in the multi-index set satisfy the \(l_p\)-norm condition \(\lVert \boldsymbol{\alpha} \rVert_p = (\alpha_1^p + \ldots + \alpha_m^p)^{\frac{1}{p}} \leq n\) for all \(\boldsymbol{\alpha} \in A\).

The corresponding complete multi-index set is (the method from_degree() constructs a complete set):

mi_complete = mp.MultiIndexSet.from_degree(
    mi_downward_closed.spatial_dimension,
    mi_downward_closed.poly_degree,
    mi_downward_closed.lp_degree,
)
print(mi_complete)

MultiIndexSet(m=2, n=3, p=1.0)
[[0 0]
 [1 0]
 [2 0]
 [3 0]
 [0 1]
 [1 1]
 [2 1]
 [0 2]
 [1 2]
 [0 3]]

which contains additional multi-index elements.

Note

Downward-closedness and completeness coincide when the lexicographically largest multi-index element of a multi-dimensional set has all the same values (i.e., \(\boldsymbol{\alpha}_{\max} = \left( k, \ldots, k \right),\; k \in \mathbb{N}_{\geq 0}\)). The corresponding downward-closed set is the same as the complete set with respect to polynomial degree \(k\) and \(l_p\)-degree \(\infty\).