Projects
\section{Proposed Sage Days Workshops}
In the following sections we describe $N$ [[update when done]]
proposed Sage Days workshops. The general format is about 5 days of
intensive work by about 20 highly-motivated participants, which often
leads to substantial additional work and research as a result of the
workshop. We describe below how each project fits into the thrust of
Sage development and builds on existing work.
\subsection{Sage Days: The Notebook Interface}
\subsubsection{Background}
\begin{wrapfigure}{r}{0.5\textwidth}
\shadowbox{\includegraphics[width=0.5\textwidth]{sagenb.png}}\\
\end{wrapfigure}
Imagine an interactive web-based worksheet in which one can enter
arbitrary Sage commands, see beautifully typeset output, create 2D and
3D graphics, publish worksheets, and collaborate with other users.
The Sage notebook is the only math software that offers this
capability; it is somewhere between a Maple or Mathematica notebook
and the online Google Documents web application, with its extensive
collaborative features.
The PI and several UW undergraduates together developed the basic
implementation of the current version of the Sage notebook during an
extremely intense three-week coding session in Summer 2007.
Many mathematicians in both pure and applied mathematics at dozens of
universities around the world are excited about how they can leverage
the Sage notebook in their own research and teaching. There is much
excitement about this being a new collaboration tool that enhances
their teaching and research. For example, the FEMHUB project
\url{http://femhub.org/} at University of Nevada has adopted and
rebranded the Sage notebook for teaching courses and doing research on
finite element methods. See \url{http://wiki.sagemath.org/sagenb} for
a list of deployed notebook servers.
\subsubsection{The Workshop}
At a Sage Days workshop on the Sage notebook, we would attack the
following problems:
\begin{enumerate}
\item Address all {\em known security vulnerabilities in the Sage
notebook}, and implement a more sophisticated user security model.
Yoav Aner, a cryptography graduate student in London, has written an
extensive threat assessment for the notebook as his Masters Thesis,
which provides a list of issues to tackle.
\item Add complete {\em spreadsheet capabilities} to the Sage
notebook. This would be similar to Microsoft Excel spreadsheets,
but the formulas would be Sage code. This could be extremely
powerful for applications that are very data-centric, yet involve
advanced mathematics.
\item Add sophisticated {\em software engineering capabilities} to the Sage
Notebook. This could include integrating a sophisticated code
editor (such as BeSpin \url{} or [[something else]]), providing an
interface to the Sage libraries revision control system and the
capability of editing any files in the Sage library, checking in
changes, creating and submitting patches, etc., all from the Sage
notebook interface. This would also included creating a
sophisticated web-based interactive debugger, which would provide
access to the Python debugger, the Python profiler, the GNU C
debugger (gdb), and Valgrind.
\item Create a {\em repository for contributions} to Sage. This would
provide a central location for people to manipulate, share, and
publish Sage worksheets, and Python and Sage code. These materials
could be rated by other users, there could be an RSS feed of new
contributions, etc. This would be a Sage-specific analogue of
Google Code, Sourceforge, and many of the other popular open source
project hosting sites.
\item Implement {\em additional 3d plotting functionality}. There are
many functions and options for 3d plots that have not yet been
implemented, and this could be done. Also improve Sage's ability to
render using HTML5's canvas, including animation output, as
something that can be embedded in a webpage, or viewed separately.
This is an open-ended project, but 1 month fulltime would provide
enough time to improve implicit plotting, options for parametric and
function plotting, and for adding text rendering and axes to canvas
rendering.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Software Engineering}
\subsubsection{Background}
Sage is big. The printed reference manual is over 4,000 pages. Sage
is the largest active software engineering projects currently under
development by the mathematical community. Several Sage developers
are experienced software engineers, some with over a decade of
experience in industry, and as it grows the project has benefited
greatly from their input.
Sage consists of well over {\em 5 million} lines of code from 97
distinct packages. This entire systems builds in a completely
automated way from source on over 20 supported platforms (many flavors
of Linux, OS X, and Solaris 10), using a cross-platform build system
that we created using standard tools (autoconf, scons, make, bash).
\begin{wrapfigure}{r}{0.4\textwidth}
\shadowbox{\includegraphics[width=0.4\textwidth]{tickets.png}}\\
\mbox{}\,\,\,\,\,Over 1200 Open Tickets...
\end{wrapfigure}
The core Sage library, which we have written over the last few years
is, well over 400,000 lines of Python, Cython, C/C++ code, and
documentation. We regularly run a test suite that involves evaluating
over 100,000 lines of input examples and verifying that the output is
correct, with care taken to initialize random seeds before each test.
This test suite is often run in parallel (thanks to the NSF/REU-funded
work of undergraduate Gary Furnish), and it covers 80\% of the
functions in the Sage library (that is about 18,000 functions).
We use the Mercurial distributed revision control system to track all
changes to the Sage codebase. All new code that goes into Sage is
publicly subjected to a rigorous peer review process which is
organized using Trac (\url{http://trac.sagemath.org}). Since January
2007 [[??]], We have closed about 6,000 [[??]] tickets using this
system, and there are 270 [[update!]] trac user accounts.
\subsubsection{The Workshop}
At a Sage Days workshop on software enginnering, we would attack the
following problems:
\begin{enumerate}
\item Create a \emph{benchmarking and regression testing system} for
Sage, which can record and compare timings automatically between
different versions of Sage. Once this system is in place, create a
large battery of tests based on the current Sage library, to prevent
any future speed regressions in Sage. This should also be completely
usable for end-user code, so that users can maintain their own list
of timing tests. This is approximately one and a half weeks of
fulltime work, split evenly between creating and debugging the
regression testing system, and writing a thorough set of benchmarks
for the Sage library.
\item \emph{Improve support for testing end-user code} via the Sage
doctest system. Support for this exists in Sage, but often has bugs
or inconsistencies in behavior. The most important part of this
project would be creating a script which \textbf{tests} this
behavior, and making it a part of the standard Sage test suite.
\item Create an \emph{automatic patch-testing system} to monitor and
report on the correctness of patches posted to the Sage bug
tracker. Several Sage developers have recently created a script to
automatically merge and test patches. This project would consist of
creating a daemon to run on a large server (such as
\url{http://sage.math.washington.edu}) which will monitor the Sage bug
tracker, and when new patches are posted, merge and test them, then
report the results back to the bug tracker. This is currently done
manually by Sage developers as part of the code review
process. Automating this process would free up a huge amount of
developer time, since they would no longer need to do this
themselves, and it's a task that's easily automated. Three weeks
fulltime. One week to create the daemon program, one week to cleanly
integrate it with trac (the software behind Sage's bug tracker), and
one week to monitor and adjust its behavior to be functional without
making the server unusable.
\item Improve the Cython \emph{Python-to-C compiler}: There are
numerous proposals on the Cython wiki
\url{http://wiki.cython.org/enhancements} for possible projects. In
particular, we would love to see continued improvement in Cython's
support for wrapping existing C/C++/Fortran libraries, since Cython
is becoming increasingly important not only for the Sage project,
but also for both NumPy and SciPy, which are the key tools for
scientified computing using Python.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Commutative and Noncommutative Algebra}
\subsubsection{Background}
[[background about commutative and noncommutative algebra capabilities and development
in sage]]
At a Sage Days workshop on commutative and noncommutative algebra, we
would attack the following problems:
\begin{enumerate}
\item Implement {\em modules over multivariate polynomial rings}.
This would be relatively straightforward to do by building on the
functionality already offered by Singular.
\item Create an optimized Cython implementation of {\em free algebras and
their quotients}.
\item Implement computation with {\em modules over Dedekind domains} (via
pseudobasis), as explained in detail in Henri Cohen's GTM book on
explicit class field theory.
\item Implement {\em arithmetic and ideal theory of quaternion algebras
over number fields}, following the algorithms and strategy John
Voight used for his Magma implementation. This assumes the project
above for computing with Dedekind domains using pseudobasis has been
completed.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Algebraic Curves}
\subsubsection{Background}
\begin{wrapfigure}{r}{0.3\textwidth}
\shadowbox{\includegraphics[width=0.3\textwidth]{algcurve.png}}\\
\mbox{}\,\,\,\,\,\,An Algebraic Curve
\end{wrapfigure}
[[background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
background about algebraic curves capabilities and development in
sage
]]
\subsubsection{The Workshop}
At a Sage Days workshop on algebraic curves, we
would attack the following problems:
\begin{enumerate}
\item Implement Florian Hess's algorithms for {\em algebraic number theory
in the context of function fields}. This would include implementing
computation of Riemann-Roch space basis computations for smooth
projective curves.
\item Document all existing functionality for {\em algebraic curves} in
Sage, and fill in all the generic missing functionality.
\item Provide {\em resolution of singularities of algebraic curves} by
wrapping functionality already available in Singular
(see \url{http://www.singular.uni-kl.de/Manual/3-0-4/sing_574.htm}).
\item Implement code for {\em computing with rational (genus 0)
curves}, since Sage currently doesn't have any special code for
them. These are mostly ``easy,'' but there are a couple of
important algorithms, which are mostly avialable in components
included in Sage (as part of eclib and Denis Simon's PARI code). So this
would mainly be a wrapping and documentation project.
\item Implement {\em 3-descent and 4-descent algorithms} for finding
rational points on elliptic curves over $\mathbf{Q}$. There are no open
source implementations of any of these algorithms, and they are
central to finding rational points on elliptic curves.
\item Create {\em optimized implementations of all pairings} on elliptic
curves over finite fields: Weil, Tate, EtaT, Etaq, Ate, ReducedAte,
and Ateq.
\item Implement algorithms for computing with {\em elliptic curves over
function fields}. John Cremona remarks that ``Quite a bit of what
Magma has came from my student David Roberts, whose thesis in 2007
was about this. I have his code.''
\item Implement all the {\em standard models of genus 1 curves} (as
defined by what Magma supports), and transitions between them.
Also, implement Edwards (and other) coordinates for elliptic curves.
\item Optimize arithmetic on {\em Jacobians of hyperelliptic curves}.
\item Jacobians: Implement {\em 2-descent on Jacobians of hyperelliptic
curves} over $\mathbf{Q}$.
\item Computation of {\em automorphism groups of smooth projective curves}
of genus $\geq 1$.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Number Fields}
\subsubsection{Background}
[[background about number field capabilities and development in
sage]]
\subsubsection{The Workshop}
At a Sage Days workshop on number fields, we
would attack the following problems:
\begin{enumerate}
\item
Rewrite {\em number fields to use FLINT} for basic arithmetic
(currently they use NTL for all basic arithmetic). This would
speed up basic arithmetic in number fields, but be a bit more difficult
than rewriting $\mathbf{Q}[x]$.
\item Finish implementing {\em relative number field} in Sage. Currently
Sage supports relative number fields, but many operations are not
implemented, inconsistent, cumbersome, or {\em unnecessarily
slow}. Bring support for relative number fields up to the same
level as for absolute number fields. This would take at least 1
month fulltime work to do. It is challenging because PARI does not
provide support for general relative number fields.
\item Sage has a large amount of code for working with number fields
and orders. However, there is very little functionality for
{\em explicit class field theory}. Fortunately, PARI does have such
functionality, and with some work we could make a polished version
of that functionality available from Sage.
\item Include a first rate number field sieve implementation in Sage.
In particular, include {\tt msieve} in Sage. {\tt msieve} is a
complete public domain implementation of the {\em general number
field sieve}. See \url{http://www.boo.net/~jasonp/qs.html}. It
would likely take one week fulltime to sort out build issues, and
one week to create, document, and test wrapper code.
\end{enumerate}
\subsection{Sage Days: Modular Forms}
\subsubsection{Background}
\begin{wrapfigure}{r}{0.3\textwidth}
\shadowbox{\includegraphics[width=0.3\textwidth]{modform.png}}\\
\end{wrapfigure}
[[background about modular forms capabilities and development in
sage]]
\subsubsection{The Workshop}
At a Sage Days workshop on modular forms, we
would attack the following problems:
\begin{enumerate}
\item Implement all algorithms for {\em weight one modular
forms}. See Tate's algorithm from Springer Lecture Notes 1585 and an
algorithm of Kevin Buzzard.
\item Implement algorithms for computing {\em Hilbert modular forms}.
This project requires quaternion algebra arithmetic over real fields
(see above). The implementation would likely follow Lassina
Dembele's papers. It would take one month to become familiar
with the theory, and another to implement a first useful
version. This project can't start until quaternion algebras over
real fields have been implemented.
\item Implement code for computing {\em Stark-Heegner points on
elliptic curves via overconvergent modular symbols}. Henri Darmon
and Robert Pollack have published Magma code for doing this.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Group Theory}
\subsubsection{Background}
[[background about group theory capabilities and development in sage]]
[[insert a picture of a Cayley graph]]
\subsubsection{The Workshop}
At a Sage Days workshop on group theory, we would attack the following
problems:
\begin{enumerate}
\item Create a {\em C-library interface to GAP}. The PI spent 1 week
fulltime during Summer 2009 and created a proof of concept of this
library interface, which proved that this project is do-able, and
that it would directly result in up to 2000 times speedups over the
current Sage/GAP pipe-based interface.
1 month to implement the GAP C library interface, and 1 month to
switch Sage over to use it instead of the pipe interface. Sage uses
the pipe interface right now for most group theory, and switching
over and optimizing the results will uncover many issues, and also
require rewriting some of the Sage library. It will also make it
reasonable to use GAP for basic arithmetic in many interesting new
cases (e.g., Lie Algebras).
\item Once there is C-library interface to GAP, sponsor a Sage Days
workshop to {\em expose to Sage as much as possible of GAP's
functionality}, including characters of finite groups, Lie
algebras, etc.
This would be a good topic for a Sage Days
workshop, since it is fairly easy to implement a wide range of
things in parallel. It would also be a good way to improve
interaction between the Sage and GAP projects, since it is likely
several GAP developers would attend.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Algebraic Topology and Homological Algebra}
\subsubsection{Background}
We can do Steenrod algebra calculations (at both $p=2$ and odd
primes), and we can do simplicial homology. We can do group
cohomology (via the optional spkg by Simon King and David Green). We
have free modules over commutative rings.
At a Sage Days workshop on algebraic topology and homological algebra,
we would attack the following problems:
\begin{enumerate}
\item We will improve simplicial homology: we should be able to
compute the ring structure for cohomology, and we should be able to
keep track of the generators. We should add an interface to CHomP,
which computes cubical homology. We should add some capabilities to
compute with formal group laws (homotopy theorists only care about
1-dimensional formal group laws, but we don't need to limit
ourselves), and the related computations with the spectrum BP. We
should implement differential graded algebras.
\item (There are a lot of other ideas on the Sage wiki page for
algebraic topology (http://wiki.sagemath.org/topology), and we could
throw some of them in. Some of them get pretty far from my own
research, so I don't know much about them. We would really want
someone who is interested in adding these things, so that we have
motivation for doing so.)
\item For graded connected algebras, we should implement Bob Bruner's
algorithm, or develop an interface between his C programs and Sage.
Christian Nassau has done some related work, but it is focused on the
Steenrod algebra, not on general graded connected algebras.
\item For group algebras, we should see if parts of the group cohomology
spkg should be made standard, and possibly extended to other algebras.
\item In general, we should implement free modules, projective
modules, and injective modules over arbitrary rings, and we should
implement resolutions and derived functors. Where possible, we
should implement methods of computing resolutions (as in the case of
graded connected algebra and group algebra). We should implement
some interesting noncommutative rings over which we can compute
examples. (Singular might help here.) There is a package (for
maxima, I think) called "affine" that does some related things, and
we should get a copy and see if we can incorporate it.
\end{enumerate}
\subsubsection{Key People} John Palmieri, Bruner and Nassau. King and
Green. Some other group theorists?
%\subsection{Sage Days: Symbolic and Algebraic Statistics}
%[[background about how much Sage has for statistics already]]
%[[algebraic statistics is a major hot topic... computational? by symbolic, I mean capabilities
%like in Mathematics as opposed to R or matlab -- see the mathematica webpage]]
% \subsubsection{The Workshop}
% At a Sage Days workshop on statics, we would attack the
% following problems:
% At a Sage Days workshop on algebraic topology, we would attack the
% following problems:
% [[grab some ideas from sage days 15]]
% \begin{enumerate}
% \item
% Implement native {\em statistics} functionality in Sage,
% beginning with a class for holding data with descriptions, methods
% for subselection, transformation and assignments, and then more
% classes with data/object interactions that wrap or use {\tt
% scipy.stats} and {\tt rpy}.
% \end{enumerate}
% \subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Sage for Engineers, Physicists, and Scientists}
\subsubsection{Background}
Most Engineers use Matlab and they don't know remember what a Ring and
a Field are. They would not find the normal Sage Tutorial attractive
because of the use those terms. However, Sage contains powerful
packages that Engineers, Physicist, and Scientists would find very
attractive if they were aware that Sage contains:
\begin{itemize}
\item Most numerical packages they want (Numpy, Scipy, FFT ect).
\item 2D and 3D plotting packages some with the same interface as Matlab
\item Symbolic Algebra for both Calculus and Linear Algebra
\item Python as basis
\item Cython, a built in C compiler, which gives them "C" speeds for numerical calculations
\item Image processing
\item Python access to html information (the financial package is an example).
\item Access to TCP/IP through Python, which could also be used to interact with experimental systems
\item Statistic and random variable functions for most distributions used in Engineering.
\item numerical differential equations solvers
\item Latex for displaying Mathematics expressions
\item signal processing packages
\item Sage is free
\end{itemize}
In industry, most Engineers use Matlab and they are by far its largest
user. One of the objectives of Sage is to be an alternative to
Matlab, so we need a tutorial, and literature attractive to them. In
recent years many Physics and Engineering departments now use Python
for class programming. MIT moved from using Scheme to Python three or
four years ago, as one example. Also, in the past year, many
Silicon Valley companies are now using Python. Sage seems like it is
the next logical step for them since it comes prepackaged with all the
items listed above.
\subsubsection{The Workshop}
One of the objectives of the Sage days would be to produce a series of
videos, worksheets, and tutorials aimed at being user friendly to
Engineers, Physicists, and Scientists. This would give a quick
introduction to the tools they use and leave out all the wonderful
mathematics they normally don't use.
A suggested list of talks (all only including symbolic and real
numbers with a engineering bent for problems) is:
\begin{itemize}
\item Sage Overview (quick run through all the gee whiz stuff).
\item Graphics and Images in Sage (2D, 3D, implicit plot, Matlab like interface).
\item Symbolic Calculus
\item Linear algebra (Show Symbolic and numerical examples i.e. eigenvectors, eigenvalues, matrix inversion, ect).
\item Numerical Analysis (Numpy, numerical solutions to differential equations)
\item Cython (Programming including numpy examples).
\item Statistics
\item Use of Interact and how to set up TCP/IP servers and clients.
\item Use of Latex and html in Sage.
\item Signal Processing in Sage
\end{itemize}
This list would not be that much different from previous Sage days, it
would just be targeted at a different audience.
\subsubsection{Key People} Josh Kantor, Michael Madison, all Enthought employees,
Fernando Perez, Jarod Milliman, Prabhu Ramakrishnan
\subsection{Sage Days: Numerical Computation}
\subsubsection{Background}
Sage includes many core components that support numerical and
scientific computation, including ATLAS (NSF-funded?) \url{atlas}
which is a high-performance numerical linear algebra package, Scipy
and Numpy \url{numpyscipyurls} which is a huge Python/Fortran library
that provides similar functionality to MATLAB, GSL \url{gslurl} which
is a C library for numerical computation, R \url{Rurl} which is
primarily a statistics package but provides substantial numerical
capabilities, and CVXOPT \url{cvxopturl} which provides numerical
convex optimization functionality and sparse matrix linear algebra.
The Sage distribution is also the basis for the FEMHUB \url{femhuburl}
project, which is an easy-to-use state-of-the-art open source
distribution of code for numerically solving partial differential
equations using finite element methods [[I think!]]. The director of
FEMHUB project is [[some connection with this proposal, either co-PI
or ...]].
\subsubsection{The Workshop}
At a Sage Days workshop on numerical computation, we would attack the
following problems:
\begin{enumerate}
\item Improve support in Sage for numerically solving differential
equations and visualizing the solutions. This would mainly involve
creating wrapper code and documentation with many examples so that
the solver capabilities provided by Scipy work efficiently with
native Sage objects (e.g., symbolic expressions). It would also
involve writing code so that solutions (and families of solutions)
can be efficiently plotted in 2 and 3 dimensions.
\item Sage has high precision interval and fixed precision floating
point arithmetic is built on top of Paul Zimmerman's rigorously
justified MPFR library (\url{mpfrurl}). Sage thus currently has the
capability to do numerical linear algebra using real and complex
interval arithmetic and with fixed arbitrary precision real or
complex floating point numbers. However, the implementations of the
underlying algorithms for these fields is naive and generic in most
cases. In consultation with experts in numerical analysis (e.g.,
Clint Whaley--director of the ATLAS project--who has attended a
recent Sage Days workshop), we propose to implement numerically
stable efficient algorithms for linear system solving, singular
value decomposition, LU, QR and Cholesky decomposition, and matrix
inversion for generic dense matrices, sparse matrices, and matrices
with extra structure.
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Numerical Solution to Partial Differential Equations}
\subsubsection{Background}
The general idea is that it would be a gathering of people interested
in the finite element method and related things, like a symbolic
derivation of that using sympy/sage, making sure the mesh, solution,
etc., works nice both on the desktop and in the notebook, interfacing
lots of opensource FEM software like libmesh, sfepy, as well as
graphics output like mayavi, VTK, etc.
\subsubsection{The Workshop}
\begin{enumerate}
\item Write PDE and boundary conditions in the notebook, and create
weak formulations automatically using sympy/sage. For more
complicated PDE systems or for PDE in other than Cartesian
coordinates, this would take a huge burden off the user.
\item Design a suitable model/protocol for passing the weak
formulations to all codes in FEMhub.
\item Define geometries interactively via Java applets and send them
to mesh generators. Visualise and edit the resulting meshes in the
notebook.
\item We can plot the solutions and meshes from python already (using
either mayavi or mpl), but this needs improvements, e.g. to be able
to plot streamlines, change plotting parameters easily, etc. We have
elaborated visualization in opengl and glut in C++, but
unfortunately this is not usable in the notebook, and also it is not
reliable across platforms.
\item Interface lots of open source FEM software like dune, fipy,
hermes, phaml, libmesh, sfepy, etc. Currently, of those only fipy,
hermes, and sfepy are in FEMhub. To design a unified interface and
allow for interoperability is one of our major tasks.
\item Improve graphics output in the notebook (mayavi, VTK, ...) Both
Mayavi and VTK are in FEMhub, but unfortunately they do not build on
Mac nor Windows. The problems have been kind of sorted out on Mac
already, now some manpower is needed to switch preferably both Sage
and FEMhub to a python framework build and then fix the
configuration of VTK. We have no idea yet what has to be done on
Windows to make it compile.
\item The web notebook should be made login free as soon as
possible. We have attempted to do this recently, but we found the
core of the notebook quite complicated and we were not efficient at
all, so we stopped this effort. Unfortunately we do not have the
manpower and expertise to fix the core of the notebook, but we think
that it should be revised. We are going to invest a substantial
amount of work into the notebook in the future. It might be useful
to coordinate our efforts eventually.
\end{enumerate}
\subsubsection{Key People} Pavel Solin (Univ. of Nevada), Ondrej Certik
(Univ. of Nevada)
\subsection{Sage Days: Combinatorics and Optimization}
\subsubsection{Background}
[[background about how much we have done with optimization and
combinatorics in sage already]]
\subsubsection{The Workshop}
At a Sage Days workshop on optimization, we would attack the
following problems:
\begin{enumerate}
\item Implement a {\em C++ interface to MiniSat} and include MiniSat
in Sage. Also implement a general DIMAC conjunctive normal form
(CNF) SAT-solver interface. (Victor Miller is extremely supportive
of this project.) Though MiniSat is small,
Stein wrote a proof-of-concept wrapper, and it is clear it will take
substantial work to really do this right.
\item Implement {\em finite planes and incidence geometry}. Sage's
capabilities are still pretty primitive. Dan Gordon remarks that
``[Sage...] has a basic functionality, and takes a database of Witt
designs and Hadamard matrices from GAP, but Magma also has a
database of difference sets, and many more operations; equivalence
testing, invariants, resolutions, ... Most of this wouldn't be too
difficult to replicate, and I've thought about doing some myself,
particularly difference sets.''
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Symbolic Computation}
{\em Symbolic computation} is the collection of exact methods used to
perform basic tasks in engineering, physics, etc., which includes
applications such as symbolic integration and solving differential and
difference equations. We divide the relevant topics into three areas:
\begin{itemize}
\item {\em Differential / difference algebra:} for indefinite
integration/summation and differential/difference solvers
\item {\em Transforms and definite integration:} Mostly table lookup and
pattern matching based approaches to evaluating transforming
integrals/special functions
\item {\em Fundamental algorithms:} Basic computer algebra methods
required to implement the algorithms above efficiently. These
include multivariate polynomial factorization, sparse multivariate
polynomial interpolation (Erich Kaltofen, Wen Shin Lee), and exact
linear algebra over multivariate polynomial rings.
\end{itemize}
\subsubsection{A Workshop on Difference/Differential Algebra}
[[Here are William Sit's comments about computational differential
algebra/Sage/Axiom from sage-devel:
\url{http://www.mail-archive.com/[email protected]/msg13097.html}
Bronstein's \verb|Sum^it| library provides implementations of some of the
fundamental algorithms we should try to get in Sage:
\url{http://www-sop.inria.fr/cafe/Manuel.Bronstein/sumit/sumit.html}
]]
[[We can contact Michel Singer and
ask for help adding mathematical content below.
AFAIK, other names I wrote below, van Hoeij and Abramov work with Maple.]]
Burcin Erocal has implemented special classes of difference fields,
called Pi-Sigma fields (by Michael Karr), as a part of his summation
code. He's planning to implement generic difference/differential
rings/fields and operators in the near future.
A theoretical framework for investigating solutions of
differential/difference equations is provided by
differential/difference algebra. At the moment, Sage doesn't have any
facilities for working with differential/difference
fields/rings/ideals, etc. An implementation of the basic structures
required here would pave the way to a proper implementation of the
Risch and Karr algorithms for indefinite integration and summation
respectively, as well as providing a basis for research in Galois
theory of differential and difference equations, which forms the
foundation for algorithms to deal with higher order equations.
The goals of a workshop in this area would be:
\begin{enumerate}
\item Provide support for working with differential/difference
rings/fields and their operator domains. Singular let's us do this
for polynomial rings. In order to handle denominators in the user
interface, one could use Pynac, and pass the harder problems, such as
computing normal forms w.r.t. an ideal to Singular after clearing
denominators.
\item Implement the Risch-Norman (parallel integration) algorithm \cite{[B2007]}
\item Implement recent algorithms by Abramov, van Hoeij, Hendriks-Singer to find
Liouvillian solutions of difference/differential equations
\cite{[B2007]} \url{http://dx.doi.org/10.1016/j.jsc.2007.04.003}
\end{enumerate}
\subsubsection{Key People}
Michael Singer, Mark van Hoeij, Sergei Abramov, Burcin Erocal
\subsubsection{A Workshop on Integral Transforms and Definite Integration}
Important cases of definite integration in computer algebra systems are
handled through applying some integral transforms (such as the Mellin
transform) to convert the integral to a contour integral which can
also be expressed as a well known special function (hypergeometric, or
Meijer-G), then using properties of this special function to arrive at
an evaluation. While these methods have been implemented, and used in
practice by closed source systems such as Mathematica and Maple,
literature on how to correctly apply these methods to get practical
results is still scarce. Sage has an efficient framework based on the
symbolic computation library GiNaC to represent these functions, and
perform pattern matching operations. This provides the basic building
block to implement the required transforms (both integral and
hypergeometric).
Goals for a workshop:
\begin{enumerate}
\item Implement a construct for hypergeometric functions
\item Recognition of hypergeometric functions, and conversion to
a standard representation (pFq)
\item Build lookup tables for well known transforms, including hypergeometric.
and integral (Mellin, Hilbert, Laplace, etc.).
\end{enumerate}
References: See \url{http://wiki.sagemath.org/symbolics},
\url{http://www.mat.univie.ac.at/~kratt/hyp_hypq/hyp.html},
\url{http://www-igm.univ-mlv.fr/~gauthier/HYPERG.html}.
\subsubsection{Key People}
Burcin Erocal,
Peter Paule, Victor Moll, Victor Adamchik (see \url{http://www-2.cs.cmu.edu/~adamchik/}).
\subsection{Sage Days: Coding Theory}
\subsubsection{Background}
\subsubsection{The Workshop}
\begin{enumerate}
\item a fast minimum\_distance for an arbitrary non-binary code (minimum distance of
linear binary codes can be computed very quickly thanks to code by
Robert Miller)
\item a function to compute a basis for the Riemann-Roch space of a
reasonably general curve
at a reasonably general divisor. This is needed to implement AG codes.)
\item implementation of the "weight function" machinery (this is an alternate
way to compute certain AG-type codes, avoiding the Riemann-Roch space
machinery; see the survey papers by Hoeholdt on AG codes...)
\item decoding algorithms
\item covering codes and covering radius algorithms (more generally,
porting over Guava
functions to Sage)
\end{enumerate}
\subsubsection{Key People} [[List of names]]
\subsection{Sage Days: Linear Algebra}
\subsubsection{Background}
Many problems in mathematics can be expressed with the language of vectors and linear transformations (matrices). Thus many areas of Sage rely on high-performace routines for solving equations, creating canonical bases, inverting matrices, in addition to computing determinants and eigenvalues. Areas relevant to other proposed workshops include coding theory, optimization, numerical computation. There are efficient routines for many of these computations, over a variety of rings and fields. Despite the maturity of Sage's support for linear algebra, there is more work to do: new routines to add, specialized versions of existing routines to implement (over different rings), speed improvements to existing routines and organizing commands to improve ease-of-use. Improvements in the linear algebra routines will strengthen Sage throughout.
\subsubsection{The Workshop}
At a Sage Days workshop on linear algebra, we would attack the following problems:
\begin{enumerate}
\item \emph{Add and improve matrix decompositions} such as LU, Cholesky, Jordan. Some of these could be improved, others could be expanded to more rings or fields, and others would be new.
\item \emph{Create specialized routines} for existing commands over specific fields or rings. Some linear algebra routines have generic implementations, which could be made much faster in some situations if they exploit knowlege or libraries for specific rings or fields (such as the rationals or integers).
\item Where \emph{specialized libraries} can provide the fastest possible routines, provide an interface from within Sage.
\item Where \emph{Cython code} can provide faster routines, remove dependence on specialized libraries.
\item \emph{Widen support for left- and right- variants} of various commands. In other words, better support the two views of a matrix: a collection of row vectors, or a collection of column vectors. Currently Sage has a bias towards rows (vectors on left of a matrix) which some users find unnatural.
\item \emph{Improve support for numpy data types}. numpy is a popular Python package for computations with mult-dimensional arrays. Currently it is awkward to move between numpy's data representations and Sage's.
\item There are about 90 open linear algebra tickets to mine for more ideas\dots
\end{enumerate}
\subsubsection{Key People} Rob Beezer, Jason Grout (?), [[other people]]
%\subsection{Sage Bug Days}
%\subsubsection{Background}
%[[Describe how the first bug days went. Explain that the second bug days is
%planned for late January, funded by a COMPMATH NSF grant.]]
%\subsubsection{The Workshop}
%At a Sage Bug Days, we would do the following.
%\begin{enumerate}
%\item We had one ``Bug Days'' workshop in San Diego, during
% which the participants fixed over 200 venerable bugs in Sage (over
% 1/3 of all known bugs), and did a triage of all bugs. Another {\em Bug
% Days workshop} would be a great way to substantially improve the
% quality of Sage, and fix many longstanding issues.
%\end{enumerate}
% \subsubsection{Key People} [[List of names]]
