\documentclass[11pt]{article}
\usepackage[square]{natbib}
\setlength{\bibsep}{1.6pt}
%\newcommand{\url}[1]{{\tt #1}}
\newcommand{\thisdocument}{Project Description}
\usepackage{url}
% bulleted list environment
\newenvironment{items}
{
\begin{list}
% {$\bullet$}
{$\cdot$}
{
\setlength{\itemsep}{.5ex}
\setlength{\parsep}{0ex}
\setlength{\leftmargin}{2.2em}
\setlength{\parskip}{0ex}
\setlength{\topsep}{0ex}
}
}
{
\end{list}
}
%end newenvironment
\include{macros}
\begin{document}
\begin{center}
\Large\bf
SAGE: Software for Algebra and Geometry Experimentation
\end{center}
%\tableofcontents
%\newpage
\section*{Major Points}
\begin{itemize}
\item SAGE is free open source software for
research in {\bf algebra}, {\bf geometry}, {\bf number theory},
{\bf cryptography}, and {\bf numerical computation}.
\item SAGE is an {\bf environment for
rigorous mathematical computation}
built using Python, GAP, Maxima, Singular,
PARI, etc.,
and provides a {\bf unified interface} to
Mathematica, Maple, Magma, MATLAB, etc.
\item There have been {\bf several successful SAGE workshops}, and
there are many active SAGE developers.
\item The primary goal of SAGE is to make
{\bf modern research-level algorithms}
available in an integrated package with
a graphical interface.
\end{itemize}
\section{Introduction}
SAGE is a project that the PI launched
in January 2005 to create a software
environment for research and experimentation in
algebra, geometry, number theory,
cryptography, and numerical computation.
This involves the creation of free open source
software and databases that support
advanced mathematical research.
%The SAGE development model
% and technology is distinguished by an
% emphasis on openness, community, cooperation, and
%collaboration.
%\begin{quote}
%``My name is Tiziano and I'm from Italy. I'm
%writing this mail first of all because I would
%like to thank you all for SAGE. It's something
%the world was really missing.
%Every free computer algebra system I've tried
%has reinvented many times the wheel without
%being able to build the car.''
%\end{quote}
The PI is one of the more sought-after people by the world-wide community
of mathematicians, for computational confirmation of conjectures,
for algorithms, for data, and for ways of formulating
problems so as to make them more accessible to algorithms.
He is also successful at bringing together a wide range of
people to work on collaborative mathematics projects; for
example, he
organized the MSRI workshop \cite{msri06modform}, two
NSF-funded SAGE Days workshops
\cite{sagedays1, sagedays2},
and will organize several more workshops during the next year
\cite{msri07parallel, sagedays3, aim07, banff07}.
He has extensive experience with software development,
having written HECKE, much of SAGE, and
over 25,000 lines
of code that are included in Magma.
\subsection{Prior Support}
The PI has used his startup money at UC San Diego and University of Washington,
his NSF grant (DMS-0555776), and the UW's VIGRE grant to
support two SAGE workshops, six undergraduate employees, four graduate
students, and research visitors.
{\bf Obtaining grant funding is critical to the
continuation of SAGE development at its present level.}
{\bf Other Grant Applications:} The PI has also applied this year to
the NSF CSUMS program to fund an {\em undergraduate education project}
entitled ``CSUMS: SAGE-Software for Algebra and Geometry Experimentation'',
and to the NSF ANTC program to support
his {\em computational and theoretical work} on the Birch and
Swinnerton-Dyer conjecture.
\section{SAGE and the Mathematical Software Landscape}
First we discuss the relationship between SAGE
and many high quality mathematical software packages.
Then we explain precisely what SAGE is and how it
unifies existing mathematical software via its
flexible interfaces. We also discuss
independent verification of research results,
free open source mathematics software, and the
SAGE development community.
%Many professional-grade
%software tools that support research in these areas are
%closed source and very
%expensive.\footnote{The list price for one personal
%non-academic non-government copy
%of Mathematica is \$\textbf{1880} (and \$3135 for certain architectures),
%for Maple is \$\textbf{1995},
%for MATLAB is \$\textbf{1900} (plus hundreds to thousands of dollars for
%each optional package), and Magma is \$\textbf{1150} (educational
%rate---the non-educational rate is not available online).}
\subsection{Mathematical Software}
In this section we briefly describe the closed source
programs Magma, Maple, Mathematica and MATLAB, and
discuss several open source programs.
{\bf Magma} \cite{magma} is a high quality, mature,
closed source program developed in Australia.
It is a non-free (indeed, quite expensive)
software package with a vast range of
functionality in number theory, algebraic geometry, arithmetic
geometry, graph theory, and group theory. It features a specialized
language for mathematics.
Magma has an excellent command line interface, though it
does not have a graphical user interface.
Magma has very limited support for numerical computation
and symbolic integration.
It is not possible for end users to define their
own datatypes, but the Magma developers are often responsive
to requests to add new datatypes to the C language core
for the next release of Magma.
In Magma it is easy to save the complete state of
a running Magma session, though there is no
way to evaluate arbitrary strings, so it is difficult
to store to disk individual objects that one has computed.
Magma's huge and highly optimized library is far more
powerful and comprehensive for research in certain
areas (e.g., arithmetic geometry, group theory, coding
theory) than perhaps anything else available.
Much of Magma is written in C, so it can link in functionality
from some existing C libraries (e.g., GMP), though such
linking is only possible by rebuilding Magma and end users
are not allowed to build Magma from source. Also, many freely
available libraries cannot be legally linked to Magma because of
license restrictions.
{\bf Maple} \cite{maple} is a powerful closed source commercial program
developed in Canada. It features a sophisticated graphical
user interface, and has a wide range of functionality,
especially for symbolic computation and plotting
relevant to undergraduate education. Its programming
language is also highly regarded.
Much of the source of Maple is distributed with Maple and can be viewed
by users, though unfortunately such interpreted source files
can run slowly (see Section~\ref{sec:foss});
some arithmetic and many functions related
to number theory are notably slower than the corresponding
functions in Magma (see Section~\ref{sec:flint}).
{\bf Mathematica} \cite{mathematica} is an optimized,
closed source, commercial mathematics software
package developed in the USA. It has a unique mathematical
programming language, a vast library
of optimized special functions, powerful symbolic
manipulation capabilities, and sophisticated 2 and 3-dimensional
plotting. It also features a pioneering
graphical user interface. In many areas it has substantial
coverage of important algorithms, though in number theory,
arithmetic geometry, and cryptography, it has limited
functionality.
{\bf MATLAB} \cite{matlab} is closed source commercial
software developed in the USA, which focuses on
numerical computation. It has a wide range of functionality
for numerical computation,
excellent performance, a graphical user interface,
and a custom programming language. It also has symbolic
computation capabilities via a link to Maple's symbolic engine.
{\bf GAP} \cite{gap}, {\bf PARI} \cite{pari},
{\bf Singular} \cite{singular}, {\bf Macaulay2} \cite{macaulay2}
and {\bf Maxima} \cite{maxima} are large, mature, high
quality, free, open source mathematics software programs.
All are currently supported and under active development.
There is surprisingly
little overlap between their functionality (except
Macaulay2 and Singular). For example, GAP
has sophisticated functionality for computing with
groups, but limited support for commutative
algebra or number theory, whereas Singular has
a huge range of commutative algebra functionality
and PARI has substantial number theory
functionality but little group theory or commutative algebra.
\begin{table}[h]
\begin{center}
\caption{There is little overlap in functionality among free math
software\label{tab:probs}}\vspace{1ex}
\begin{tabular}{|l||l|l|l|l|}\hline
{\bf Function } & Singular & Gap & PARI & Maxima \\\hline
Multivariate polynomial factorization & Yes & No & No & Yes\\\hline
Subgroup enumeration & No & Yes & No & No \\\hline
Class groups of number fields & No & No & Yes & No \\ \hline
Symbolical integration & No &No & No & Yes \\\hline
\end{tabular}
\end{center}
\end{table}
SAGE incorporates all four programs listed in Table~\ref{tab:probs} (and
many others) into a single unified program so it does
all the listed problems well.
Every mathematics software system described above
has its own special-purpose programming language.
Many of these languages make it easy to express
mathematical concepts and get results quickly.
Unfortunately, most do not support modern exception handling
(like that available in C++, Java, and Python),
name spaces and many cannot be extended with new
data types (or classes).
For example, PARI's programming language is
useful for writing short programs but
awkward for large projects.
In addition, these special purpose mathematics languages
can be difficult to
use when one needs to do non-mathematical programming
(e.g., create
a web server to distribute the results of computations,
or connect to an online database or web page and parse
the results).
Some of the closed source systems, most notably recent
versions of Mathematica and MATLAB, make use of multiple
processors on a computer when available. None of the
open source programs listed above do. Tightly
integrated support for parallel computation is a key
goal of SAGE.
%Much more in this direction will likely be done, though
%such retrofitting for massive libraries is likely
%to be difficult, and require substantial new research.
\subsection{SAGE: A Unifying Approach}
SAGE is
\begin{enumerate}\setlength{\itemsep}{-0.5ex}
\item A {\bf distribution} of free open source mathematics software,
\item A {\bf new interpreter, graphical user interface, and library} of implementations of mathematical algorithms,
\item A {\bf better way to use} existing mathematics software together.
\end{enumerate}
\subsubsection{A Distribution of Math Software}\label{sec:dist}
SAGE is a cohesive distribution of several dozen pieces of open source
mathematics software, with almost no external dependencies,
which can easily be built completely from source
with one command on OS~X, Linux,
and Windows. Creating this distribution has required the combined
work of numerous specialists in the arcane build processes
of different operating systems, and requires regular
maintenance (which would be funded by this proposal)
to remain up to date. The PI has often been
told by mathematicians that various open source
programs, e.g., PARI and Singular, can
easily be built as part of SAGE, but are ``impossibly difficult''
for them to build without SAGE.
The PI also distributes prebuilt binaries of SAGE
for some of these platforms.
The PI is requesting
funds in order to regularly {\bf purchase new hardware}
for testing automated building of SAGE from source on a wide
range of platforms, and building binaries.
The PI used \$38,000 in funding from
NSF grant (DMS-0555776) for the purchase of a 16-core
computer with 64GB RAM that is the main home for SAGE development.
But a much wider range of equipment
is needed to test and optimize implementations of algorithms
on diverse hardware.
The PI must own such hardware in order to have
dedicated access to it for intensive testing of new implementations; moreover,
regular compilation of SAGE from source is resource intensive.
Also, in many cases (e.g., Itaniums) it is nearly impossible
to gain sufficient access to hardware without purchasing
that hardware. Finally, it is important to test building of SAGE
on both a range of hardware and operating system installs, which
requires owning the hardware.
\subsubsection{A New Interpreter, Graphical Interface, and Library}
SAGE improves on the existing systems by using the Python
programming language, which is a popular, mainstream, open source, free
programming language with support for programming
constructs that are useful in mathematics, such as user-defined classes, list
comprehensions and regular expressions.
SAGE can be used interactively
from the SAGE command line \cite{ipython},
via the SAGE Notebook,
and as a library from Python and C/C++ programs.
%One can use C libraries from SAGE.
As mentioned before, the other major mathematics software packages
have their own custom programming languages.
This can be particularly costly to occasional and beginning users of
mathematical software, as well as those whose work straddles
several mathematical subdisciplines. The use of Python for SAGE
avoids
this problem.
%In particular, the Python language has first-rate exception
%handling capabilities and powerful
%introspection capabilities (i.e., one can easily determine
%all methods available for an object at runtime, view the documentation
%or implementation of any function, etc.).
%Users can define their own new datatypes,
%both via the Python interpreter and via SageX (which results
%in fast new types with minimal overhead).
Moreover, because Python has
long been used for database and web programming applications,
it provides excellent support for
saving and loading of individual objects and network programming.
Also Python has a massive standard library and active
development community that is constantly optimizing the language
and moving it forward.
The SAGE Notebook is a sophisticated web-browser based graphical user
interface, which the PI created in response to student demand.
Graphical output can be easily embedded in
the notebook, and the notebook can be used as a front end for
many other mathematical software systems that do not have a
graphical interface, including Magma, PARI, and Singular.
The PI intends to use funds
to improve the robustness and
security model of the notebook using Twisted \cite{twisted}.
The PI hopes to include support in SAGE for practical
parallel computation at several different levels. For
example, the PI is chairing the organizing committee of the
upcoming MSRI
workshop ``Interactive Parallel Computation in Support of Research in
Algebra, Geometry and Number Theory'' \cite{msri07parallel},
which he funded using a grant from the National Geospatial Agency.
Also he has employed Yi Qiang for
several months to design and implement functionality for coarse grained
parallelism that is tightly integrated with SAGE.
The PI also hopes to use this grant to fund work by
SAGE developers to create highly
optimized new code for SAGE for basic arithmetic,
number theory, algebraic geometry,
arithmetic geometry, cryptography, graph theory, numerical computation,
and group theory (see Sections~\ref{core}--\ref{ntalg}).
%The several thousand
%examples in the SAGE reference manually are automatically tested to
%verify that the output is precisely as claimed.
\subsubsection{Using Existing Mathematical Software from SAGE}
The PI invented and implemented for SAGE a new way to create
and work with numbers, matrices, vectors, polynomials,
graphs, functions, and all other mathematical objects defined
in other mathematical software,
including Axiom, Maple, Mathematica, Macaulay2, Magma, MATLAB,
Octave, Maxima, Singular and PARI.
These interfaces are mostly implemented using pseudo-ttys and files,
so they can be created for any program with a command line
interface, and it is not necessary to make any changes to that program.
A running instance of SAGE can thus simultaneously orchestrate dozens
of other mathematics programs. This
gives SAGE a rich range of features, and makes it possible
for researchers to use SAGE while still using the other systems
they are accustomed to.
The PI would use support from this grant to hire graduate
students to create new SAGE interfaces to PHCpack,
Bertini, 4ti2,
REDUCE, CoCoA,
and many other significant pieces of mathematical software
(both free and commercial). Though each interface is initially
fairly straightforward to write, it is crucial that the author
have intimate knowledge of the functionality and mathematics behind
the program being interfaced with, and students are often
experts in them.
\subsubsection{Support for Specialized Programs}
An exciting aspect of SAGE is how it
makes it easy to make use of small
special purpose programs for mathematical research
as part of a larger project. For instance, in
low-dimensional topology,
algebraic combinatorics, and number theory (see \cite{ntw:calc}),
there are numerous specialized programs which
compute one or two things.
Often, research projects involve using several of these in conjunction with larger software packages.
\begin{quote}
``A recent project used:
\begin{items}
\item Snap, a version of the 3-manifold SnapPea library with PARI,
\item KhoHo, for computing Khovanov homology of links in $S^3$,
\item PHCpack, the polynomial equation solver, and
\item Mathematica.
\end{items}
In the past, I've always done this with Python scripts, but there was always a lot of overhead in translating back and forth between the various programs, and this was limiting in a lot of ways because {\em Python understands so little about mathematics}. (Using e.g. Magma or Mathematica as the ``core'' program never seemed to work very well because the file input/output functionality is poor, as well as the weakness of custom data-structures.)
{\em SAGE makes this so much easier}.''\\
\mbox{}\hspace{15em} --- Nathan Dunfield, Caltech
\end{quote}
The PI would use funds from this proposal to invite authors or
major users of some of these specialized programs as month-long
visitors, during which time they would turn the programs into
integrated components of SAGE.
\subsection{Independent Verification of Research Results}
%In many cases it is desirable to check computational
%results with at least two separate programs:
\begin{quote}
``One should always have at least two proofs of any result.''
\hfill-- J-P. Serre (personal communication)
\end{quote}
Many algorithms in number theory and cryptography, e.g.,
$3$-descent on elliptic curves, modular forms computation, quaternion
algebras arithmetic, and fast arithmetic on Jacobians of curves
are implemented only in Magma. Having
an independent implementation of these algorithms will help
increase our confidence in computational results.
%If one spends
%years trying to prove a conjecture motivated primarily by numerical
%evidence, it
%is helpful to verify the relevant
%motivating computations in two separate
%pieces of software.
%In some areas of mathematics this is possible,
%but in arithmetic geometry (the PI's research area) it
%often is not.
SAGE addresses Serre's remark both by providing new implementations
of algorithms currently available in only one place, and by
making it easier to run a computation in more than one system
and compare the results.
%Note that computational arithmetic geometry provides many of the
%tools that are crucial for modern cryptography research.
\subsection{Free Open Source Software}\label{sec:foss}
%J. Neub\"user \cite{neub} describes his
%view of the importance of free open source mathematics
%research software as follows:
\begin{quote}
``You can read Sylow's Theorem and its proof in Huppert's book in the
library [...] then {\em you can use Sylow's Theorem} for the rest of your
life free of charge, but for many computer algebra systems {\em license
fees have to be paid} regularly [...]. You press buttons and you get
answers in the same way as you get the bright pictures from your
television set but you cannot control how they were made in either
case.
With this situation {\em two of the most basic rules of conduct in
mathematics are violated}: In mathematics {\em information is passed on
free of charge} and {\em everything is laid open for checking}. Not applying
these rules to computer algebra systems that are made for mathematical
research [...] means {\em moving in a most undesirable direction}.
Most important: Can we expect somebody to believe a result of a
program that he is not allowed to see?''
\hfill-- J. Neub\"user \cite{neubuser}
\end{quote}
Though the {\em development of SAGE is very expensive},
SAGE itself is freely available, so researchers
that have limited software budgets are guaranteed access to SAGE.
The source of SAGE and all dependencies
are ``laid open for checking''; any part of SAGE
may be inspected, modified, and redistributed.
%Moreover SAGE is easy
%to build from source (see Section~\ref{sec:dist}).
Some non-free programs are partly implemented in an
interpreted language, and include this interpreted source code.
Unfortunately, due to their commercial
nature, there are restrictions when viewing such source files.
It may be illegal to read the implementation
of a function and use
what is learned in ones research:
\begin{quote}
``Without the express written permission of Maplesoft, Licensee shall
not, and shall not permit any Third Party to:
\begin{items}
\item[(a)] reproduce, transmit, modify, adapt, translate or create any
derivative work of, any part of the Software, in whole or in part, [...]
\item[(b)] reverse engineer, disassemble, or decompile the Software,
create derivative works based on the Software, or {\em otherwise attempt to
gain access to its method of operation or source code.}''
\end{items}
\mbox{}\hspace{10em} --- The Maple end user license agreement
\end{quote}
\subsection{The Development Community}\label{devs}
SAGE development is driven by a strong spirit of altruism,
openness, community, cooperation, and collaboration.
SAGE is a large project with over 30 developers: five
are undergraduate student employees, one is
a full-time employee, many graduate students work
on the project (three supported by the PI's
startup money), and there are numerous volunteers
in the USA, Europe, and Australia.
There were 571 posts on the sage-devel mailing list
during October 2006.
SAGE developers include Martin Albrecht (Bremen, Germany, grad student),
Tom Boothby (UW undergrad),
Robert Bradshaw (UW grad student),
Iftikhar Burhanuddin (USC grad student),
Craig Citro (UCLA grad student),
Alex Clemesha (UW employee),
John Cremona (Nottingham),
Didier Deshommes (North Carolina student),
Jon Hanke (Duke University),
William Hart (Warwick, UK),
David Harvey (Harvard grad student),
David Joyner (US Naval Academy),
Josh Kantor (UW grad student),
Emily Kirkman (UW undergrad),
David Kohel (Univ. of Sydney),
Kevin McGown (UC San Diego),
Bobby Moretti (UW undergrad),
Yi Qiang (UW undergrad),
Naqi Jaffery (UCSD undergrad),
Kiran Kedlaya (MIT prof),
Bill Page (top Axiom developer),
David Roe (Harvard grad student),
Steven Sivek (Princeton grad student),
Jaap Spies (The Netherlands),
Gonzalo Tornaria (Uruguay),
Justin Walker (retired Apple OS X developer),
Mark Watkins (Bristol),
Joe Wetherell (San Diego),
and Gary Zablackis (high school teacher).
The wide range of backgrounds of the contributors helps
ensure that SAGE is relevant to a broad constituency of students and
researchers.
\subsubsection{Advisory Board}
These people have agreed to serve on an advisory board,
which will provide feedback before the PI allocates
any funding from this grant:
\vspace{1ex}
\begin{items}
\item Tom Boothby (undergraduate, University of Washington)
\item David Harvey (graduate student, Harvard University)
\item Kiran Kedlaya (assistant professor, MIT)
\item David Joyner (professor, US Naval Academy)
\end{items}
\vspace{1ex}
\noindent{}All have contributed substantial code to
SAGE, and their range of backgrounds
and positions ensure that a wide
range of SAGE users are represented.
\subsubsection{Workshops}
The PI organized {\em SAGE Days 1} \cite{sagedays1},
which was a workshop at UC San Diego in
February 2006, which had about 40 participants and was funded by NSF
grant DMS-0555776. There were talks on a wide range of computer
algebra systems and software, ranging over pure and applied
mathematics, along with coding sprints.
In June 2006, the PI ran a
workshop \cite{simuw06} at UW for
high school students, in which they used SAGE to
investigate the Birch and Swinnerton-Dyer conjecture.
In August 2006, the PI ran a two-week workshop at MSRI \cite{msri06modform}
in which 30 graduate students, and 6 research mathematicians
worked together to design and implement a wide range of algorithms
in SAGE for computing with modular curves, modular forms, elliptic
curves and related objects.
In October 2006, the PI ran {\em SAGE Days 2} \cite{sagedays2}
at UW, which had about
40 participants, and was funded by NSF grant DMS-0555776. The main
topic of the workshop was improving the speed and robustness
of SAGE. There were 2 days of talks and
3 days of coding sprints, which initiated
numerous projects.
The PI has secured funding for four upcoming SAGE-related workshops:
the parallel computation workshop \cite{msri07parallel} at MSRI
in January 2007, Sage Days 3 \cite{sagedays3} at IPAM in February 2007,
a Banff workshop on computing modular forms in June 2007 \cite{banff07},
and an AIM workshop on databases of modular forms in July 2007 \cite{aim07}.
These workshops have been pivotal in the development
of SAGE, so securing funding for them is crucial.
The PI hopes to run four SAGE Days
workshops per year, and is requesting funding from
the NSF for one of these
workshops each year.
%, and is applying for other sources of funding
%for the other 3 workshops.
\section{Specific Goals}
In this section we outline some specific
projects that this proposal
would fund.
These include
% making it easier to use a wide range
%of {\bf small specialized programs} for research
%mathematics,
designing and coding fast core algorithms for
exact arithmetic, creating and implementing a wide range of
algorithms for number theory and cryptography
research, and improving SAGE's
visualization capabilities.
\subsection{Fast Core Arithmetic Algorithms}\label{core}
\subsubsection{Support for Optimized Compiled Code}
To implement a state-of-the-art mathematics software system,
it is crucial to have an easy-to-use language for writing
optimized compiled code, which integrates well with the
high-level interpreter.
SAGE accomplishes this using SageX, which is
a customized version of Pyrex \cite{pyrex}.
Using SageX, one can
write compiled programs, which are easy to use
from SAGE.
Programs written in SageX are converted to C, compiled,
and loaded at runtime.
The SageX language is similar to Python, and provides
easy access to both Python objects and arbitrary C and C++ functions.
The PI has done much to make SageX easier to use
in the context of SAGE, and intends to write more documentation
and implement new features. This proposal would fund work by
one computer science graduate student who is an expert
in compilers for one quarter to greatly improve the quality
of SageX.
SageX supports compilation during runtime, which can provide
huge speed gains to interactive users. For example, Tom Boothby
implemented a program so that when a polynomial
will be evaluated repeatedly, it can be converted to an optimized
SageX representation that is compiled and made available to
the user, all from the interpreter---this can speed up evaluation
by a factor of over 1000.
%High level parts of the SAGE library are implemented
%in pure Python, and
%programs written in Python are easier for users to debug, inspect, and modify.
%Currently about 50\% of the low-level arithmetic types in SAGE
%are partly implemented in pure Python, which is too slow.
%The PI intends to transition all low-level
%implementations that must be fast to SageX.
\subsubsection{A New Fast C Library for Number Theory}\label{sec:flint}
Much of the arithmetic in SAGE for number theory is currently based on
the NTL and PARI libraries. However, neither library is fast enough
to satisfy the PI's goals for SAGE. To address this
problem, two SAGE developers, William Hart and David Harvey, are creating FLINT,
which is a library written in C for number theory applications.
The PI is requesting funds to support
work on FLINT, and for William Hart to
visit UW for at least one quarter to work full time on FLINT.
Currently available libraries for arithmetic are not
fast enough for SAGE. In some cases the algorithms are not
asymptotically fast or their implementation is not
sufficiently optimized.
PARI's integer factorization is only
slightly better than Magma's on some platforms and well behind
the state of the art on all platforms. It also does not have the latest
algorithms in many cases. For example it does not have an
asymptotically fast Schoenhage-Strassen implementation for multiplying
polynomials.
NTL is a well written package, having set numerous
world records. However its implementation strategy makes
it difficult to get maximum performance from the GMP library,
and in some cases Magma contains much faster implementations
of core algorithms (see Table~\ref{tab:bench}).
%The PI hopes FLINT will supply a free open
%source library with performance equalling or exceeding all other
%packages (both free and non-free).
Neither PARI nor NTL support fine-grained parallel
computation, which is a severe
limitation as multicore multi-processor machines are becoming
common.
%The PI intends to build into SAGE low-level arithmetic
%support for such machines.
%The code in FLINT will be highly optimized for modern processors and will
%include automatic support for multicore and multiprocessor
%machines.
FLINT includes routines for integer factorization.
See Table~\ref{tbl:factor} for how long it takes a {\bf 1.8GHz Opteron}
to factor the $61$-digit number $pq$, where
$p$ is the next prime after $10^{29}$ and $q$
the next prime after $10^{31}$.
(These programs implement roughly the same algorithms; but
some implementations are clearly much more optimized than others.)
FLINT also contains an optimized Schoenhage-Strassen
polynomial multiplication
implementation, whose speed is illustrated in Table~\ref{tab:bench}.
\begin{table}[h]\vspace{-2ex}
\begin{center}
\caption{Time to factor a 61-digit number with two large factors\label{tbl:factor}}\vspace{1ex}
\begin{tabular}{|l|r|}\hline
{\bf Software} & {\bf Time (seconds)} \\\hline
SAGE (FLINT) & 16s \\\hline
PARI 2.3.1 & 54s\\\hline
MAGMA 2.13 & 63s \\\hline
Mathematica 5.2 (FactorInteger) & 299s \\\hline
Maple 10 (ifactor) & 715s \\\hline
\hline\end{tabular}
\end{center}
\end{table}
\vspace{-2ex}
\begin{table}[h]
\caption{10000 multiplies of two degree $255$ polynomials with 1000 bit coefficients\label{tab:bench}}
\begin{center}
\begin{tabular}{|l|r|}\hline
{\bf Software} & {\bf Time (seconds)} \\\hline
FLINT & 23s \\\hline
MAGMA 2.13 & 28s \\\hline
NTL-5.4 & 136s \\\hline
PARI 2.3.1 & 295s\\\hline
SINGULAR 3-0-2 & 839s \\\hline
Maple 10 & 2100s \\\hline
Mathematica 5.2 & 2075s \\\hline
GAP 4.4.8 & 2846s\\\hline
% Maxima 5.10.0 (clisp) & 5000s\\
%\hline
\end{tabular}
\end{center}
\end{table}\vspace{-3ex}
%As mentioned, Magma and PARI come with an interactive
%interpreter for programming at a high level. FLINT on
%the other hand is a C library which can only be
%linked to a computer program written in C.
%SAGE on the other hand, is a powerful interpreter written
%as an extension to Python, which can make use of any
%C library via SageX.
%SAGE uses many open source libraries, including NTL, GAP and PARI,
%to perform number theoretical, geometric and algebraic computations.
%Since SAGE can be linked to C libraries,
%FLINT can be directly used in all cases where faster implementations
%exist in the FLINT library than elsewhere. In particular,
%\textbf{FLINT can be used immediately} and the full functionality
%of the latest improvements provided by FLINT can become available
%almost immediately to users of SAGE.
%Thus FLINT does not have to provide coverage of a large
%set of number theoretic algorithms in order to be useful to
%a number theorist. This new approach, made
%possible by SAGE, speeds up the development
%cycle for mathematicians who cannot wait to have the
%best available performance in algorithms.
\subsubsection{Groebner Bases}
%The PI also intends for SAGE to include highly optimized implementation of
%arithmetic over the integers and rationals via the GMP
%library \cite{?}, real and complex numbers via
%MPFR \cite{?} and GSL \cite{?}, and exact real
%numbers via RealLib \cite{?}.
Groebner bases are central in commutative algebra,
just as echelon forms are central in exact linear algebra.
SAGE currently computes Groebner bases using either Singular
or (optionally) Macaulay2 or Magma (if available).
Magma is substantially faster at computing Groebner bases in
many cases than anything else available
(in particular, Singular, Macaulay2 and CoCoA).
One of the SAGE developers, Martin Albrecht, has
implemented Faugere's F4 algorithm for SAGE in some
cases, and achieved impressive results. The PI is
requesting student support for
Martin Albrecht to refine his F4 implementation
into what might become
the first {\em complete free} optimized implementation
of F4, since the other two complete implementations, Faugere's
and Magma's, are closed source and non-free.
%The PI also hopes to investigate parallel algorithms
%for Groebner basis computations (e.g,. \cite{?})
%G. Attardi and C. Traverso, "Strategy-Accurate Parallel Buchberger
% Algorithms", Journal of Symbolic Computation 21 (1996), 411-425
%See work of Kathy Yelick.
%\begin{items}
%\item Complex numbers -- mpfr, use pari for special functions, maybe use mpc??
%\item Reallib -- exact arithmetic with real numbers
%\item Groebner Basis Computation
%[[ask Martin Albrecht]] say something about parallelization
%\begin{items}
%\item In the original F4 paper Faugere states that he has implemented a first version of a parallel F4 algorithm
%\item G. Attardi and C. Traverso, "Strategy-Accurate Parallel Buchberger
% Algorithms", Journal of Symbolic Computation 21 (1996), 411-425 (I haven't
% read it yet)
%\item Every parallelism of sparse matrix row echelon computation aids F4
%\item Kathy Yelick -- "she's been working
%on this for years"
%\item $p$-adic numbers: custom (via GMP)
%\item Laurent series: custom
%\item Power series: custom
%\item Multivariate polynomials: Singular, CoCoAlib.
%\end{items}
%\end{items}
\subsubsection{Asymptotically Fast Exact Linear Algebra}
Sparse and dense exact linear algebra is the bottleneck in
many algorithms in graph theory, group theory, combinatorics,
number theory, and other areas.
Unfortunately, no existing free libraries meet the quality, speed
and functionality requirements for SAGE (none approach the
speed or functionality of Magma overall),
so we propose to put substantial effort into optimized
asymptotically fast sparse and dense exact linear algebra.
The PI, David Harvey
and Robert Bradshaw have designed and implemented
asymptotically fast block echelon and matrix multiplication
algorithms, but much optimization work remains to be done.
The PI is requesting funding for
graduate students to further optimize the implementation,
add sparse and dense support for many rings and fields,
and design and implement new multimodular
linear algebra algorithms over cyclotomic fields.
\subsubsection{Numerical Computation}
Support in SAGE for numerical computation is crucial.
Computation of special functions, Fourier transforms,
and numerical linear algebra all play a role in number theoretic
computations.
Efficient algorithms for computing exact algebraic
objects, e.g., Bernoulli numbers and models for curves,
often proceed by computing numerical approximations, and
algebraic problems can sometimes be solved (with proof)
more efficiently
via numerical methods.
Support for numerical computation also
expands the range of people who can benefit from
SAGE.
% (e.g., 290 theorem \cite{} and mention my involvement).
SAGE includes numpy \cite{numpy}, which is a
mature and well supported Python library for numerical matrix computations.
SAGE also includes the GNU Scientific Library \cite{gsl},
which is a C library that provides a wide range of numerical
algorithms. The PI is requesting funding to hire a graduate
student to design and implement substantial new algorithms and
code
for SAGE to make it easier to use
numpy, scipy \cite{scipy}, and GSL to support algebraic computation.
% from SAGE.
%There will be fast transformations of matrices, vectors, polynomials, etc.,
%over the rational numbers to matrices with numerical
%entries.
%The Python scientific computing community has created scipy.
%This library is easily available to any SAGE user, but we
%think even more is needed, since scipy is not designed in a way that
%fits into the SAGE's structured algebraic organization.
%Instead SAGE includes the GNU Scientific
%Library (GSL) \cite{} which is extremely robust and mature.
%We intend to write an interface that fits perfectly into the SAGE
%setup, but provides extensive integrated support for visualization,
%and provides fast transalation between SAGE and SciPy objects.
%
%\subsection{Interfaces with Maple, Mathematica, MATLAB, etc.}
%\label{sec:interfaces}
%
%We intend to create interfaces to CoCoA,
%4ti2, PHCpack, Bertini, REDUCE, etc.
%\subsubsection{Robustness and Speed}
%[[propose to make interfaces to certain systems with identical interfaces
%but much more robust via specialized client/server support. Say something
%about the options for Maple, Mathematica, Magma, etc.]]
%%Unfortunately, in some cases it is technically possible to create
%%better interfaces, but the relevant commercial systems view
%%SAGE as a competitor, so they will not help or cooperate.
%\subsubsection{Introspection}
%[[magma -- add code to the core to make it easier]]
%[[which systems need more]]
%
%\subsubsection{Summary}
%The proposed core arithmetic of SAGE will be based
%on GMP for fast multiprecision computations.
%Code will be highly efficient and optimized for modern microprocessors,
%and future releases of SAGE will provide enhancements to take advantage of
%multicore and multiprocessor systems.
%We will implement asymptotically fast algorithms for basic
%ring and matrix arithmetic.
\subsection{Advanced Number Theory Algorithms}\label{ntalg}
\subsubsection{Modular Forms and Modular Abelian Varieties}
The PI has done
much work on modular forms computations in his thesis and for
Magma and published a book on computing with modular
forms \cite{ stein:modform}.
The PI proposes to create an optimized,
flexible package in SAGE for computing with
modular forms for general congruence subgroups of
${\rm SL}_2(\Z)$. He would also like to create a package
for computing with half-integral weight and weight 1
modular forms that uses a combination of Gabor Weise's
new algorithm and Tate's classical algorithm.
Jointly with Lassina Dembele and David Kohel, the
PI intends to implement algorithms of John Voight and
others for computing
with quaternion algebras that will be used to
compute both classical and Hilbert modular forms.
With Robert Pollack, the PI intends to implement
algorithms for computing with $p$-adic modular
forms and $p$-adic $L$-functions, especially algorithms
building on Glenn Steven's work on $p$-adic modular symbols.
The PI would also like to implement a range of trace
formula algorithms for investigating $p$-adic modular forms.
The PI would use funds from this proposal to
invite John Voight, Lassine Dembele, David Kohel,
and others to UW to help with implementations.
%He has implemented bits
%and pieces of all the above algorithms over the years,
%and he initiated SAGE to eventually provide a single place
%for an optimized implementation of all these algorithms.
%\subsubsection{Modular Abelian Varieties}
The PI has done work on explicit computations with
modular abelian varieties, including creating a package
for computing with them that is included with Magma.
Working with Jordi Quer (of Barcelona),
he intends to implement in SAGE a package for computing
with modular abelian varieties over $\Q$ and over number
fields. This involves decomposition into simple factors,
computation of endomorphism rings,
isomorphism testing, computation of period lattices
and defining equations (Jacobians, low genus), and
special values of $L$-functions.
\subsubsection{Elliptic and Hyperelliptic Curves}
The arithmetic of elliptic curves is a rich central
area of number theory. SAGE currently includes a wide
range of functionality, and we hope to add
more, and improve the quality of what is there now.
SAGE includes Denis Simon's program for algebraic
2-descents, but does not take full advantage
of its functionality yet. Cremona's mwrank program
\cite{mwrank} is also included in SAGE, but some of its
functionality has not been exposed to the SAGE interpreter.
There has been a major thrust to
use $3$, $4$, and even $12$ descents to compute Mordell-Weil
groups of elliptic curves. All current implementations
of these methods are part of Magma---there are no independent
or free implementations, though the algorithms
are published in recent Ph.D. theses and papers.
The PI would use money from this proposal to
fund SAGE implementations of these algorithms.
%Another major trend in elliptic curve computation is the use
%of Heegner points, both for computing Mordell-Weil groups and
%for investigations into deep conjectures of Kolyvagin, Mazur,
%Rubin, and others. The PI has done recent work with Jetchev
%and Lauter on such algorithms, and intends
%to implement them in SAGE.
%
%For investigations into $p$-adic $L$-functions and
%$p$-adic analogues of the Birch and Swinnerton-Dyer
%conjecture, it is crucial to have fast implementations
%of algorithms for
For cryptographic applications, SAGE requires
optimized implementations of algorithms for computing
with Jacobians of hyperelliptic curves. David Kohel
has implemented preliminary algorithms in this direction
for SAGE, and the PI intends to optimize these
so that they are useful for serious research.
%
%Denis Simons
%\begin{items}
%\item 2-descent: invariants (mwrank), algebraic (Simon's program)
%\item 3-descent: port what Michael Stoll implemented in Magma
%\item 4-descent: port what's in Magma (Tom Womack's thesis)
%\item Heegner points: Mark Watkins's work
%\item Point counting: PARI, French team
%\item Elliptic curve factorization method (ECM)
%\item Cremona's database
%\item Stein-Watkins database
%\item Values of $L$-series: Dokchitser
%\item Zeros of $L$-series: Rubinstein
%\end{items}
%\subsubsection{Hyperelliptic Curves}
%\begin{items}
%\item Arithmetic
%\item Kedlaya's Point Counting algorithm
%\end{items}
\subsubsection{Databases}%
Though SAGE already has many
databases, including Sloane's tables \cite{sloane} of integer sequences and
Cremona's tables \cite{cremona:onlinetables} of elliptic curves,
the PI intends to greatly expand the range of databases
available in SAGE. This will mainly involve creating
new databases related to the PI's research, including
databases of modular forms, elliptic curves,
modular abelian varieties, and
special values of $L$-functions.
\subsection{The SAGE Notebook: Graphics and Visualization}
The SAGE notebook is implemented as a Python-based
web server that interacts
with numerous SAGE instances (one for each running worksheet).
The user interface to the notebook
is implemented using Javascript in a web browser.
%
%Wiki-like functionality
%Logins, Text format, tracking of changes (diffs),
%Robustness
%Twisted (async web server), ssl, running of worksheets in
%%jail.
%\subsubsection{Browsing Documentation}
%In Python functions are attached to objects, so it is easy to obtain a list of
%all functions that can be called on an object. Currently, in the notebook
%typing, e.g., {\tt X.[tab]} pops up a list of all of X's functions. One can
%then easily get documentation for any given method, but it is in plain text.
%We intend to make the documentation available in a typeset form, so that
%the numerous examples can be clicked on in order to easily have them copied
%into an input cell. Moreover, we intend to make the documentation full
%text searchable from within the notebook by creating a B-tree index of the
%documentation each time a new version of the SAGE library is installed
%(high-performance B-trees are part of ZODB \cite{}, which is a
%component of SAGE).
%\subsubsection{Browsing Source Code}
%SAGE is open source, so it is crucial that it is easy for any user
%to see the source code of any function they are using.
%If {\tt f} is any Python function, typing {\tt f??} in the notebook currently
%lists the source code of {\tt f} as plain text. This does not work if {\tt f} is
%defined in Pyrex code, and there are difficulties in implementing
%source code viewing for such functions, which we hope to overcome.
%We hope to format the source code using syntax highlighting (Python
%provides parse trees).
%%Also, when Pyrex code calls C-library code,
%%we hope to make that source code easily available as well, which will
%%require different methods, e.g., c-tags, depending on the relevant
%%library.
There are three categories of graphics and visualization
that must be addressed for SAGE: static graphics embedded
in the notebook, dynamic graphics in the notebook, and
dynamic local graphics that do not use the notebook.
Matplotlib \cite{matplotlib}, which is included with SAGE,
provides 2d graphics with an interface very similar to MATLAB's.
Alex Clemesha, a full time employee
doing SAGE development, has used matplotlib to implement static
2d graphics with a Mathematica-like interface,
which embed nicely in the notebook. For example, the PI
used this package to illustrate Mazur's recent
Nature article \cite{mazur:nature}.
There is
some support for 3d rendering in matplotlib, and Clemesha
intends to create a similar Mathematica-like interface
for 3d graphics.
For high quality static rendering of 3d images, SAGE includes
a multi-threaded
3d ray tracer \cite{tachyon}, which produces beautiful 3d images with
shadows, transparency, and reflections.
%The PI intends to make it so exactly the same 3d scenes
%can be rendered using either Tachyon or the 3d rough draft
%renderer of \cite{sec:mpl}.
For dynamic graphics in the notebook, the PI intends to either
find or hire a student to write a free open source Java applet that can
display a scene involving mathematical primitives,
and allows for dynamic rotation and scaling.
For interactive local graphics not using the notebook,
Mayavi \cite{mayavi} is an excellent
solution.
%The PI intends to improve support for using
%Mayavi with SAGE.
%The PI also intends to add plot methods to a wide range of objects in SAGE.
%For example, matrices will be plotted as a grid of normalized squares
%or a surface in space. Many other objects, e.g.,
%finite fields, elliptic curves, modular forms, finite groups, etc.,
%will all have graphical representations.
\section{Justification for Funding}
The primary goal of SAGE is to make a wide range
of modern research-level algorithms
available in a high quality, easy-to-use, integrated package with
a graphical interface.
Tables~\ref{tbl:factor}--\ref{tab:bench}
and the discussion of advanced research algorithms above illustrate
that this has not yet been achieved by any free or commercial
software. The commercial programs have several million dollar
per year revenues, but do not address the research needs
of our community; for SAGE to achieve similar quality
while serving the needs of researchers requires significant funding, and until
SAGE is much more established, grant funding is the primary source.
The PI hopes that in three years
SAGE will be sufficiently pervasive that
SAGE development can be funded by a foundation
that receives donations and support contracts.
Until then {\bf NSF funding is critical}.
%\newpage
\bibliographystyle{amsplain}
\bibliography{biblio}
\end{document}