The corresponding page at University Paderborn

Design and implementation of efficient algorithms for computer algebra

Responsible in France : Paul Zimmermann, projet Euréca, Inria Lorraine.

Responsible in Germany : Prof. Benno Fuchssteiner, University of Paderborn.

Report for 1997

Scientific objectives. The purpose of this proposal is to design and implement new and efficient algorithms for symbolic computation, in particular for the MuPAD computer algebra system. This system being distributed for free to the scientific community, we want to provide to both researchers and students a free computer algebra system of professional quality with the best-known algorithms.

Work plan. The current specific objectives are:

  • first a meeting of one week for all participants to the project in a common place between Paderborn and Nancy (for example Oberwolfach) to make people know each other and to split the future work. This meeting took place in Oberwolfach on January 10, 1997 and here is what was decided. Who does what ?
  • implementation of a recurrence solver (1 year)
  • implementation of Kovacic's and Prelle-Singer algorithm for ODEs (1 year)
  • numerical evaluation of special functions (2 years)
  • implementation and testing of the parallel version of MuPAD on a network of clusters (2 years).

    Interest of collaboration, team complementarity. The Nancy team has some competence on discrete algorithms (for example for solving recurrences and ODEs) and special functions. The Nancy team also has a new machine (Power Challenge Array from Silicon Graphics, i.e. 4 clusters of 8 processors each) on which we would like to port and test the parallel version of MuPAD.

    The MuPAD team has of course the best experience about the implementation of computer algebra systems, and in particular the MuPAD kernel. In addition, it has experience about the implementation of the memory management unit (MAMMUT) of MuPAD, about micro- and macro-parallelism.

    One of our main objectives is to prove that parallelism can be used efficiently in computer algebra systems. In a first stage we would like to produce some significant speedups using a shared-memory version of MuPAD (micro-parallelism). In a second stage we would like to produce speedups using a distributed version based onto PVM or MPI on a cluster of several machines, each machine having possibly several processors. This is exactly the architecture MuPAD was designed for (in 1992), and also exactly the architecture of the Power Challenge Array (designed in 1995).

    Composition of the teams.

    France: Françla;ois Bertault (PhD student), Vladimir Grebinski (PhD student), Gregory Kucherov (doctor, researcher), Alain Mirgaux (professor, teaches MuPAD), Joseph Rouyer (professor, teaches MuPAD), Paul Zimmermann (doctor, researcher, responsible).

    Germany: Benno Fuchssteiner (professor, responsible), Oliver Kluge (doctor, researcher), Holger Naundorf (doctor, researcher), Frank Postel (PhD student).

    Means available for the realization of the project. France: several workstations, a Power Challenge Array of 32 processors. Germany: several workstations, a multi-processor SparcStation.