\documentclass[10pt]{beamer}
\include{macros}

\mode<presentation>
{
  \usetheme{Warsaw}
\usecolortheme{rose}
%\usecolortheme{seahorse}
  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[english]{babel}
% or whatever

\usepackage[latin1]{inputenc}
% or whatever

\usepackage{times}
\usepackage[T1]{fontenc}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.


\title{SAGE: Linear Algebra Plan}

\author{William Stein}

% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

\date[Jan 5] % (optional)
{\vspace{-6ex}

February 12, 2007, SAGE week\\

\includegraphics[width=22em]{sage-car.png}}

\subject{Talks}

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

%\beamerdefaultoverlayspecification{<+->}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}[fragile]
\frametitle{The Goal}

{\bf GOAL:} {\dred Implement fast optimized linear algebra over exact rings
and fields in SAGE.}

\vfill

We have been working on this for what seems like {\em\dred forever}, and are not done!

\begin{verbatim}
On Friday 08 April 2005 03:09 am, Kevin Buzzard wrote:
> I had no idea it [SAGE] had got so far. I had 
> conjectured that you would still be messing with
> the linear algebra stuff.
\end{verbatim}

\vfill

In particular, at a minimum we need modern fast optimized implementations
of algorithms for linear algebra over $\Z$, $\Q$, $\F_q$, $\Q_p$,
number fields (especially cyclotomic fields), and $k(t)$ for $k$
each of the fields listed before. {\dblue Both dense and sparse with
identical functionality.}

\end{frame}

\begin{frame}
\frametitle{First Challenge}

\begin{enumerate}

\item In the world of numerical computation, developing good linear algebra
tools has been extremely difficult (because of roundoff error, etc.), but
that group of people has succeeded.   
\vfill

\item Unfortunately, for linear algebra over exact rings and fields, the
situation is {\dred terrible} in comparison because the main people who have done this (Magma
and cryptography researchers) often do not make their tools available to the
community (so ask them to!!).  But at least they have proved that good results are possible.

\vfill
\item The {\dred linbox} project has been around for over 5 years now, and is
a free C++ library that aims to address this problem:
\url{http://www.linalg.org/NEWS-1.1.html}
\vfill
\item Linbox is now finally getting quite usable, and is in fact {\dred kicks ass} at
{\em certain} things.

\end{enumerate}

\end{frame}

\begin{frame}
\frametitle{High Level Plan for Linear Algebra in SAGE}

\begin{enumerate}

\item (done) {\dred Initial Python implementation} so what functionality is needed is clear, and a package
that {\em uses} linear algebra in a highly nontrivial way over almost every base ring can be implemented (namely modular symbols).  
\item (done) {\dred Rewrite implementation SageX} -- compiled language, and restructure implementation to make
it possible to systematically create optimized matrix classes for different base rings. 
\item {\dred Incorporate linbox} into SAGE (in progress); complain, fix bugs, discover gaps, etc. 
\item {\dred Implement advanced optimized algorithms} in the context of SAGE (in progress);
fix bugs, etc. 

\end{enumerate}

\end{frame}
\begin{frame}[fragile]
\frametitle{Yardstick}

\begin{enumerate}
\item The fastest general purpose system in the world for dense linear algebra is MAGMA.
\item Most general purpose math software is {\em terrible} compared to MAGMA at
exact linear algebra.  PARI won't save us here:
\begin{verbatim}
sage: m = random_matrix(ZZ,200)
sage: time k=m*m
CPU times: user 0.05 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.12
sage: g = pari(m)
sage: time h=g*g
CPU times: user 0.71 s, sys: 0.00 s, total: 0.72 s
Wall time: 0.72
sage: time z = g.matker()
CPU times: user 47.64 s, sys: 0.21 s, total: 47.85 s
Wall time: 49.12
sage: n=m.change_ring(QQ)         
sage: time w=n.kernel()
CPU times: user 0.14 s, sys: 0.02 s, total: 0.16 s
Wall time: 0.18
\end{verbatim}
\end{enumerate}
\end{frame}

\begin{frame}
\frametitle{More precise plan}
With linbox having matured enough in the last year to be usable,
success is finally within reach!  I'm going to work very hard
on this during the next two weeks.  The plan
\begin{enumerate}
\item Create a good set of {\dred benchmarks and challenge problems}. These will
come from modular symbols, etc.  {\blue My project for today.}
\item Incorporate {\dred IML (integer matrix library)} into SAGE.
\item Polish, test, and tune new code Robert Bradshaw and I have been writing 
since this summer in SageX for {\dred fast dense echelon and matrix multiply}.
In particular, we must be able to completely turn off linbox with no loss
in functionality (since linbox is complicated and this helps with debugging).  
\item Incorporate as much of {\dred linbox's} functionality as we can.  NOTE: Linbox
is tricky to use, buggy in some ways, etc., so this squeezing full
value out of linbox is quite hard.  But it's well worth it, and everybody benefits. 
\item Build {\dred optimized algorithms} out of components available in linbox.  For example,
for dense echelon I think a wide range of tricks should be used together -- 
there's no one best algorithm. 
\item Improve interface to {\dred system solving} over exact base rings. 
\end{enumerate}
\end{frame}

\begin{frame}[fragile]
\vfill
\Large\bf
Linear Algebra in SAGE: Tutorial
\vfill
\begin{enumerate}
\item Matrices: 
\begin{enumerate}
  \item {\tt matrix} command, {\tt random\_matrix} command, via a {\tt MatrixSpace}
  \item Compute the following associated to $A$: kernel, inverse (if invertible), characteristic
polynomial, eigenspaces (and understand the output), the product $A A$, echelon form, 
Hessenberg form, determinant.
\item Create matrices form given rows or columns of $A$.  Make $A$ immutable.
\end{enumerate}
\item Vector spaces:
\begin{enumerate}
\item Choose a field $k$.  Create the $4$-dimensional vector space $V = k^4$ over $k$.
\item Create two three-dimensional subspaces $W_1$ and $W_2$ of $V$. 
\item Compute the intersection of $W_1$ and $W_2$.  Compute their sum.  
\item Express an element of $W_1 \cap W_2$ in terms of the basis for $W_1$ (using the
coordinates method). 
\item Do the above 3 steps with $k$ replaced by $\Z$. 
\end{enumerate}
\end{enumerate}
\end{frame}

\begin{frame}
\vfill
\Large\bf
Tour of Linear Algebra Source Code
\vfill
\begin{enumerate}
\item {\tt docs.py}; overall layout and design; levels of implementation functionality
\item Abstract base class for matrices: {\tt matrix0.pyx}, {\tt matrix1.pyx}, {\tt matrix2.pyx},
and {\tt matrix.pyx}. 
\item Dense and sparse base classses
\item Generic dense and generic sparse matrices
\item Dense and sparse matrices modulo $n$.
\item Dense matrices over $\Z$ and $\Q$.
\end{enumerate}
\end{frame}




\end{document}