\documentclass[german,10pt]{beamer}
%% Integer set
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\Rset}{\field{R}}
\newcommand{\Zset}{\field{Z}}
\newcommand{\Qset}{\field{Q}}
\newcommand{\Nset}{\field{N}}
% Beamer specific settings
% Other styles can be used instead of Boadilla, e.g., to add an index column.
\mode<presentation>
{
\usetheme{Boadilla} % Without index, with footer
}
\title{Finding Bounds on Ehrhart Quasi-Polynomials}
\author[H. Devos et al.]{Harald Devos \and Jan Van Campenhout \and Dirk Stroobandt}
\date[ACES'07, Edegem]{Seventh ACES Symposium \\ September 17--18 2007, Edegem}
\institute[Ghent University]
{
ELIS/PARIS \\
Ghent University
}
% This command makes the logo appear at the right side which does not fit
% the UGent style. A solution is found further below.
% \logo{\includegraphics[scale=0.25]{logolabel.jpg}}
\AtBeginSubsection[]
{
\begin{frame}<beamer>\frametitle{Outline}
\tableofcontents[currentsection,currentsubsection]
\end{frame}
}
\setbeamersize{text margin left=1cm}
\setbeamersize{text margin right=1cm}
\begin{document}
% Titlepage containing the logo of the Faculty (Engineering in this example)
\begin{frame}[plain]
\mode<presentation>{\includegraphics[width=\textwidth]{tw.pdf}}
\titlepage
\end{frame}
% UGent logo at left side from second slide on.
\setbeamertemplate{sidebar left}{
\vfill
\rlap{%\hskip0.1cm
\includegraphics[scale=0.3]{logolabel2.jpg} }
\vskip20pt
}
% Outline
\begin{frame}<beamer>\frametitle{Outline}
\tableofcontents
\end{frame}
\section{Introduction}
\subsection{What are (Ehrhart) quasi-polynomials?}
% Periodic Numbers: Example
\begin{frame}\frametitle{Periodic Numbers}
\begin{example}
\begin{minipage}{0.6\textwidth}
\includegraphics{fig/ex1_periodic_number.pdf}
\end{minipage}
\centering{
$u(n)=[3,1,4]_n$
}
\end{example}
\end{frame}
% Periodic Numbers: Def
\begin{frame}\frametitle{Periodic Numbers}
\begin{definition}
Let $n$ be a discrete variable, i.e. $n\in\Zset$.
A 1-dimensional periodic number is a function that depends periodically on $n$.
$$
u(n)=
[u_0,u_1,\ldots,u_{d-1}]_n=
\begin{cases}
u_0 & \mbox{ if $n\equiv 0 \pmod d$} \\
u_1 & \mbox{ if $n\equiv 1 \pmod d$} \\
\vdots \\
u_{d-1} & \mbox{ if $n\equiv d-1 \pmod d$}
\end{cases}
$$
$d$ is called the period.
\end{definition}
\end{frame}
% Quasi-Polynomials: Example
\begin{frame}\frametitle{Quasi-Polynomials}
\begin{example}
\centering{
$$
\begin{array}{rcl}
f(n)
&=&
-\left[\frac{1}{2},\frac{1}{3}\right]_n n^2
+3n-[1,2]_n
\\
&=&
\begin{cases}
-\frac{1}{3} n^2 +3n-2
& \mbox{ if $n\equiv 0 \pmod 2$} \\
-\frac{1}{2} n^2 +3n-1
& \mbox{ if $n\equiv 1 \pmod 2$}
\end{cases}
% &=&
% -\frac{n^2}{2}+3n-1
% -\left\{ \frac{n}{2} \right\}
% \left( \frac{2}{3}n^2+2
% \right)
\end{array}
$$
\begin{minipage}{0.4\textwidth}
\includegraphics[width=\textwidth]{fig/ex2_quasi_polynomial.pdf}
\end{minipage}
}
\end{example}
\end{frame}
% Quasi-Polynomials: Def.
\begin{frame}\frametitle{Quasi-Polynomials}
\begin{definition}
A polynomial in a variable $x$ is a linear combination of powers of $x$:
$$
f(x)=\sum_{i=0}^g c_i x^i
$$
\end{definition}
\pause
\begin{definition}
A quasi-polynomial in a variable $x$ is a polynomial expression
with periodic numbers as coefficients:
$$
f(n)=\sum_{i=0}^g u_i(n) n^i
$$
with $u_i(n)$ periodic numbers.
\end{definition}
\end{frame}
\subsection{Where do they arise?}
% Where: example
\begin{frame}\frametitle{Where do Quasi-Polynomials arise?}
\begin{example}
\begin{columns}
\column{0.40\textwidth}
\centering
\includegraphics<1>[width=\textwidth]{fig/ex3a_pp.pdf}
\includegraphics<2>[width=\textwidth]{fig/ex3b_pp.pdf}
\includegraphics<3>[width=\textwidth]{fig/ex3c_pp.pdf}
\includegraphics<4->[width=\textwidth]{fig/ex3d_pp.pdf}
$x+y\le p$
\column{0.1\textwidth}
\begin{tabular}{rr}
$p$ & $f(p)$ \\ \hline
3 & 5 \\
\pause
4 & 8 \\
\pause
5 & 10 \\
\pause
6 & 13 \\
\end{tabular}
\column{0.3\textwidth}
\pause
$$
\frac{5}{2}p+\left[-2,\frac{-5}{2} \right]_p
$$
\end{columns}
\end{example}
\end{frame}
% Where QP: overview
\begin{frame}\frametitle{Where do Quasi-Polynomials arise?}
\begin{itemize}
\item
The number of integer points in a \alert{parametric polytope} $P_{{p}}$ of dimension $n$
is expressed as a piecewise a quasi-polynomial of degree $n$ in ${p}$ (Clauss and Loechner).
\item
More general \alert{polyhedral counting problems}:\\
Systems of linear inequalities combined with $\lor, \land, \neg, \forall,$ or $\exists$ (Presburger formulas).
\item
Many problems in \alert{static program analysis} can be expressed as polyhedral counting problems.
\end{itemize}
\end{frame}
\subsection{Why do we need bounds on quasi-polynomials?}
\begin{frame}\frametitle{Why do we need bounds on quasi-polynomials?}
Some problems in static program analysis need bounds on quasi-polynomials.
\begin{example}
\centering
Number of live elements = quasi-polynomial\\
$\Downarrow$ \\
Memory usage = maximum over all execution points
\end{example}
\end{frame}
\section{How do we find bounds?}
\subsection[Ctu vs. Discr.]{Continuous versus discrete domain extrema of polynomials}
\begin{frame}\frametitle{Continuous vs. Discrete domain extrema of polynomials}
Discrete domain $\Rightarrow$ evaluate in each point \\
Not possible for
\begin{itemize}
\item
parametric domains
\item
large domains (NP-complete)
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Continuous vs. Discrete domain extrema of polynomials}
\begin{columns}
\begin{column}{0.5\textwidth}
\includegraphics[width=\textwidth]{fig/CvsD_ex.pdf}
\end{column}
\column{0.5\textwidth}
\begin{itemize}
\item
The relative difference is smaller for
\begin{itemize}
\item larger intervals
\item lower degree
\end{itemize}
\item
$\Rightarrow$ Continuous-domain extrema
can be used as approximation of discrete-domain extrema.
\end{itemize}
\end{columns}
\end{frame}
\subsection{Converting quasi-polynomials into polynomials}
% Mod Classes
\begin{frame}\frametitle{How: Mod Classes}
\begin{example}
\begin{minipage}{0.6\textwidth}
\includegraphics[width=\textwidth]{fig/QP_ex_mod_classes.pdf}
\end{minipage}
\begin{minipage}{0.35\textwidth}
Good for
\begin{itemize}
\item small period
\item large domains
\end{itemize}
\end{minipage}
\end{example}
\end{frame}
\begin{frame}\frametitle{How: Other Methods}
\begin{minipage}{0.6\textwidth}
\includegraphics[height=0.9\textheight]{fig/ACES_07_hmdevos.png}
\end{minipage}
\begin{minipage}{0.39\textwidth}
Other methods
\begin{itemize}
\item needed for large periods
\item offer trade-off between accuracy and computation time
\item see poster
\end{itemize}
\end{minipage}
\end{frame}
\section{Conclusions and Future Work}
\begin{frame}\frametitle{Conclusions and Future Work}
% Keep the summary *very short*.
\begin{itemize}
\item
Bounds on quasi-polynomials useful for static program analysis
\item
Different methods fit different situations (period, degree, domain size).
\end{itemize}
% The following outlook is optional.
\vskip0pt plus.5fill
\begin{itemize}
\item
Outlook
\begin{itemize}
\item
A hybrid method should be constructed.
\item
Parametric bounds on parameterized quasi-polynomials
\end{itemize}
\end{itemize}
\end{frame}
\end{document}
