Make a Multi-Index Set Complete#

import minterpy as mp
import numpy as np

A multi-index set \(A\) is said to be complete if, for a given polynomial of degree \(n \in \mathbb{N}\) and with respect to a given \(p\) of an \(l_p\)-norm (i.e., the \(l_p\)-degree), it contains all the exponents such that \(\lVert \boldsymbol{\alpha} \rVert_p = (\alpha_1^p + \ldots + \alpha_m^p)^{\frac{1}{p}} \leq n\) for all \(\boldsymbol{\alpha} \in A\).

This guide shows how to check a given MultiIndexSet instance for completeness and make the corresponding set of exponents complete.

Motivating example#

Consider a (incomplete) three-dimensional multi-index set with a single element and \(l_p\)-degree of \(2.0\) as follows:

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

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

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

print(mi)

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

This set has a polynomial degree of:

mi.poly_degree

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\). Given a set of exponents and \(l_p\)-degree, Minterpy automatically infers this polynomial degree.

Check for completeness#

The property is_complete of a MultiIndexSet instance returns True if the set of exponents in the instance is complete and False otherwise.

mi.is_complete

False

The check indicates that the given multi-index set is not complete with respect to the given polynomial degree and \(l_p\)-degree.

Make complete#

The method make_complete() creates a complete multi-index set from a given instance of MultiIndexSet.

mi.make_complete()

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

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

mi_complete = mi.make_complete()

And indeed, the resulting multi-index set is complete:

mi_complete.is_complete

True

Completeness with respect to different polynomial degrees and \(l_p\)-degrees#

A complete set is always defined with respect to a given polynomial degree and \(l_p\)-degree. For instance, the complete three-dimensional multi-index set for a polynomial degree \(2\) and \(l_p\)-degree \(1.0\) is:

print(mp.MultiIndexSet.from_degree(3, 2, 1.0))

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

Note

As noted in Create a Multi-Index Set, the constructor from_degree() of the MultiIndexSet class creates a complete multi-index set for the given spatial dimensions, polynomial degree, and \(l_p\)-degree.

while the complete three-dimensional multi-index set for a polynomial degree \(2\) (the same polynomial degree) and \(l_p\)-degree \(2.0\) as given above is:

print(mi_complete)

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

In particular, the element \((1, 1, 1)\) is missing from the complete set with respect to \(l_p\)-degree \(1.0\) because the element does not satisfy the condition \(\left( 1^1 + 1^1 + 1^1 \right)^1 \leq 2\) (i.e., for \(l_p\)-degree \(1.0\)). However, the element does satisfy the condition \(\left( 1^2 + 1^2 + 1^2 \right)^{0.5} \leq 2\) (i.e., for \(l_p\)-degree \(2.0\)).

Similarly, if the polynomial degree differs, the corresponding complete set for the same \(l_p\)-degree (and spatial dimensions) is in general different. For instance, the complete three-dimensional multi-index set for a polynomial degree \(3\) and \(l_p\)-degree \(2.0\):

print(mp.MultiIndexSet.from_degree(3, 3, 2.0))

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

The set contains many more elements compared the previous two because the condition \(\lVert \boldsymbol{\alpha} \rVert_2 = (\alpha_1^2 + \alpha_2^2 + \alpha_3^2)^{\frac{1}{2}} \leq 3\) may now be satisfied for many more multi-index elements.

Completeness vs downward-closedness#

All complete multi-index sets are downward-closed (see Make a Multi-Index Set Downward-Closed). Indeed, the three different complete multi-index sets given above do not contain any lexicographical “holes”; all are downward-closed.

Generally speaking, a downward-closed set may or may not be complete but, unlike completeness, downward-closedness is defined independently from any polynomial degree and \(l_p\)-degree.