===================
MultiIndices
===================

Background
-------------------

A multiindex is simply a length :math:`D` vector of nonnegative integers :math:`\mathbf{p}=[p_1,p_2,\dots,p_D]`.
Multiindices are commonly employed for defining multivariate polynomial expansions and other function parameterizations.
In these cases, sets of multiindices define the form of the expansion.   

**Example: Multivariate Polynomial**

A multivariate polynomial :math:`\Phi_{\mathbf{p}}(\mathbf{x}) : \mathbb{R}^D\rightarrow R` can be defined as the 
product of :math:`D` univariate polynomials.   Using monomials for example,

.. math::

    \Phi_{\mathbf{p}}(\mathbf{x}) = \prod_{i=1}^D x_i^{p_i}

A multivariate polynomial expansion can then be written succinctly as 

.. math::

    f(\mathbf{x}) = \sum_{\mathbf{p}\in\mathcal{S}} c_{\mathbf{p}} \Phi_{\mathbf{p}}(\mathbf{x})

where :math:`\mathcal{S}` is a set of multiindices and :math:`c_{\mathbf{p}}` are scalar coefficients.


**Example: Wavelets**

Multivariate polynomials are constructed from a tensor product of one-dimensional functions and each
one-dimensional function depends on a single integer: the degree of the one-dimensional polynomial.   This is a common 
way to define multivariate functions from indexed families of one-dimensional basis functions.  In a general 
setting, however, the one-dimensional family does not need to be index by a single integer.  Families of 
one-dimensional functions indexed with multiple integers can also be "tensorized" into multivariate functions.
Wavelets are a prime example of this.

A one dimensional wavelet basis contains functions of the form

.. math::

    \psi_{j,k}(x) = 2^{j/2}\psi(2^jx -k)

where :math:`j` and :math:`k` are integers and :math:`\psi :\mathbb{R}\rightarrow \mathbb{R}` is an orthogonal wavelet. 
Unlike polynomials, two integers are required to index the one-dimensional family. Nevertheless, a multivariate wavelet 
basis can be defined through the tensor product of components in this family:

.. math::

    \Psi_{\mathbf{p}}(\mathbf{x}) = \prod_{i=1}^{D/2} \psi_{p_{2i},p_{2i+1}}(x_i)

where :math:`\Psi_{\mathbf{p}} : \mathbb{R}^{D/2}\rightarrow \mathbb{R}` is a multivariate wavelet basis function in 
:math:`D/2` dimensions and :math:`\mathbf{p}` is a multiindex with :math:`D` components. 

C++ Objects
-------------------

.. toctree::

   multiindices/multiindex
   multiindices/multiindexset
   multiindices/fixedmultiindexset
   multiindices/multiindexlimiter
   multiindices/multiindexneighborhood


Definitions
-------------------

.. topic:: Limiting Set

    In general, any length :math:`D` vector in :math:`\mathbb{N}^D` is a multiindex.  In many adaptive approaches, however,
    it is useful to only consider multiindices in some subset :math:`\mathcal{G}\subseteq \mathbb{N}^D`.   We call this subset 
    the limiting set or, more loosely, the "limiter".   In MParT, limiting sets are defined by functors that accept a 
    MultiIndex and return `true` if the multiindex is in :math:`\mathcal{G}` and `false` otherwise.  Some predefined limiting 
    sets are defined in the MultiIndexLimiter namespace, but custom functors can also be employed.

.. topic:: Neighbors

    In most parameterization applications, there is additional structure in the multiindex set that can be represented 
    through edges on a graph.   Each multiindex can be treated as a node in directed graph.  Outgoing edges connect to 
    other multiindices, which we call "forward neighbors", that represent higher order basis functions.   Incoming edges
    come from multiindices, which we call "backward neighbors", that represent lower order basis functions.   
    
    In the multivariate polynomial example above, the backward neighbors of a multiindex :math:`\mathbf{j}` are the multiindices
    that only differ from :math:`\mbox{j}` in one component, and in that component, the difference is -1.  More precisely, 
    the set of backward neighbors is 
    
    .. math::
    
        \mathcal{B}_{\mathbf{j}} = \{\mathbf{i} : \|\mathbf{i}-\mathbf{j}\|_1=1 \text{ and } \mathbf{i}_k \leq \mathbf{j}_k \text{ for all } k \}.
    
    The set of forward neighbors is similarly defined as 

    .. math::

        \mathcal{F}_{\mathbf{j}} = \{\mathbf{i} : \|\mathbf{i}-\mathbf{j}\|_1=1 \text{ and } \mathbf{i}_k \geq \mathbf{j}_k \text{ for all } k \}

    The neighborhood structure of a multindex set is defined through a child of the abstract MultiIndexNeighborhood class.

.. topic:: Downward Closed

    A multiindex set :math:`\mathcal{S}` is downward closed if for any multiindex :math:`\mathbf{j}\in\mathcal{S}`, all 
    backward neighbors of :math:`\mathbf{j}` are also in :math:`\mathcal{S}`.

.. topic:: Margin

    For a multindex set :math:`\mathcal{S}\subseteq\mathcal{G}`, the margin of :math:`\mathcal{S}` is the set
    :math:`\mathcal{M} \in \mathcal{G}\setminus\mathcal{S}` containing indices that have at least one backward neighbor
    in :math:`\mathcal{S}`.

.. topic:: Reduced Margin

    The reduced margin :math:`\mathcal{M}_r\subseteq\mathcal{M}` is a subset of the margin :math:`\mathcal{M}` containing
    indices that could be added to the set :math:`\mathcal{S}` while preserving the downward closed property of :math:`\mathcal{S}`.
    Multiindices in the reduced margin are often called admissible. 

.. topic:: Active/Inactive Indices

    The MultiIndexSet class stores both the set :math:`\mathcal{S}` and the margin :math:`\mathcal{M}`.   In MParT,
    multiindices in :math:`\mathcal{S}` are sometimes called active, while multiindices in :math:`\mathcal{M}` are called inactive.
    Only active indices are included in the linear indexing.  Inactive
    indices are hidden (i.e. not even considered) in all the public members
    of this class.  Inactive multiindices are used behind the scenes to check admissability, to define the margin, and 
    are added to the :math:`\mathcal{S}` during adaptation.

.. topic:: Frontier

    The Frontier is similar but contains multiindices in :math:`\mathcal{S}` that have at least one forward neighbor in 
    the margin :math:`\mathcal{M}`.   We use the term "strict frontier" to describe the set of multiindices in :math:`\mathcal{S}` that have all of their forward neighbors in the margin.