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


\chapter{Overview over the included packages}
This is the documentation for the most important functions of the packages
\texttt{cell}, \texttt{double}, \texttt{m}, \texttt{sequence}, \texttt{subdivision}, \texttt{tjsr} and \texttt{tmisc} (summarized as the \texttt{t}-packages).
The documentation for all functions (including those in this manual) can be read with the Matlab-command 
\texttt{help name}, where \texttt{name} is the name of a function, e.g.\ \texttt{help tjsr}. 

This file should also contain a copy of the \texttt{TTEST} package, which is necessary to run the test suites.

The \texttt{t}-packages can be downloaded from the Matlab file exchange
\href{https://de.mathworks.com/matlabcentral/fileexchange/}{\texttt{mathworks.com/matlabcentral/fileexchange}}.

\section{Naming/calling conventions and data-format}
\begin{itemize}
\item Most functions expect vectors in column format, contrary to Matlab's default. I.e. if you want the two column vectors 
$\left[\begin{array}{c c c}1&2&3\end{array}\right]^T$,
$\left[\begin{array}{c c c}7&8&9\end{array}\right]^T$
written in one matrix, all of the packages function expect them as%
\footnote{Internally most of the functions also use this data-format. 
Since sparse arrays in Matlab do not work well with this data-format, 
in a future release the function \texttt{tjsr} may change its data-format 
to Matlab's default.}
\begin{equation*}
\left[\begin{array}{c c c}1&7\\2&8\\3&9\end{array}\right].
\end{equation*}


\item All of the functions use \emph{name-value} pairs to pass options, e.g. \texttt{tjsr(...,'plot','norm')}, where \texttt{'plot'} is a \emph{name} and \texttt{'norm'} is a \emph{value}.
Some names expect no value, in which case the value can be omitted or given. 
If used without a value or with the value $1$ the option is enabled, if used with the value $0$, the option is disabled. 
Other arguments behind options which do not expect a value lead to undefined behaviour.

\item Optional arguments are written inside of square brackets in this documentation, with the exception when they are \emph{Options}, i.e.\ all options are optional.

\item All function-names/names/values/etc.\ are singular and written in lower-case, with the only exception when a corresponding mathematical symbol uses an upper-case letter.

\item Since Matlab (nearly) has no types for variables, we denote parameters which shall be whole numbers with the type \texttt{integer}, even if they are \texttt{double}s in reality.

\item The variables \texttt{idx} and \texttt{val} in the source-code are used only locally. They are only valid for some lines of code. They are re-used, since Matlab has no scope for variables.

\item The letters $\texttt{XX}$ in the source-code, indicates things which should be changed.
\end{itemize}

\section{Test-drivers}
Apart from the described example-usages in this documentation and in the \text{help} of each function, 
one can call the functions
\texttt{runtests('testcell')},
\texttt{runtests('testdouble')},
\texttt{runtests('testm')},
\texttt{runtests('testsequence')},
\texttt{runtests('testsubdivision')},
\texttt{runtests('testtjsr')} and
\texttt{runtests('testtmisc')}
which test every function included in the packages. 
By calling \texttt{INIT('all',1)} before executing a test suite, 
more tests are made when running the above commands.
The function \texttt{setupt} is a wrapper function, calling each of the functions above.
It succeeded on the following architectures (i.e.\ the \texttt{t}-packages are expected to run on the following architectures):
\begin{itemize}
\item Intel Core i5-4670S@3.8GHz, 8GB RAM\\
Linux 4.15.0-38,
Ubuntu 16.04.5 LTS\\
Matlab R2017a\\
with and without Gurobi v8.0.1

\item Intel Xeon IvyBridge-Ep E5-2650v2@2.6GHz, 64GB RAM\\
Linux 3.10.0, CentOS Linux 7\\
Matlab R2016b/R2017b/R2018b\\
with and without Gurobi v7.5.1/Gurobi v8.0.1

\item 
Intel Core i5-760@2.8GHz, 8GB RAM,\\
Windows 7 SP1\\
Matlab R2017a/R2018a\\
with and without Gurobi v8.0.1

\item
Intel Core i7@2.5GHz, 16GB RAM\\
OSX 10.10.5 (Yosemite), macOS 10.14.1 (Mojave)\\
Matlab R2017b\\
Gurobi v8.0.1

\item 
AMD Ryzen 5 3600, 32GB RAM,\\
Windows 10 LTSC, version 1809\\
Matlab R2018a\\
Gurobi v8.1.1

\item 
Intel Core i7-8650U@1.90GHz\\
Linux 4.15.0-99, Ubuntu 18.04\\
Matlab R2019a\\
without Gurobi
\end{itemize}
The packages do not run on Matlab versions before and including R2015b.

\section{\texttt{cell}-package}
This package implements functions for scalar operations on cell arrays. 
This package is not needed for any other package and does not depend on any other package.
\subsection*{Dependencies/Collisions}
It is possible that functions in this package are replaced by Matlab functions in future releases of Matlab.

\subsection*{Functions}
So far the following functions have been implemented:

Functions in the packages \texttt{cell} and \texttt{double} are likely to be replaced by Matlab functions in future releases of Matlab.
\texttt{diag},
\texttt{double},
\texttt{ldivide},
\texttt{minus},
\texttt{plus},
\texttt{rdivide},
\texttt{times},
\texttt{triu},
\texttt{uminus},
\texttt{uplus}.

\section{\texttt{double}-package}
This package contains functions which Matlab did not implement for \texttt{double}s but did implement for \texttt{sym}s.
This package does not depend on any other package.

\subsection*{Dependencies/Collisions}
The function in this package are hopefully replaced by Matlab functions in future releases of Matlab.

\subsection*{Functions}
So far the following functions have been implemented:
\texttt{isAlways},
\texttt{simplify}.

\section{\texttt{m}-package}
This package implements functions which generalize Matlab functions to $n$-arrays for arbitrary $n\in\NN_0$, 
and equips them with a consistent behaviour and interface.
Mathematical functions which are defined for an arbitrary number of arguments, 
but Matlab only accepts a small number (usually two), are also included in this package.
All functions should have the same input/output format as the original Matlab functions;
at least for basic inputs. Most of the functions do not rely on other packages. 

\subsection*{Dependencies/Collisions}
This package depends on the \texttt{sequence}-package and on the \texttt{tmisc}-package, but partly runs also without them.

{\color{red}
Some names of functions of this package may collide with functions from the
Matlab \texttt{Mapping Toolbox}, in particular \texttt{plotm} and \texttt{sizem}.
There are also reports that the function name \texttt{flatten} collides with some unknown package.}

The functions in this package are likely to be moved into a seperate namespace in future releases.

The function in this package are hopefully replaced by Matlab functions in future releases of Matlab.

\subsection*{Functions}
So far the following functions have been implemented:
\texttt{allm},  
\texttt{anym},  
\texttt{cart2sphm},
\texttt{convm},  
\texttt{dec2basem},  
\texttt{factorialm},  
\texttt{gcdm},  
\texttt{ind2subm},  
\texttt{isvectorm},  
\texttt{kronm},  
\texttt{lcmm},  
\texttt{maxm},  
\texttt{minm},  
\texttt{nchoosekm},
\texttt{ndimsm},  
\texttt{onesm}, 
\texttt{parsem}, 
\texttt{repmatm}, 
\texttt{sizem},  
\texttt{sph2cartm},  
\texttt{squeezem},
\texttt{summ},  
\texttt{upsamplem},  
\texttt{zerosm},  


The package also includes a small set of functions, originally not included in Matlab. These are:
\begin{param}
\item[sph2cartm2] Transforms hyperspherical to Cartesian coordinates, assuming the radius is one.
\item[cart2sphm2]Transforms Cartesian to hyperspherical coordinates, but does not return the radius.
\item[parsem] Parses \texttt{varargin}, similar to Matlab's \texttt{parse}\footnote{Most functions in the other packages rely on that function, thus it is included here.}.
\item[plotm] Unified interface for the visualization of various data types.
\item[repcellm] Works like \texttt{repmat} but returns cell-arrays.
\item[padarraym] Works like \texttt{padarray} from the \texttt{Image processing toolbox}, but works also for cell arrays, etc..\footnote{Written by~Notlikethat, \href{stackoverflow.com/users/3156750/notlikethat}{stackoverflow.com/users/3156750/notlikethat}, (2014) published under Common Creative Licence CC BY-SA.},
\end{param}



\section{\texttt{sequence}-package}
This package implements the vector space $\ell_0(\ZZ^s)$, $s\in\NN$.
The design-goal is, that \texttt{sequence}s behave exactly as arrays (whenever it makes sense) and code written for arrays can be used without modifications for \texttt{sequence}s. Unfortunately, direct referencing is not implemented yet. 

\subsection*{Dependencies}
The package depends on the \texttt{tmisc} and \texttt{m}-package. 

The package furthermore depends on the Matlab \texttt{Symbolic Math Toolbox}.
and uses functions from the Matlab \texttt{Signal Processing Toolbox} but also runs without the latter.

\subsection*{Functions}

So far the following functions are implemented:
\texttt{characteristic}   ($\chi$), 
\texttt{diffsequence}   ($\tilde{\nabla}_\mu$, $\nabla^k$), 
\texttt{norm} ($\|\vardot\|_p$), 
\texttt{supp} ($\operatorname{supp}$), 
\texttt{symbol} (the corresponding symbol),
\texttt{upsample} ($\uparrow_M$),
\texttt{conv} ($\ast$),
\texttt{nnz},
\texttt{ndims},
\texttt{size},
\texttt{ref},
and all point-wise operations. 


\section{\texttt{subdivision}-package}
This package implements functions for the work with subdivision schemes. Most of them can be used as a black-box.

\subsubsection*{Dependencies}
The package depends on the \texttt{m}-, \texttt{tmisc}- and \texttt{sequence}-package.
The package furthermore depends on the Matlab
\texttt{Parallel Toolbox} and \texttt{Symbolic Math Toolbox}.
Furthmore it uses functions from the Matlab \texttt{Signal Processing Toolbox} but also runs without the latter.

\subsubsection*{Important functions}
\begin{param}
\item[blf] Plots the basic limit function of a multiple subdivision scheme.
\item[constructOmega] Constructs the set $\Omega_C$ of a multiple subdivision scheme~\cite{CM18}.    
\item[constructordering] Constructs the data-type \texttt{ordering}.
\item[constructVt] Constructs a basis for the space $\tilde{V}_k(\Omega)$~\cite{CM18}.
\item[dimVVt] Computes the dimension of the spaces $V_k(\Omega)$ and $\tilde{V}_k(\Omega)$~\cite{CM18}.
\item[getS] Returns subdivision operators in this packages format.
\item[num2ordering] Computes number expansions for multiple multivariate number systems.
\item[ordering2num] Computes numbers corresponding for multivariate multiple number systems.
\item[restrictmatrix] Restricts matrices to a subspace.
\item[tile] Plots the attractor of a multiple subdivision scheme.
\item[transitionmatrix] Constructs transition matrices.
\end{param}

\subsubsection{Remaining functions}
\begin{param}
\item[characteristic] Returns the characteristic function of an index set.
\item[compresscoordinates] Returns an array representing the graph of a function.
\item[constructdigit] Constructs the usual digit set $M[0,1)^s\cap \ZZ^s$. 
\item[constructU] Constructs a basis for the space $U$~\cite{CP17}.
\item[constructVt] Constructs a basis for the space $\tilde{V}_k(\Omega)$~\cite{CM18}.
\item[daubechiesmask] Returns the mask coefficients for Daubechies' wavelet.
\item[findperiod] Searches for periodics in sequences.
\item[isodering] Determines if input is {ordering}.
\item[isS] Determines if input are {subdivision operator}s.
\item[isT] Determines if input are transition matrices.
\item[multiplyS] Concatenates subdivision operators.
\item[mask2symbol] Computes the symbol of a mask.
\item[normalizeS] Normalizes the values of a mask.
\item[ordering2vector] Converts an ordering to a vector of certain length.
\item[peter] Removes randomly columns of arrays.
\item[supp] Computes the support of a mask.
\item[symbol2mask] Computes the masks from given symbols.
\item[checktile] Tests if an attractor is a tile.
\item[tilearea] Tests heuristically if an attractor is a tile (for dimension $1$ and $2$).
\item[vector2ordering] Wrapper function for \texttt{findperiod}.
\end{param}



\section{\texttt{tjsr}-package}\label{tjsr_package}
This package implements functions to compute the $\JSR$ using the modified invariant-polytope algorithm.

\subsection*{Dependencies}
The package depends on the \texttt{m}- and the \texttt{tmisc}-package and partly on the \texttt{subdivision}-package
but also runs without the latter.
The package furthermore depends on the \texttt{Gurobi}-Solver
and the Matlab \texttt{Parallel Toolbox}.

If the \texttt{Gurobi}-solver is not installed, Matlab-functions will be used as a fall-back 
and the algorithm runs magnitudes slower.
If the \texttt{Parallel Toolbox} is not installed, the algorithm will run single-threaded.

\subsection*{Important functions}
\begin{param}
\item[findsmp%
\footnote{Copyright for algorithm \texttt{'genetic'} by~\cite{BC11}.}%
]
\hyperref[findsmp]{\textuparrow}
Searches for s.m.p.-candidates using various algorithms.

\item[invariantsubspace%
\footnote{Copyright for algorithm \texttt{'perm'} and \texttt{'basis} by~\cite{Jung2014} under the 3-clause BSD License.}%
]%
\hyperref[invariantsubspace]{\textuparrow}
Searches for invariant subspaces of matrices using various algorithms.

\item[tgallery]%
\hyperref[tgallery]{\textuparrow}
Returns sets of matrices, mostly used for \texttt{tjsr}.

\item[tjsr]%
\hyperref[tjsr]{\textuparrow}
Computes the joint spectral radius.

\item[tjsr\_getpolytope]%
\hyperref[tjsr_getpolytope]{\textuparrow} Returns the constructed invariant polytope returned by \texttt{tjsr}.

\item[preprocessmatrix]%
\hyperref[preprocessmatrix]{\textuparrow} Simplifies sets of matrices while preserving its $\JSR$.

\end{param}

\subsection*{Remaining functions}
\begin{param}
%\item[addcombination] Constructs short cycles from long cycles.
\item[binarymatrix] Returns sets of binary matrices.
\item[blockjsr] Returns the JSR of block diagonal matrices, given the JSR of the blocks.
\item[codecapacity] Returns matrices whose JSR is related to their capacity, given forbidden differences.
\item[computepolytopenorm] Computes the Minkowski-norm.
\item[daubechiesmatrix\footnote{Copyright for algorithm \texttt{'jung'} by~\cite{Jung2014} under the 3-clause BSD License. Copyright for algorithm \texttt{'gugl'} by Nicola Guglielmi.}] Constructs matrices whose $\JSR$ is related to the Daubechies' wavelets regularity.
\item[estimatepolytopenorm] Estimates the Minkowski-norm.
\item[estimatejsr] Rough estimate of the $\JSR$.
\item[extravertex] Finds vertices such that given polytope has non-empty interior.
\item[chooseval] Selects highest values of a vector.
\item[findsmpold] The old implementation of \texttt{findsmp}%
\footnote{Copyright for algorithm \texttt{'genetic'} by~\cite{BC11}. Copyright for algorithm \texttt{'gripenberg'} by~\cite{Jung2014} under the 3-clause BSD License.}
 (version$\leq 1.0.5$)
\item[intersectinterval] Intersects intervals.
\item[leadingeigenvector] Returns all leading eigenvectors of a matrix.
\item[makeorderinggraph] Constructs the graph corresponding to a partially ordered set.
\item[paritionatepolytope] Partitions points in $\RR^s$ into clusters of nearby points.
\item[reducelength] Removes periodics and cycles vectors such that they have smallest lexicographic value.
\item[removecombination] Constructs a minimal set of cycles.
\end{param}

\subsection*{Functions taken from others}
\begin{param}
\item[tavailable\_memory\footnote{\label{footnote_jsrtoolbox}Taken from \texttt{The JSR-toolbox}~\cite{Jung2014}. Published under the 3-clause BSD License.}] Returns the available memory.
\item[tbuildproduct\_fast\footnote{Uses code from~\cite{Jung2014}. Copyright: 3-clause BSD License.}] Constructs the product of matrices corresponding to a ordering.
\item[tcellDivide\footnoteref{footnote_jsrtoolbox}] Divides matrices in a cell.
\item[tgenNecklaces\footnoteref{footnote_jsrtoolbox}] Generation of all necklaces.
\item[tgraphSCC\footnoteref{footnote_jsrtoolbox}] Finds the strongly connected components of graph.
\item[tjointTriangul\footnoteref{footnote_jsrtoolbox}] Searches for invariant subspaces of matrices.
\item[tjsr\_zeroJsr\footnoteref{footnote_jsrtoolbox}] Decides if the JSR of a set of matrices is equal to zero.
\item[tliftproduct\footnoteref{footnote_jsrtoolbox}] Computes all products of matrices of a given length.
\item[tliftsemidefinite\footnoteref{footnote_jsrtoolbox}] Computes semi-definite liftings of matrices.
\item[tpermtriangual\footnoteref{footnote_jsrtoolbox}] Searches for invariant subspaces of matrices.
\end{param}

\noindent
All functions with prefix \texttt{tjsr\_} are subroutines of \texttt{tjsr} and are not documented here, since they are subject to big changes, whenever the main function \texttt{tjsr} is changed.
 


\section{\texttt{tmisc}-package}\label{tmisc_package}
This package contains useful functions. Most other packages rely on this package.

\subsubsection*{Dependencies}
The package depends on the~\texttt{m}-package and the~\texttt{double}-package.

\subsubsection*{Important functions}
\begin{param}
\item[findperiod] Searches for periodics of digit sequences.
\item[grCenter] Finds the centre of a tree.
\item[grVerCover] Computes all locally minimal vertex-covers of a graph.
\item[intersectspace\footnote{Copyright by Ondrej Sluciak, ondrej.sluciak@nt.tuwien.ac.at  under the 2-clause BSD License.}] Finds a basis of the intersection of subspaces.
\item[mixvector\footnote{Uses code from Jos van der Geest, samelinoa@gmail.com, under the 2-clause BSD License.}] Constructs all possible combinations of a set i.e.\ the Cartesian product.
\item[normalize] Normalizes matrices in various ways.
\item[removezeros] Deletes zeros in arrays in various ways.
\item[repcell] Repeats copies of an array.
\item[rho\footnoteref{footnote_jsrtoolbox}] Computes the spectral radius of matrices.
\item[searchincellarray] Searches in cell arrays. 
\item[setplus] Element-wise addition of vectors.
\item[setupt] Performs a self-test of all described packages.
\item[tbuildProduct\footnote{Uses code from~\cite{Jung2014}. Copyright: 3-clause BSD License.}] Constructs the product of matrices corresponding to an ordering.
\item[trho] Computes the spectral radius of matrices.
\item[uniquecell] Same behaviour as \texttt{unique}, but for cell-arrays.
\item[vdisp\footnote{\label{footnote_vdisp}Uses code by Stefan, University of Copenhagen,  under the 2-clause BSD License.}] Compact (but sometimes ugly) display of (nested) objects.
\item[vprintf] Powerful version of \texttt{sprintf} with the additional specifier \texttt{\%v}.
\end{param}

\subsubsection*{Remaining functions}
\begin{param}
    \item[cprintf\footnote{Copyright by Yair Altman (2015) under the 2-clause BSD License.}] Displays styled formatted text in the command window.
    \item[flatten] Converts nested cell arrays to flat cell arrays.
    \item[identifymatrix] Returns standard properties of matrices.
    \item[issquare] Tests if an array is a (hyper)-square.
    \item[issym] Tests if an object is symbolic.
    \item[iswholenumber] Tests if an array contains only whole numbers.
    \item[limsup] Computes the (cumulative) $\limsup$ of vectors.
    \item[liminf] Computes the (cumulative) $\liminf$ of vectors.
    \item[lexicographic] Orders vectors in a norm-lexicographic ordering.
    \item[nestedcellfun] Wrapper function calling \texttt{cellfun} for each cell in a (nested) (cell-)array.
    \item[makepositive] Multiplies arrays such that its first non-zero entry is positive.    
    \item[mat] Converts a vector to a matrix
    \item[nondiag] Extracts non-diagonal parts of 2-arrays and 2-cells.
    \item[num2color] Assigns colours to integers.
    \item[savetocellarray] Stores values in a cell array corresponding to a linear index-vector.
    \item[subsco] Indexing of matrices by coordinate-vectors.
    \item[tif] Ternary if operator.
    \item[unflatten] Converts a flat cell array to a nested cell array.
    \item[vec] Converts a matrix to a vector
   
\end{param}



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