% !TeX encoding = UTF-8 Unicode
% !TeX root = manual.tex
% !TeX spellcheck = en_GB


\chapter{\texttt{subdivision}-package}

\section{\texttt{constructordering}}\label{constructordering}
The ordering in which the subdivision operators are applied for multiple subdivision schemes, is defined by the ``data-type'' \emph{ordering}. 
An ordering is a representation of an infinite periodic sequence.\footnote{Thus the multiple subdivision schemes defined by this package can be seen as stationary schemes.}
It is stored as an 1x2 - cell array, where the first cell is the non-periodic part, and the second cell is the periodic part.
Each cell can have an arbitrary number of rows.

The function \texttt{constructordering} takes vectors representing the non-periodic parts and the periodic parts of an ordering and returns it as a cell array.

\subsection*{Syntax}
\begin{param}
\item[{[ oo ] = constructordering( oo1, [pp1, oo2, pp2, ... ])}]
\end{param}

\subsection*{Input}
\begin{param}
    \item[oo1] vector of numbers, mandatory\\ The non-periodic part of the first row.
    \item[pp1] vector of numbers, optional\\ The periodic part of the first row.
    \item[ooi/ppi] vector of numbers, optional\\ The non-periodic/periodic part of the \texttt{i}$^{th}$ row.  
\end{param}

\subsection*{Output}
\begin{param}
    \item[oo] ordering\\The ordering defined by the input arguments. 
\end{param}

\subsection*{Note}
\begin{itemize}
    \item If \texttt{oo1} is an ordering, \texttt{oo1} is returned unchanged.
    \item All periodic and non-periodic parts must have the same length.
    \item The number of arguments is either 1 or an even number.
\end{itemize}

\subsection*{Example Usage}
\begin{itemize}
    \item \texttt{constructordering([1 2],[3 3])} returns \texttt{\{[1 2],[3 3]\}} which corresponds to the infinite sequence
    $1,2,3,3,3,3\ldots$.
    \item The number $\frac{1}{3}$ could be represented by \texttt{constructordering([],[3])}. Since \emph{ordering}s do not encode a decimal point, this sequence could also stand for the number $3.333\cdots$, etc..
\end{itemize}

\section{\texttt{getS}}
This function returns a finite set of \emph{subdivision operators}. This is a cell array, each row describing one subdivision operator. Each row has the entries
\begin{center}
    \texttt{\{ mask a, dilation M, digit-set D, ..., name n\}}.
\end{center}
The variables are: 
\begin{param}
    \item[mask a] $dim$-array\\Mask $a$ of the subdivision operator. 
    
    Note that univariate subdivision schemes have column vectors as masks.
    
    \item[dilation M] $dim\times dim$ matrix\\Dilation matrix $M$ of the subdivision operator.
    \item[digit-set D] $dim\times |\det M|$ matrix\\Set of representatives $D\simeq \ZZ^s/M\ZZ^s$.
    \item[name n] string\\Name of the subdivision operator.
\end{param} 
In future releases of the package, data-fields may be added to subdivision-operators. The \texttt{name} will always be the last entry in each row.

The function \texttt{getS} returns examples of \emph{subdivision operator}s in the described format.

\subsection*{Syntax}
\begin{param}
\item[{[ S ] = getS(dim || cellarray || name || list, [options])}]
\end{param}

\subsection*{Input}
\begin{param}
    \item[dim] integer\\
    Returns all subdivision operators encoded in the file \texttt{getS} in the section \texttt{\%UNNAMED OPERATORS} of the source file \texttt{getS}.
    E.g.: \texttt{getS(2);}
    
    \item[cellarray] cell-array \texttt{\{[a],M,[D],[n]\}} where \texttt{a}, \texttt{M}, \texttt{D}, \texttt{n} are described above.\\
    Takes a subdivision operator (or parts from it) and computes the missing variables. Only \texttt{M} is mandatory and thus the cell array must be at least of size $1\times2$.
    
    If \texttt{D} is not given, $D:=M\ZZ^{dim}\cap\ZZ^{dim}$.\\
    If \texttt{a} is not given $a:=\chi_D$, where $\chi$ is the characteristic function.\\
    If \texttt{n} is not given $n:=\texttt{'unnamed'}$.
    
    E.g.: \texttt{getS(\{[0.5 1 0.5]',2\});}
    
    
    \item[name] string\\
    Returns the subdivision operator with name \texttt{name} encoded in the file \texttt{getS} in the sub-routine \texttt{getS\_named}.
    
    E.g.: \texttt{getS('1\_Hassan\_Dodgson\_3point');}
    
    \item[list] name-value pairs of strings\\
    The possible names are 
    \texttt{'a'} or \texttt{'mask'}, 
    \texttt{'M'} or \texttt{'dilation}, 
    \texttt{'D'} or \texttt{'digit'}, 
    \texttt{'n'} or \texttt{'name'}.
    The possible values are as described above.
    
    E.g.: \texttt{getS('a',[.25 .5 .25;.5 1 .5;.25 .5 .25],'M',[2 0; 0 2],'n','tensorlinear');}    
\end{param}

\subsection*{Options}
\begin{param}
    \item['bigcheck'] Enables some data-integrity checks.

    \item['characteristic']  Instead of the masks, the characteristic function of the digit sets is returned as the masks.
    
    \item['help'] The strings of the named subdivision operators (i.e.\ the allowed strings for \texttt{name})  are printed (among some other strings)\footnote{This is actually an option for the function \texttt{parsem}.}.    

    \item['Omega'] Instead of the digit sets, the support of the masks minus the digit sets is returned as the digit sets.
    
    \item['nocheck'] Disables basic data-integrity checks.

    \item['supp'] Instead of the digit sets, the support of the masks is returned as the digit sets.        

    \item['verbose',val] integer, \defval{1}\\Verbose level.

\end{param}

\subsection*{Output}
\begin{param}
\item[S] cell array of subdivision operator(s)
\end{param}   

\subsection*{Note}
\begin{itemize}
\item All subdivision operators in a cell array should be for the same dimension.
\item Matlab versions prior to R2018a cannot display subdivision operators for dimension 1, and throw an error if attempted to do so. 
\end{itemize}

\subsection{Subset of the possible values for \texttt{name}}

\subsubsection{Univariate schemes}
\begin{param}    
\item['1\_all'] All named subdivision schemes of dimension $1$.
\item['1\_rand'] A random subdivision scheme of dimension $1$.
\item['1\_4point'] The 4-point scheme {\small$a=\frac{1}{16}\tbmatrix{-1&0&9&16&9&0&-1}$}, $M=2$.
\item['1\_DD'] The Dubuc-Deslauriers scheme {\small $a\!=\!\frac{1}{256}\tbmatrix{3& \!0& \!-25& \!0 &\!150 &\!256& \!150& \!0 &\!-25&\!0 &\!3}$}, $M\!=\!2$.
\item['1\_balanced\_ternary'] The balanced ternary number system $M=3$, $D=\{-1,\ 0,\ 1\}$.
\item['1\_cantor'] A scheme whose attractor is the Cantor-set.
\item['1\_daubechies',n] The $n^{th}$ Daubechies wavelet scaling function.
\item['1\_devil\_stairs'] A subdivision scheme whose basic limit function is the devil-stairs function.
\item['1\_Hassan\_Dodgson\_3point'] The Hassan-Dodgson 3-point scheme {\small$a\!=\!\frac{1}{16}\tbmatrix{1&\!\!5&\!\!10&\!\!10&\!\!5&\!\!1}$}, $M\!=\!3$.
\item['1\_spline\_binary-2'] The second order B-Spline scheme.
\item['1\_strange\_interpolatory'] An interpolatory scheme which does not fulfil $a(0)=1$.
\item['1\_three\_disjoint\_Om'] A scheme which has three disjoint invariant sets $\Omega$~\cite{CM18}.
\end{param}



\subsubsection{Bivariate schemes}
\begin{param}
\item['2\_all'] All named subdivision schemes of dimension $2$.
\item['2\_rand'] A random subdivision scheme of dimension $2$.
\item['2\_butterfly'] The butterfly scheme.
\item['2\_flash'] Scheme whose attractor is the flash.
\item['2\_McLure'] Non-integer scheme with self affine 4-tile.
\item['2\_rqj43'] Example from~\cite[Example 4.3]{CJR2002}.
\item['2\_sierp'] A scheme whose attractor is the Sierpinski triangle.
\item['2\_twindragon'] Scheme whose attractor is the twindragon.
\item['2\_V0neqV0bar\_1'] Scheme where $V_0\neq\tilde{V}_0$~\cite{CM18}.
%\item['2\_superomega'] Scheme whose super-tile is the cover-image.
\end{param}


\subsubsection{Trivariate schemes}
\begin{param}
\item['3\_rand'] Returns a random subdivision scheme of dimension $3$.
\end{param}

\subsubsection{Quadrovariate schemes}
\begin{param}
\item['4\_rand'] Returns a random subdivision scheme of dimension $4$.
\item['4\_cex\_Pot97'] Dilation matrix which does not posses a digit set, such that the corresponding attractor is a tile~\cite{Pot97}.
\end{param}


\subsection*{Example Usage}
\begin{param}
\item[getS(2)] Returns all unnamed subdivision operators of dimension $2$. The returned set may be empty, if there are no unnamed subdivision operators.
\item[getS('2\_butterfly')] Returns the butterfly scheme.
\item[getS('1\_all')] Returns all named subdivision operator of dimension 1.
\item[{getS('a',[.25 .5 .25;.5 1 .5;.25 .5 .25],'M',[2 0; 0 2],'n','tensorlinear');}] The first bivariate tensor-product B-spline.
\end{param}


\section{\texttt{blf}}
This function plots the basic limit function of multiple subdivision schemes.
    
\subsection*{Syntax}
\begin{param}
\item[{[ c, PM, xyzv, oo ] = blf( [oo], S, [options] )}]
\end{param}

\subsection*{Input}
\begin{param}
\item[{[oo]}] ordering, optional\\
Defines the ordering in which the subdivision operators are applied.
If \texttt{oo} is not given, a random ordering is computed.
\item[S] subdivision operators (or something else), mandatory\\
The parameter \texttt{S} is passed to \texttt{getS} and the returned value is used.
\end{param}

\subsection*{Options}

% Options:
\begin{param}

\item['diff',val]                  $1 \times dim$-vector or integer, \defval{0}\\
    Computes (partial) derivatives (finite differences). If \texttt{diff} is a vector the given partial derivative is computed. 
    If \texttt{diff} is a scalar, then all partial derivatives of that order are computed.
    


\item['iteration',val]             integer, \defval{depends on \texttt{S}}\\
                                   Computation stops after \texttt{iteration} many iterations.

\item['maxiteration',val]          integer, \defval{50}\\ Maximum number of iterations.

\item['maxnumpoint',val]           integer, \defval{30000}\\ Maximum number of points in the output-sequence to be computed.

\item['numpoint',val]              integer, \defval{30000}\\ Number of points in the output-sequence to be computed.

\item['plot',cellarray]            cell array or scalar, \defval{\texttt{\{\}}}\\
                                   Arguments passed to \texttt{plotm}.
                                   If $\texttt{plot}=0$, nothing is plotted.\\
                                   E.g.\ \texttt{'plot',\{'Color','red'\}}.

\item['start']                     $dim$-array, \defval{$\delta_0$}\\ Starting sequence.

\item['verbose',val]               integer, \defval{1}\\Verbose level.

\end{param}

\subsection*{Output}
\begin{param}
\item[c] $dim$-array or cell array of $dim$-arrays.\\
Iterated sequence, i.e.\ $\texttt{c}=
S_{\texttt{oo}_\texttt{n}}
\cdots
S_{\texttt{oo}_\texttt{2}}
S_{\texttt{oo}_\texttt{1}}
(\texttt{start})$.    
If \texttt{diff} is given and there is more then one partial derivative, \texttt{c} is a cell array.

\item[PM] $dim\times dim$ matrix\\Dilation matrix corresponding to the returned mesh.\\
{\color{red} There is a bug, and the returned matrix may be the transposed.}

\item[xyzv] $dim + 1 \times N$ matrix\\
Column vectors $v$ containing the function values at the position $xyz\in\RR^{dim}$.

\item[oo] vector\\ Ordering used. Equals (input-)\texttt{oo} if given.
\end{param}

\subsection*{Example Usage}
\begin{param}
\item[{[ c, PM, xyzv ,So ] = blf( '2\_butterfly', 'iteration',3, 'diff',1 )}]
\end{param}

\section{\texttt{tile}}
Plots the attractor corresponding to a multiple subdivision scheme. I.e.\ for given \texttt{S} and \texttt{oo}, the set defined by
\begin{equation*}
\texttt{M}_{\texttt{oo}_1}^{-1}\texttt{D}_{\texttt{oo}_1}+
\texttt{M}_{\texttt{oo}_1}^{-1}\texttt{M}_{\texttt{oo}_{2}}^{-1}\texttt{D}_{\texttt{oo}_2}+
\texttt{M}_{\texttt{oo}_1}^{-1}\texttt{M}_{\texttt{oo}_{2}}^{-1}\texttt{M}_{\texttt{oo}_{3}}^{-1}\texttt{D}_{\texttt{oo}_3}+
\cdots.
\end{equation*}

\subsection*{Syntax}
\begin{param}
\item[{[ Q, oo ] = tile( [oo], S, [options] )}]
\end{param}

\subsection*{Input}
\begin{param}
\item[{[oo]}] ordering, optional\\
The ordering in which the subdivision operators are applied
\item[S] subdivision operators, mandatory\\
The subdivision operators
\end{param}

\subsection*{Options}
\begin{param}
\item['digit']                    \defval{false}\\Computes iterated digit sets instead of the attractor.

\item['iteration',val]             integer, \defval{depends on \texttt{S}}\\
Computation stops after \texttt{iteration} many iterations.

\item['maxiteration',val]          integer, \defval{50}\\Maximum number of iterations.

\item['numpoint',val]              integer, \defval{30000}\\Number of points in the output-sequence to be computed.

\item['plot',cellarray]            cell array or scalar, \defval{\texttt{\{\}}}\\
Arguments passed to \texttt{plotm}, e.g.\ \texttt{\{'Color','red'\}}.
If $\texttt{plot}=0$, nothing is plotted.

\item['round',val]                integer or $1\times 2$-vector, \defval{\texttt{1e-2, 1e-12}}\\
If \texttt{round} is an integer, the same round value is used in each iteration.
If \texttt{round} is a vector, the round values are linearly interpolated.

\item['start',array]              $dim$-array, \defval{$\delta_0$}\\The starting set.

\item['supertile',n]              integer\\Computes the supertile $K=\cup_{j}(M_j^{-1}K+D_j)$ instead of the attractor. 

\item['verbose',val]              integer, \defval{1}\\Verbose level.

\end{param}

\subsection*{Output}
\begin{param}
\item[Q] $dim\times N$ matrix\\The computed attractor.
\item[oo] vector\\Ordering used. Equals \texttt{oo} (Input) if given.
\end{param}
    
\subsection*{Example Usage}
\begin{param}
\item[{tile('2\_frayed\_squares','round',[.1 1e-2])}]
\item[{tile('1\_cantor','digit')}]
\item[{tile([getS('2\_rand'); getS('2\_rand')],'supertile','iteration',10)}]   
\end{param} 

\section{\texttt{constructOmega}}
Constructs the set $\Omega_C$ as described in~\cite{CM18}.

\subsection*{Syntax}
\begin{param}
    \item[{[ Om ] = constructOmega( S, [options] )}]
\end{param}

\subsection*{Input}
\begin{param}
    \item[S] cell array of subdivision operators, mandatory
\end{param}

\subsection*{Options}
\begin{param}
    \item['lexicographic']      \defval{false}\\Orders the output set lexicographically.
    \item['Omega',val] matrix, optional, \defval{automatically computed}\\
        Starting set. If not given, a point is computed where to start from.
        In some cases, the algorithm may not find a good starting point, and the returned set is not minimal.
    \item['stable'] \defval{false}\\Does not order the set the output set.        
    \item['verbose',val] integer, \defval{1}\\Verbose level.
\end{param}    

\subsection*{Output}
\begin{param}
    \item[Om] matrix\\The set $\Omega_C$.
\end{param}

\subsection*{Example Usage}
\begin{param}
    \item[{constructOmega('2\_butterfly','Omega',[2;2],'stable')}]
\end{param}   

\subsection{Basic implementation}
\begin{lstlisting}
function [ Om ] = constructOmega( S, Om )
% S: cell array of subdivision schemes. Each row consists of a, M and D.
% Om: (Optional) the starting set
% Ex: a=1/3*[1 2 3 2 1]; M1=[2 -1;1 -2]; M2=[1 1;1 -2]; D=[0 1 2;0 0 0];
%     constructOmega({a, M1, D; a, M2, D})
    a=S(:,1); M=S(:,2); D=S(:,3);                  %extract the sets a,M and D
    J=numel(a);                                    %number of subdivision operators
    dim=size(M{1},1);                              %the dimension
    if(nargin==1); Om=zeros(dim,1); end            %if Omega is not given, set it to zero
    while(true)
        sizebefore=size(Om,2);                     %used to check if elements were added 
        for j=1:J                                  %iterate through all subdiv. operators
            OmN=M{j}\setplus(supp(a{j},dim),Om,-D{j}); %compute new possible entries
            OmN=round(OmN(:,sum(abs(OmN-round(OmN)),1)<.5/abs(det(M{j})))); %round to integers
            Om=unique([Om OmN]','rows')';          %remove duplicates
        end
        if(size(Om,2)==sizebefore); break; end     %if no elements were added, terminate
    end
    
function [ X ] = setplus( varargin )
% setplus(A,B) = { x=a+b : a in A, b in B}, operates column wise
% Ex: setplus([1 2; 1 0],[0 -1;-1 -1]); %Output: [0 1 1 2;0 -1 0 -1]
    sze=size(varargin,2);                 %number of sets
    X=varargin{sze};                      %the output set
    for i=sze-1:-1:1                      %iterate through all sets
        A=varargin{i};                    %the set to be added
        X=repmat(A,1,size(X,2))+reshape(repmat(X,size(A,2),1),size(A,1),[]); %add the set
        X=unique(X','rows')';             %remove duplicates
    end
    
function [ L ] = supp( a, dim )
% returns the support of an array. First entry is supposed to have index (0,0,...,0)
% Ex: supp([1 1;0 1],2) %Output: [0 0 1;0 1 1];
    L=zeros(dim,nnz(a));                  %output variable
    CO=cell(1,dim);                       %dummy-variable to do calculation with indices
    j=1;                                  %index-variable for the columns of D
    for i=1:numel(a)                      %iterate through all elements of the masks
        if(a(i)~=0)                       %if the element is nonzero, save the indices
            [CO{:}]=ind2sub(size(a),i);   %get the indices
            L(:,j)=[CO{:}]'-1;            %add converted cell to vector
            j=j+1;                        %increase counter
        end
    end
\end{lstlisting}
 

\section{\texttt{constructVt}}
Constructs a basis for the space $\tilde{V}_k(\Omega)$, as described in~\cite{CM18}.

\subsection*{Syntax}
\begin{param}
\item[{[ V, Om, Xmuf ] = constructVt( Om, [k] , [options])}]
\end{param}

\subsection*{Input}
\begin{param}
\item[Om] $dim \times N$ array of column vectors, mandatory\\
The set for which $V_k$ shall be constructed
\item[{[k]}] integer or a vector of integers greater equal zero, optional\\
Index or indices $k$.

\end{param}

\subsection*{Options}
\begin{param}
    \item['01'] Allows to give input \texttt{Om} as a logical array.\\ 
    E.g.\ \texttt{constructV( [1 0; 1 1; 1 0], 0, '01','verbose',2)} is equivalent to \texttt{constructV( [0 0; 1 0; 1 1; 2 0]' , 0,'verbose',2)}.
    
    \item['verbose',val] integer, \defval{1}\\Verbose level.
    
\end{param}

\subsection*{Output}
\begin{param}
    \item[Vt] matrix (or cell array of matrices) of column vectors.\\
    The basis (bases) for the space $\tilde{V}_k$.
    If $k$ is empty, then all spaces $\tilde{V}_k$ are computed for which $\dim \tilde{V}_k>0$.
    \item[{[Om]}] array of column vector\\The set for which $\tilde{V}_k$ is constructed.
    \item[{[Xmuf]}] scalar/vector\\ 
    If set, all sets $X_\mu$ of the corresponding space $V_k$ are non-empty, see~\cite{Mej19}.    
\end{param}

\subsection*{Note}
\begin{itemize}
    \item The functions \texttt{constructV} and \texttt{constructU} construct the spaces ${V}_k(\Omega)$ and $U_k(S)$ as described in~\cite{CM18}. They have nearly the same interface as \texttt{constructVt}, so they are not described in this manual. See the \texttt{help} of these functions for more informations.
    
    \item If one wants to use the matrix-approach for the characterization of convergence of subdivision schemes, the set $\Omega$ has to fulfil two assumptions. $(i)$ $\dim \tilde{V}_k(\Omega)=\dim V_k(\Omega)$, $(ii)$ $X_\mu(\Omega)$ is non-empty for all $|\mu|=k+1$. The function \texttt{dimVVt} may be used to check these two conditions.    
    
\end{itemize}

\subsection*{Example Usage}
\begin{param}
    \item[{Om=constructOmega('2\_butterfly'); constructV(Om,1)}]
\end{param}
% Output:
%   V           matrix/or cell array of matrices, each column is one basis vector for the space V_i i \in k
%
% E.g.: vdisp(constructVt([0 1 2 3]))
%       Om=constructOmega('2_butterfly'); constructV(Om,1)
%       constructV([1 0 1; 0 1 1; 1 0 1],1,'01')
%
% See also: constructVt, constructU
%
% Reference:
%   Set V_k is described in:
%       Maria Charina, Thomas Mejstrik,
%       Multiple multivariate subdivision schemes: Matrix and operator approaches, 
%       Journal of Computational and Applied Mathematics, 2018

\section{\texttt{restrictmatrix}}
Restricts matrices to a subspace and checks whether the subspace is invariant or not, 
i.e.\ with the notation from below, the function computes 
\begin{equation}
\texttt{TT}=
\left[\begin{array}{c c}\texttt{TA}&\ast\\\texttt{NULL}&\texttt{TR}\end{array}\right]=
\texttt{BASIS}^{-1}\cdot\texttt{T}\cdot\texttt{BASIS}.
\end{equation}
\subsection*{Syntax}
\begin{param}
\item[{[ TA, TT, TR, NULL, BASIS ] = restrictmatrix( T, A, [options] )}]
\end{param}

\subsection*{Input}
\begin{param}
\item[T] square matrix or cell array of square matrices, mandatory\\
The matrices which shall be restricted to the subspace \texttt{A}.
\item[A] rectangular matrix, mandatory\\
Matrix defining the subspace using column vectors.
\end{param}


\subsection*{Options}
\begin{param}

\item['epsilon',val] double, \defval{$10^{-12}$}\\The matrices are considered to be invariant if all norms of the residua \texttt{NULL\{i\}} are less then $dim\cdot\texttt{epsilon}$.

\item['smallsize'] Removes all columns of \texttt{A} (starting from the last column), without changing the rank of \texttt{A}, before computing the restriction.

\item['verbose',val] integer, \defval{1}\\ Verbose level
\end{param}
\subsection*{Output}
If the input \texttt{T} is a cell array, then the outputs 
\texttt{TA}, 
\texttt{TT}, 
\texttt{TR} and 
\texttt{NULL}
are also cell arrays. \texttt{BASIS} is always a matrix.
\begin{param}
\item[TA] $dim_A\times dim_A$ matrix (or cell array of)\\ Restriction of \texttt{T} to \texttt{A}
\item[TT] $dim_T\times dim_T$ matrix (or cell array of)\\ \texttt{T} in the basis of \texttt{A} complemented to a basis of $\RR^{dim_T}$.
\item[TR] $dim_{T-A}\times dim_{T-A}$-matrix (or cell array of)\\ Lower right corner of matrix \texttt{TT}.
\item[NULL] $dim_{T-A}\times dim_{A}$-matrix (or cell array of)\\ Lower left corner of \texttt{TT}. If \texttt{T} is \texttt{A} invariant, then \texttt{NULL} consists of zeros only.
\item[BASIS] $dim_T\times dim_T$ matrix (or cell array of)\\Complemented basis of \texttt{A} to a basis of $\RR^{dim_T}$.
\end{param} 

\subsection*{Example Usage}
\begin{param}
\item[{restrictmatrix([1 1 0; 0 1 1; 1 0 1],[1 -1 0; 0 1 -1]')}]
\end{param}

\section{\texttt{transitionmatrix}}
Constructs transition matrices 
$T_{d, \Omega}=(\texttt{a}(\alpha-\texttt{M}\beta+d))_{\alpha, \beta\in\Omega}$ 
where 
$\texttt{a}\in\texttt{S}$ are subdivision masks, 
$M\in\texttt{S}$ are dilation matrices, 
$d\in\texttt{D}\in\texttt{S}$, $D\simeq\ZZ^s/\texttt{M}\ZZ^s$, are digit sets and $\Omega\subseteq\ZZ^s$ is an invariant set for these matrices~\cite{CM18}.
\subsection*{Syntax}
\begin{param}
\item[{[ T, Om, Vt ] = transitionmatrix( S, [options] )}]
\end{param}

\subsection*{Input}
\begin{param}
\item[S] cell array of subdivision operators, mandatory
\end{param}

\subsection*{Options}
\begin{param}
\item['colsum',val]  double, \defval{disabled}\\
Tests if the columns sum up to \texttt{colsum}. If \texttt{colsum==0}, the column-sum of the first column of the first transition matrix in \texttt{T} is used.

\item['infindices']        Entries of indices not element of the support of the masks, are replaced by $\infty$ instead of $0$.

\item['noflat']            Function returns cell array of cell arrays, each corresponding to one subdivision operator.

\item['onlyindices'] Function returns $(dim+\#\Omega) \times \#\Omega$ matrix with the indices used for construction of the transition matrices (instead of the values of the mask \texttt{a} at the indices position).

\item['Omega',val] $dim\times N$ integer matrix, \defval{automatically constructed using \texttt{constructOmega}}\\
Index set used for construction of the transition matrices.

\item['verbose',val] integer, \defval{1}\\Verbose level.

\item['V',val] integer, \defval{1}, {\color{red}experimental}\\ Constructs set $\Omega$ such that $X_\mu$ is non-empty for all $|\mu|<\texttt{val}+1$, see [Mejstrik, PhD Thesis, 2019]. This option is needed if one wants to compute whether a subdivision scheme is $C^\texttt{val}$.
\end{param}

\subsection*{Output}
\begin{param}
\item[T] cell array of matrices\\The transition matrices.
\item[Om] The set $\Omega$ used to compute the transition matrices.
\item[Vt] matrix, only returned if $\texttt{'V',val}$ is given\\
The difference space $\tilde{V}_\texttt{val}$.
\end{param}

\subsection*{Example Usage}
\begin{param}
\item[{vdisp(transitionmatrix({1/4*[1 4 3]',2}))}]
\end{param}

\section{Example showing how to use the \texttt{subdivision}-package}

\begin{example}\label{ex_subdivision}
This example computes the Hölder regularity of the stationary subdivision scheme given by the subdivision operator 
$S=(a,M)$, 
with mask $a=\frac{1}{4}\left[\begin{array}{cccc}1 & 1& 3&3\end{array}\right]$ 
and dilation $M=2$.
We first generate the cell array of subdivision operators
\begin{verbatim}
S=getS('a',1/4*[1;1;3;3],'M',2);
   %There is a bug in Matlab which throws an error for the command disp(S). 
   %Thus the semi-colon is important.
\end{verbatim}
To plot the basic limit function we call
\begin{verbatim}
blf(S);
\end{verbatim}
We next construct the transition matrices and restrict them to the invariant subspace $V_0$. 
We also construct the space $\tilde{V}_0$. To apply the joint spectral radius approach to compute the regularity of subdivision-schemes, the dimension of $V_0(\Omega)$ and $\tilde{V}_0(\Omega)$ must coincide.
\begin{verbatim}
[T, Om]=transitionmatrix(S); %compute transition matrices and the set Omega
plotm(Om,'x') %plot the set Omega
V0=constructV(Om,0)                   %Construct space orthogonal to polynomial sequences
V0bar=constructVt(Om,0);            %Construct space of differences of delta
if(size(V0,2)~=size(V0bar,2)); 
    fprintf('Set Omega is wrong.');   %Test ifV0==V0bar
end
TV0=restrictmatrix(T,V0); vdisp(TV0); %restrict transition matrices and display them
\end{verbatim}
The last step is to compute the Hölder regularity using the modified invariant polytope algorithm.
\begin{verbatim}
[JSR, type]=tjsr(TV0);  
al=-log(JSR)/log(2) %Hoelder regularity. The 2 comes from the dilation M=2.
\end{verbatim}

\end{example}

%%%%%%%%%%%%%%%%%%%
% EOF
%%%%%%%%%%%%%%%%%%%