next_inactive up previous


Workshop on Open Source Computer Algebra
Report

by the organization committee:
Daniel Duparc, Bernard Mourrain, Bernard Parisse, Fabrice Rouillier,
Marie-Françoise Roy, Nicolas Thiéry et Paul Zimmermann

June 17, 2002

There were $52$ registered participants, and altogether about $60$ participants, counting people who did not register or local auditors. The average audience to the talks and to the day-3 discussions was about $45$ people. Among the participants were 2 people from the USA, one from Australia, and 3 from Germany, one from Ghana, one from Italy (the last two being real participants, i.e. not invited speakers). There were also 4 teachers from French ``Classes préparatoires'', several persons from a French ``IREM'' (Research Institute about Teaching Mathematics) mostly (but not only) interested in teaching problems with CAS.

1 Day 1: May 21st

14h
Opening session (Bernard Mourrain). Recall of the objectives of the workshop (state of the art of the existing free systems in computer algebra, and discussion about a collaborative effort for a free computer algebra system or platform).

15h
Open source software, licenses, and legal issues (Bernard Lang). Different forms of protection: (1) copyright (protects only the form, i.e. text, not the idea, technique or algorithm that it implements); (2) patent (to protect a particular technique, for example displaying a cursor on a white or black screen using the xor function); (3) industrial secret (not relevant here); (4) trade marks (this is the basis for the free software economy: trade marks make the real difference from modified version, for example between different distributions of Linux, Mandrake, RedHat, ...). About patents: people often patent (i.e. make public) only the trivial parts of their systems, and keep secret the hard techniques. For free software, trade marks are the only way to guarantee the specification or content of a given distribution. Bernard Lang proposes the following model: first accept all open-source contributions, then make the selection at the distribution level, with possibly several trade-marks competing. Parallel with the process for scientific publication: we are slowly going from a ``select then publish'' process (first selection by editorial board of a journal, then publication in the given journal) to a ``publish then select'' process (first put your preprint on the web, then selections/reviews are made by different groups).

What about the protection of languages? Bernard Lang: they are usually not protected, since it is the best way to kill them (example of Simula 67).

Software licenses: remember the difference between a patent (forbids the use of a technique, even for people who invented it independently) and a copyright (only applies to a real program, and derived work). A license is a way to give rights: (a) legal rights, and (b) technical rights (relative to the source code for example). Open Source: source code is given, and permission to use, modify, and redistribute, plus no discrimination is made (if there is a restriction for military use, or use by employees of Microsoft, then it is no longer an open-source license). Copyleft: same as open-source + additional requirement that redistributed work remains under the same license (example the GPL, or Gnu General Public License). The BSD license has no copyleft item. Bernard Lang: you should find a way to mix licenses, to have maximal cooperations, and have the possibility to include components under proprietary licenses.

16h30
TeXmacs (Joris van der Hoeven). GNU TeXmacs (http://www.texmacs.org) is a graphical interface for computer algebra systems, distributed under the GPL. Joris van der Hoeven demonstrates its nice capabilities (for example line-breaking facilities) and some interfaces with Axiom, GIAC, MuPAD, GP, ... Main features: a wysiwyg (what you see is what you get) editor which is close to the mathematical notation, with an easy interface to computer algebra systems (about 6 hours according to Joris van der Hoeven).

17h15
GINAC (Richard Kreckel). GINAC (http://www.ginac.de) is a free (GPL) system for the manipulation of very large symbolic expressions (for example series), with mainly applications to physics. It is distributed with Debian, SuSe and FreeBSD, and interfaced with gTybald, pyginac, Symbolic Octave, Purrs. The original motivation was the limitations of existing systems (for example Maple V could not deal with polynomials/series of more than $2^{17}$ terms). Even new versions of proprietary software contain serious pitfalls that are not fixed by the developers; Richard Kreckel points out the Maple 7 bug of $\frac{2001!}{2000!}$ that simplifies to $1$. Main feature: designed for very large and huge expressions.

17h45
GIAC (Bernard Parisse). GIAC (http://www-fourier.ujf-grenoble.fr/~parisse/giac.html) is a free (GPL) general purpose computer algebra system with interactive geometry. It is developed by Bernard Parisse, and Renée de Graeve for the documentation. GIAC is the C++ library, and XCAS the interface. First target is educational (runs on small IPAC pocket-computer), it is 2 years old, 70k lines of code (C++), built over GMP and the C++ STL, compiled over Unix/Linux (x86, ARM) and Windows, user interface with GNU readline. Main features: an interface with Maple and MuPAD, a symbolic step-by-step debugger, a localization for French and Spanish.

18h15
Linbox (Pascal Giorgi). Linbox (http://www.linalg.org) is a C++ library, which is specialized for linear algebra computations. It is built by people in Lyon/Grenoble (around Gilles Villard) and the group of Kaltofen at North Carolina State University. It contains about 40k lines of code. Coefficients domains are external to the library (with wrappers), enabling a common interface. The overhead of wrappers for coefficients is rather small (a few percents to maximum 20% on the given examples). Example: take a $200000 \times 200000$ sparse matrix $A$, with $A_{i,i}$ being the $i$th prime, $A_{i,j}=1$ if $\vert i-j\vert$ is a power of $2$, and $A_{i,j}=0$ otherwise. Now compute $B=A^{-1}$. Then $B_{1,1}$ is a rational with numerator and denominator of more than $100.000$ digits, that Linbox can compute in about 180 CPU hours. A beta-version of Linbox is under development, but it is not yet available, so its license is not yet clear. Main features: it contains many optimized representations for matrices (dense, column-sparse, global-sparse), and almost all classical algorithms (Gaussian elimination, black-box algorithms).

18h45
TRIP (Jacques Laskar and Mickael Gastineau). TRIP is a software dedicated to celestial mechanics computation, which is developed at ``Bureau des Longitudes'' in France (http://www.bdl.fr). It is not (yet) distributed. Mainly used to study the stability of solar system: Newton's equations and relativity. First approach: about one page equations, step size about half a day, simulation on 3 millions years takes 4 months. With perturbation methods (secular equations): 150.000 monomials, about 800 pages, human work about 500 years, simulation on 3 millions years takes 5 minutes, on 1 billion years takes 1 day (computation done in 1985, with 500k memory). Contains generalized power series with several variables, and now a general algebraic manipulator: while, for loops, if-then-else, macros, recursivity, different representations (dense recursive, sparse recursive, block homogeneous, block d'Alembert, block Fourier). Operations on series: derivation, integration, inversion, exponentiation, fast evaluation, substitution, coefficient selection, ... Coefficients: double-precision floating-point, quadruple precision, rationals with limitation, interval arithmetic with double or quadruple precision, ... Matlab-like module, uses Gnuplot for graphs, communication with MathML 2.0. About 140k lines of C, interface with bison/(f)lex, ensures portability. Works under AIX, Tru64, Unix, Windows, MacOS, and uses BIAS 2.0a. Main feature: special data representation for multiseries, that reduces memory usage and simplifies computations, thus faster computations.

2 Day 2: May 22nd

9h
Objective Caml (Pierre Weis). Objective Caml (http://caml.inria.fr/ocaml) is a ML dialect developed at INRIA Rocquencourt. It is distributed under the LGPL for the run-time system and libraries, and under the QPL (Q Public License) for the compilers and tools. It includes a run-time (interpreter), and a compiler, which can compile both in byte-code or in native code. The native code produced is as efficient as that obtained with cc -O2, and somewhat more efficient than that obtained with c++. It could be a basis to implement a computer algebra system. A question arises about the overloading of operators, for example $+$. Main feature: very efficient and highly portable!

9h45
SYNAPS (Philippe Trébuchet). SYNAPS (http://www-sop.inria.fr/galaad/logiciels/synaps/) is an environment for the integration of computer algebra components. That project started in 1996 (formerly based on ALP), and is distributed under the LGPL (GNU Lesser General Public License). Main features: a bridge between different computer algebra systems and specialized libraries (like GMP), but also numerical software (for example LAPACK, BLAS).

10h45
Scilab (Claude Gomez). Scilab (http://www-rocq.inria.fr/scilab) is a system for numerical/scientific computations (similar to Matlab). It is distributed with source code, under a special ad-hoc license. It is a huge system: 265k lines of Fortran, plus 200k lines of C, and 75k lines in the Scilab language itself. A consortium will be soon created around Scilab, where industrials pay to support the further development of the system, and participate through an executive committee to the future of the system. In particular this executive committee could propose to change the Scilab license to a ``more open'' license like the GPL. Main feature: only ``free alternative'' to Matlab, which is proprietary and highly expensive.

11h30
GAP (Alexander Hulpke). GAP (http://www.gap-system.org) is a system specialized for group theory. It contains an interpreter with a Maple-like language. Since version 4.3, GAP is distributed under the GPL. The distribution contains a huge database of groups. Main features: Algorithms for algebraic structurs, efficient versions of many basic algorithms, flexible type system for mathematics, a formal process for the inclusion of new external contributions (GAP packages), through some kind of refereeing process.

14h
MuPAD 2.5 (Oliver Kluge). Presentation of the new features of MuPAD 2.5 (http://www.mupad.de): a new statistics package, an interface with Scilab, the combinat package. New graphics using a XML-based protocol. MuPAD is not free in the sense of freedom to use, modify, and redistribute it, although there is no charge for academic personal use. Oliver Kluge suggests interesting possibilities to be considered by the MuPAD developers to make the system more open: the library could become open source (every MuPAD user has free access to the whole library through expose(foo)), and the language could become free (this means that it may be possible to develop a clone of the MuPAD kernel).

14h45
Magma (Allan Steel). Magma (http://magma.maths.usyd.edu.au/magma) is a general purpose computer algebra system developed at the University of Sydney, by the group of John Cannon. It is the successor of the Cayley system developed in the 1980's in the same group. While Cayley was originally specialized in group theory, Magma is now a general algebra system (number theory, linear algebra and matrices, lattice theory, integer and polynomial factorization, ...) Main features: includes very efficient implementations of state-of-the-art algorithms (NFS for integer factorization, FFT for integer and matrix multiplication, $F_4$ and Kronecker for solving polynomial systems, Xavier Gourdon's implementation of Schönhage's algorithm for approximating roots of univariate polynomials), and has a nice object-oriented language, near from the mathematics. Magma is commercial mainly to support the group and the grants that allow to invite researchers from all the world to implement their latest algorithms in Magma. If another way to keep those revenues is found, the system might evolve to an open source one.

15h30
Axiom (Tim Daly). Axiom is the successor of Scratchpad which was first developed by IBM starting in 1973. It was later sold to the Numerical Algorithms Group (NAG). NAG stopped selling Axiom in October 2001 and searched for someone to open-source the code. Tim Daly proposed to take over Axiom under an open source license. Discussions between IBM and NAG about license issues are ongoing. Tim Daly is quite confident that someday Axiom will be open source. (He already has the sources from NAG, and got some agreement so that Joris van der Hoeven got a binary for his TeXmacs-Axiom demonstration).

Tim Daly makes a classification of computer algebra systems in three categories: (1) systems made by programmers, characterized with a kernel (mostly in C++) and a library, for which the most important issue is speed; (2) systems made by engineers, with a full interpreter, for which the most important issue is that the results are made to work regardless of correctness (e.g. $P-P$ where $P$ is a polynomial gives $0$ as an integer); and (3) systems made by mathematicians, with an interpreter and an algebra oriented language that is based on theory.

Axiom represents 30 years of development (23 at IBM research) involving 70 people and a large code base. As a research platform Axiom was a success but as a commercial platform it was a failure.

Tim Daly proposes several ways to motivate the development of free software (1) Developing Academic degrees (BA in Computer Algebra or open source) (2) Grants made to project moderators to pay per line of accepted code (3) Awards such as a Schelter Award (4) Pay for developing new features.

Tim Daly maintains a web page (http://home.earthlink.net/~jgg964/axiom.html) with discussions about Axiom.

Main feature of Axiom: a new-generation system, closer to the mathematics, with a huge man-year investment, but surely not a commercial success!

16h45
Maxima (presented by Marc Giusti, slides prepared together with Annick Valibouze). Marc Giusti also presented at the end of his talk some slides prepared by James Amundson. Maxima (http://maxima.sourceforge.net) is one of the systems derived by the system developed at MIT using MacLisp. Maxima was maintained by Bill Schelter, who obtained that the US Department of Energy (DOE), who owned the rights of the original Macsyma, did allow a free version named Maxima. Since the death of Bill Schelter in 2001, James Amundson took over the development of Maxima, and created a source forge project. Main work currently is to clean the code and improve the installation process (based on GCL, the GNU Common Lisp implementation, also maintained by Bill Schelter). A first development release will appear as Maxima 5.9.0. The main goal is a ``rock-solid'' Maxima 6.0. Main feature: currently the only system which is both general purpose and open source.

17h30
FOC (Renaud Rioboo). FOC (http://www-calfor.lip6.fr/~foc) is a system to develop certified computer algebra algorithms. The language design looks that of Axiom. The main idea is to compile each algorithm into the Objective Caml language, and the benefit from the efficient Objective Caml compiler. In parallel, the correctness of the algorithm can be checked using the Coq proof assistant. FOC is not (yet) available, a first distribution is expected at the end of the year. The license under which it will be distributed is not yet clear. Main feature: a solid foundation (like Axiom) with an addition a way to certify the correctness of algorithms.

18h15
PARI (Karim Belabas). PARI (http://www.parigp-home.de) is a system specialized for number theory. It is distributed under GPL since 2000. It contains a run-time interpreter (GP) and a library (libpari). The GP interpreter has a fairly simple script-like language. PARI/GP contains some functions for symbolic computation (factorization of univariate polynomials, truncated power series) but it is not a general purpose system. Any expression is fully evaluated, for example $\sin x$ evaluates to the truncated power series at $x=0$. A companion program, named GP2C, is developped by Bill Allombert; GP2C is a compiler from a subset of the GP script-language to the C (libpari) language, equiped with a wrapper around the system's build toolchain. It transparently builds and loads shared modules, providing speedups up to a factor of $10$ on some applications without dealing with the intricacies of C programming or Makefile writing. The PARI arithmetic is used by several computer algebra systems, since it implements multiple-precision complex floating-point numbers, and many elementary and special functions: it is used by MuPAD (a version before 2000, which was not under GPL), by Magma and at least by former versions of GCL and Maxima. One of the main objectives of the PARI group is to rewrite completely the system, replacing its own arithmetic by GMP, with better-structured source code, ... Main features: fast, very portable (just requires that sizeof(long) == sizeof(void*)), contains a number of unique algorithms in algebraic number theory, used by many researchers (also outside of number theory).

19h
Singular (Gerhard Pfister). Singular (http://www.singular.uni-kl.de) is a system specialized for computations involving polynomials (solving systems of polynomial equations, primary decomposition, computing triangular sets, ...) It has been distributed under the GPL license for 2 years. A new software dealing with non-commutative algebra will be called Plural.

3 Day 3: May 23rd

9h
g++ (Gabriel Dos Reis). Gabriel Dos Reis detailed the development model of g++, and the future directions of the compiler and tools. He is quite confident in the future of g++ since it has many users, even in the industry. The maintenance is active and effective.

9h30
ACE, mu-EC, mupad-combinat (Florent Hivert). Florent Hivert described a set of tools for combinatorics, developed at University of Marne-la-Vallée and University of Lyon 1. These packages have a long history and were fist developed with Maple. However some problems are to be solved, in particular the maintenance of packages like ACE when the main authors go to industry.

10h
Main discussion.

4 Conclusions

This workshop did bring together many people interested in free computer algebra software, and people from different fields of computer algebra (number theory, combinatorics, linear algebra, group theory) who did not know each other previously. The state of the art objective was successful, in so far that most participants did not know all the systems presented at the workshop. Even some possible collaborations between existing systems did appear during the workshop: there were some discussions between MuPAD and GIAC, which share common interest for the school market and PDAs; also GAP plans to use the GMP library and may use the MPFR library for its large integer and floating-point computations

Most speakers invited to present a software did really answer to the questions asked by the organizers: What makes the strength of your system? What are its weaknesses? What development model was used? What difficulties were encountered? Why did your system succeed or fail? What is the future of your system? Are you ready to distribute your system under an open source license?

There were some really great moments during the workshop: when Tim Daly remembered to everybody his friend Bill Schelter's memory, and when Gerhard Pfister did a demonstration of one of the first versions of Singular, from the 1980's, using a Sinclair's computer emulator! A special thanks to Tim Daly who made and brought with him 60 copies of a Rosetta-stone CDROM with Aldor, CoCoA, GAP, GCL, GIAC, GINAC, GMP, GnuPlot, Maxima, MPFR, NTL, Octave, Pari/GP, Gnu Readline, Scilab, Singular, TeXmacs, Yacas, and a file explaining how to define a matrix in each system.

Questions were numerous after the talks, and the chairman often had to stop them or delay them to the coffee break or the lunch or dinner, to be able to go on with the next presentation!

One of the aims of the workshop was to push existing non-free systems to become (more) free. This was successful since Oliver Kluge seemed not uninterested by making MuPAD more free.

Some main computer algebra systems that were not presented at the workshop are Maple and Mathematica, since we thought those systems are more commercial, and it would be harder for them to evolve towards a free system. However the possibility of developing clones of these systems should be considered, or developing front-end interfaces for those systems (this may solve the problem of switching to a new language). However legal issues carry great problems, to be considered carefully.

However,we are currently only in a preparation stage; so we don't want to discard potential approaches and collaborators too early.

Among the specificities of the domain is the fact that the user community is fairly thin, especially if we look for power users and potential contributers. This is mainly due to the simultaneous requirements for mathematical knowledge and programming experience, and to the fact that researchers often cannot afford to spend time on user interfaces/maintainance/... out of the scope of their research interests because this is not "rewarded" by their employers.

Please don't see these final conclusions as some kind of contempt w.r.t. the rest of the world; it just comes from the practical experience of some of us of several GPL projects like PARI who have a fairly large user base ( 10 000), but still don't really get any external contributions.

Also teaching problems were not really discussed. They are often very dependent of the country. Maybe the future discussion list will permit exchanges and new ideas from different countries. Another point was that the presented softwares (and discussions) were more centered about algebra than analysis (or 'calculus' at large).

5 Last minute news

It was pointed out by Gabriel Dos Reis that FIASCO is yet the name of a project under GPL. So we have to avoid this name!

The real work of the steering committee didn't begin yet. However Tim Daly had recently a very positive idea. Here is his email announcing a new mailing list devoted to Open Source Computer Algebra Systems (published, of course, with his permission): 

Date: Tue, 4 Jun 2002 23:21:35 -0400
Subject: [oscas] Open Source Computer Algebra Systems Mailing List

As a result of the Open Source Computer Algebra conference in Lyon
in May, 2002 we have decided that there needs to be a list of 
requirements gathered for an open source computer algebra system.
The purpose of this mailing list is to discuss and distill a list
of requirements. You are invited to participate if you wish.

There are 3 different communities that need to be served by such
a system (or group of systems). 

First is the education community. We need to collect requirements
related to the teaching of computer algebra or teaching with a
computer algebra system.

Second is the engineering community. We need to collect requirements
related to using a computer algebra system across many disciplines.

Third is the mathematics community. We need to collect requirements
related to doing research in mathematics.

Discussions of existing systems provided they highlight a particular
requirement.

Proposals for new features or future systems are appropriate provided
they highlight a particular requirement.

It is expected that this information will be used for setting 
direction and prioritizing work in current systems. It will also
be used to propose new work to funding agencies on existing or
future systems. These requirements will also form the basis of
discussion at the next open source computer algebra conference.

To subscribe to the list send email to LISTSERV@ACM.ORG
with one line in the body:

subscribe OSCAS FirstName LastName

Once you have subscribed you can send mail to everyone by sending
mail to OSCAS@ACM.ORG

Tim Daly
daly@idsi.net

About this document ...

Workshop on Open Source Computer Algebra
Report

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_subdir -split 0 -show_section_numbers report.tex

The translation was initiated by Duparc Daniel on 2003-01-17

next_inactive up previous
Duparc Daniel 2003-01-17