Computer algebra systems

When the Symbolibre project started, it was decided right away that the calculator had to support computer algebra. But this leaves a wide spectrum of tools to choose from: PARI/GP, Xcas, SageMath, SymPy, Scilab to name only a few.

Logos PARI/GP, Xcas, SageMath, SymPy, Scilab

Of course, several aspects constrained this choice. Even if the Raspberry Pi Zero is by far more powerful that typical high-school calculators, doing computer algebra in Python is still too heavy in terms of performance. So SymPy is out first. We’re also not going to use the various graphical interfaces because we’re going to build our own, so we’re looking for a program with a command-line interface, ideally a library we can link against.

First attempts at using SageMath

Our first attempt, clearly the most ambitious, was to try out SageMath. Two ideas backed this choice. We first wanted to test the limits of the Pi Zero, and since SageMath is a set of interfaces to existing native programs, the raw evaluation performance is not much of a problem. Plus, we wanted the project to contribute to the free software world, in the form of an implementation of Turing machines in SageMath’s finite automaton module (somewhat like Librem 5 developers contribute to Wayland, if I can afford the analogy). One of our groups worked on this contribution during the project year.

SageMath is written in Python, but it delegates computation to other computer algebra systems typically written in compiled languages; I can mention PARI/GP (C) and Giac, the system behind Xcas (C++). Our intuition was to remove external interfaces to trim down SageMath both in size and performance.

But of course theory models practice much better in theory than it does in practice. SageMath modules are theoretically disabled at configuration time by a simple mechanism: just write disabled in the SAGE_ROOT/build/pkgs/<module>/type file for each module to disable. This sets a preference that might be ignored during dependency resolution if the selected module is a hard dependency of an enabled module.

And there’s a great deal of modules. Building SageMath on my laptop (4 cores, 8 GiB of RAM, SSD drive) takes about 2 hours. For reference, here are the modules that took the longest time to build (for a native build – cross-compiling adds some technical elements but no major changes in build time):

ModuleBuild time
Singular 4.127 minutes
Sagelib 8.320 minutes
gfortran 7.2.019 minutes
Pynac 0.7.2215 minutes
Giac 1.4.913 minutes
scipy 0.19.110 minutes

The main problem comes now. SageMath is a gathering of many tools, but the implementation of SageLib itself is not modular; for instance, it contains several thousands of calls to Singular split over more than 200 files. This kind of dependencies cannot be worked around, and traversing the dependency tree eventually shows that only two modules can be disabled: the r language and its Python interface rpy2. Improving the code structure is one of the future goals of SageMath, along with transitioning to Python 3, but this is going to take some time.

For now, we can’t disable crucial modules, and it takes a heavy toll on performance: 1 minute and 55 seconds and 175 Mio of RAM are needed to start the SageMath shell. RAM is not the critical issue since the Pi Zero has 512 Mio. It just means we can have only one instance of the computation server and we must communicate with IPC, which is inconvenient but feasible. The startup time however is a deal-breaker. Even by starting SageMath at bootup, we’d need at least two minutes before we can compute anything.

Second attemps with Giac

We then turned to Giac, Bernard Parisses’s computer algebra system, which happens to be used by the HP Prime. There are again several reasons for this choice. Giac is one of SageMath’s backends, so we could try it immediately since it was already cross-compiled. Plus, as the computer algebra system of the HP Prime, we had prior guarantees on its features and performance.

Indeed, Giac is linked against as a C++ library with much more reasonable costs for our Pi Zero: trivial programs can be executed in less than a second using only 15 MiB of RAM. This type of startup time is much better, even if every application has its own instance of the library.

We’re now developing the Symbolibre calculator with Giac. The C++ interface makes it easy for native applications, and the giacpy module will handle any computer algebra in Python in the programming application. It’s interesting to see how modern computers hide the complexity of software at times. The loading time of a SageMath shell is a couple seconds away from that of a Giac shell; but as soon as we switch platforms, the difference suddenly appears. That’s why we pay great attention to our software stack to keep the system efficient.

Leave a Reply

Your email address will not be published. Required fields are marked *