\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}