\documentclass[11pt]{article}
\newcommand{\thisdocument}{Budget}
\usepackage{url, xspace}
\include{macros}

\newcommand{\sagecombinat}{{\sc Sage-Combinat}\xspace}
\newcommand{\sage}{{\sc Sage}\xspace}
\newcommand{\fixit}[1]{\textcolor{red}{*** \texttt{#1} ***}}

\begin{document}

\begin{center}
\Large\bf Budget Justification Page
\end{center}
\begin{itemize}\setlength{\itemsep}{-0.5ex}
\item[A] SALARY: 

\item[B] OTHER PERSONNEL:

\item[C] FRINGE BENEFITS:  
 
\item[D] EQUIPMENT:
\begin{enumerate}%

\item Computer: A Dell Server with 48 cores and 256GB RAM:  {\bf \$25,526}

\end{enumerate}


\item[E] TRAVEL:

\item[F] OTHER DIRECT COSTS:
\begin{enumerate}%

\item {\bf Student Salary:} The PI is requesting salary for 1 graduate student for 
1 hour per week at \$20/hour for 3 years:  
$\qquad
 1\times 52 \times 20 \times 3 = \mathbf{\$3120}
$

The student will do routine systems administration of the computer
(upgrades, backups, creation of accounts, etc.). 

\end{enumerate}


\item[G] MATERIALS AND SUPPLIES:

\item[I] INDIRECT COSTS: 

\end{itemize}

\section{Budget justification}

The collaborative nature of the project requires advanced software
development tools (ticket server, distributed version control), as
well as heavy computational resources (multi-platform compilation,
regression testing, benchmarking;
see \S~\ref{section.devel}). So far, the \sagecombinat
project has been using a virtual server, courtesy of the \sage team at
the University of Washington (\url{combinat.sagemath.org}). Scaling
further will require its replacement by a modern server, to be hosted
as part of the \sage computation farm (which currently includes four
{\sc GNU/Linux} servers with 24 cores and 128Gb of RAM). It will be
accessible remotely for all participants, through {\sc ssh} or the
\sage notebook interface. This server will also be used for time or
memory demanding calculations
(see \S~\ref{section.exploration}). Unused resources will be
made available to the \sagecombinat and \sage community at large and
will continue to be a resource for the \sagecombinat community well
after the end of this project.

An important artifact is that our computing needs, both for software
development and computer exploration, usually come in bursts.  Beside,
assuming appropriate software preconfiguration (which rules out using
typically available supercomputers which are preconfigured for
``scientific computing''), running such large calculations remotely is
easy. It is therefore a much better investment (both from a financial
and system administration point of view) to share a single large
computing server, as opposed to several smaller ones hosted at local
institutions, as it spreads the load and thus guarantees a continuous
use of the computing power.

We chose the quote from Dell over the ones from Oracle and Silicon
Mechanics, because Oracle's was too high, and though Silicon Mechanics
quote was a little lower, Dell is a much larger vendor with an
excellent relationship with the University of Washington mathematics
department.

\subsection{Software development needs}
\label{section.devel}

\sage is a rather large and complex piece of software. Its stability
relies very much on its review process. Lately, this review process,
together with the subsequent release management, has become a
bottleneck in \sage's development. This is being tackled by the \sage
developers by a progressive automation of the workflow. This
automation is particularly vital for a project mostly run by
volunteers whose main job is research, even if the price is a heavy
use of computing power.

Let us give some figures. The \sagecombinat queue continuously holds
around 200 patches; at some \sage releases more than 30 of them were
merged at once. One important part of the review and release process
is the running of \sage's regression test, which ensures that new
features and bug fixes do not introduce problems; a typical patch
review requires running the tests a dozen times. Running them on an
average laptop takes two hours, compared to a couple minutes on the
current \sage's multicore server, and tentatively one on the requested
server. This difference totally conditions the feasibility of reviews.

Beside, the current \sage servers are being progressively saturated,
and the \sagecombinat community is growing at a fast pace.

\subsection{Outstanding computer exploration}
\label{section.exploration}

All the recent results of the participants made use of heavy computer
exploration at some point. Due to the typical combinatorial explosion
in algebraic combinatorics, the involved calculations can just not be
run on a desktop computer nor even on an average computation
server. In the following, we give three outstanding examples of
calculations that would be made possible by the requested server.

\subsubsection{Classification of finite affine crystals}

Kashiwara conjectured~\cite[Introduction]{kashiwara.2005} that any
'good' finite affine crystal is an $n$-fold tensor product of
Kirillov-Reshetikhin crystals (see~\cite[Section 8]{kashiwara.2002}
for a definition of 'good') for some $n$. This would result in a
classification of these
crystals. In~\cite{Bandlow_Schilling_Thiery.2008.Promotion} we proved
this result in type $A$ and $n=2$ for crystals coming from promotion operators,
and found further evidence for this conjecture for $n>2$
using heavy computer exploration with {\sc MuPAD-Combinat} involving
crystal graph isomorphisms. This also revealed new structures about
these crystals.

Pursuing computer exploration for larger $n$ would allow to better
understand, and make use of, the symmetries, which is the main
bottleneck for tackling $n>2$. This would be made possible by the
combination of the requested many-core server, of \sage's parallel
features and of a parallel implementation of the crystal isomorphism
algorithmic, in order to tackle the exponential growth with $n$ of the
exploration space.

\subsubsection{Combinatorial conjectures on Bruhat order}

There are a number of combinatorial conjectures in Bump and
Nakasuji~\cite{BumpNakasuji} that have been tested using \sage for
simply-laced Cartan types, but only up to $A_5$ and $D_4$, by lack of
a powerful enough computer. Pushing those computations further is
necessary to gain confidence in the conjectures.

\subsubsection{Computation with Macdonald polynomials}
In the paper where $k$-Schur functions were introduced \cite{LLM03}, it
was conjectured that an appropriate subset of Macdonald polynomials
expand positively in the basis of $k$-Schur functions.  This conjecture
is still open, and has only been verified to a relatively low degree
(around $n=15$).  This is due to the difficulty of computing large
Macdonald polynomials.  A publicly available, easily accessible table of
precomputed Macdonald polynomials would simplify exploration of this and
other similar conjectures.

%\bibliographystyle{alpha}
%\bibliography{budget}
\begin{thebibliography}{LLM03}

\bibitem[BN10]{BumpNakasuji}
Daniel Bump and Maki Nakasuji.
\newblock Integration on {$p$}-adic groups and crystal bases.
\newblock {\em Proc. Amer. Math. Soc.}, 138(5):1595--1605, 2010.

\bibitem[BST10]{Bandlow_Schilling_Thiery.2008.Promotion}
Jason Bandlow, Anne Schilling, and Nicolas~M. Thiéry.
\newblock On the uniqueness of promotion operators on tensor products of type a
  crystals.
\newblock {\em Journal of Algebraic Combinatorics}, 31, Mai 2010.
\newblock arXiv:0806.3131 [math.CO].

\bibitem[Kas02]{kashiwara.2002}
Masaki Kashiwara.
\newblock On level-zero representations of quantized affine algebras.
\newblock {\em Duke Math. J.}, 112(1):117--175, 2002.

\bibitem[Kas05]{kashiwara.2005}
Masaki Kashiwara.
\newblock Level zero fundamental representations over quantized affine algebras
  and {D}emazure modules.
\newblock {\em Publ. Res. Inst. Math. Sci.}, 41(1):223--250, 2005.

\bibitem[LLM03]{LLM03}
L.~Lapointe, A.~Lascoux, and J.~Morse.
\newblock Tableau atoms and a new {M}acdonald positivity conjecture.
\newblock {\em Duke Math. J.}, 116(1):103--146, 2003.

\end{thebibliography}


\end{document}