The project's technical results can be broadly categorised as infrastructure, algorithms and software, and industry analysis and applications. In this chapter we give a high-level overview of the activities in each area, and indicate relationships between them. Then, in the chapters which follow, the results of the individual areas are described in more detail.
Under infrastructure, we view the work on the Common Algebra Runtime and Software Interoperability. The Common Algebra Runtime provides basic facilities needed by symbolic and symbolic-numeric programs in various embedded environments. Interoperability is an important feature which allows mathematical software components written in different programming languages to build on each other. Together these provide an infrastructure for building and deploying the advanced algorithms of the project, in their diverse settings.
The function of memory management was provided in this context by the Customisable Memory Manager (CMM). An earlier version of the CMM had been developed as background to the project and was further developed and refined within the project. The CMM provides a memory management model in which C++ objects can define methods accurately to treat pointers within objects for memory management purposes, and allows multiple heaps obeying different protocols to be used together. The multi-precision integer arithmetic was provided by developing an enhanced version of the GNU multi-precision integer package, GMP.
Experiments showed that the CMM memory manager and the GMP arithmetic package were viable and exhibited reasonable performance under a variety of circumstances and could form the basis of a family of products, and a special version of the Aldor runtime system was constructed using CMM and GMP. During this period several other multi-precision arithmetic packages were developed or enhanced by other investigators outside the project. Performance of the combined CMM-GMP-Aldor runtime system was not so markedly superior to the original runtime system that it was the obvious choice as the sole product platform, and the Aldor developers preferred to keep the option open of using other software as it became available.
The technical aspects of the Common Algebra Runtime are discussed further in chapter 4.
The goal of the Interoperability activity was to allow FRISCO components written in different high-level languages to be able to call and be called by programs written in the most heavily used application programming languages, C++ and Fortran.
The current and envisioned symbolic mathematics products of the
industrial partner, NAG, are based on the Aldor programming language
(formerly known as A
). The main emphasis of the interoperability effort
was therefore directed at interoperability between Aldor and C++
and between Aldor and Fortran. This allows Aldor programs to access FRISCO
components written in C++, and numeric libraries written in Fortran.
Interoperability with C++ addressed both generic questions on the semantic alignment of a static, class-based, object-oriented language with a dynamic, domain-based, abstract-data-type language, as well as specific questions on the detailed interaction between a C++ system and an Aldor system for object interoperability.
Interoperability with Fortran addressed both generic questions of accommodating reference-based parameter passing versus value-based parameter passing, and of numeric data layout for packed real and complex arrays versus cascaded, reference based object arrays, as well as specific questions relating to special low-level calling sequences in passing string data to Fortran functions and the interface needs of specific libraries.
Developing these interoperability mechanisms involved the creation of software tools for the automatic analysis of C++ header files, for the automatic generation of bridging code, and significant modifications to the Aldor compiler. The approach taken in this activity has had a benefit unanticipated in the original project plan: Java has emerged as an important programming language, and the techniques for language interoperability between Aldor and C++ have shown to be workable for Aldor/Java interoperability (in a very preliminary setting).
The above interoperability mechanisms are used in situations where tightly-coupled codes must make use of efficient, direct linkage between component libraries. Additionally, the project investigated mechanisms for flexible linkage of loosely connected components. This activity tracked emerging technology for component architectures, including OLE/Active X from Microsoft and CORBA from the Object Management Group. Demonstrators were developed in both architectural frameworks, establishing that these were indeed suitable for linking large components which need to exchange relatively little data. An additional demonstrator was produced to verify the viability of integration in the MuPad open architecture.
When the data to be exchanged was richer than strings or numbers, it was noted that special purpose objects were required to represent structured mathematical objects such as polynomials. It was noted that for loosely coupled, ``plug-and-play'' components from several sources to interoperate successfully, it would be necessary to have some standard representations for transmitting mathematical objects. This observation has served as the starting point for OpenMath, the ESPRIT fifth framework project 24.969 (Multimedia standards).
A detailed technical presentation of the work on interoperability is provided in chapter 5.
The mathematical activity of the project comprised theoretical advancement in mathematical algorithms and their practical embodiment in software packages.
The basic and arithmetic tools category produced the base elements for use in the various algorithms of the later three categories. Several elements had already been developed in the PoSSo project, but improved versions using more efficient algorithms were required for the advanced solvers. Algorithms for a wide variety of specialised arithmetic domains were produced, including fast Fourier transform arithmetic, infinitesimals, straight-line-program coefficients, algebraic numbers, quotient structures and linear algebra with structured matrices.
The algebraic solving category addressed problems relating to polynomial equations. In general it is not possible to write an explicit exact solution to a system of polynomial equations. The notion of ``solving'' is thus taken more generally to mean a process of transforming a system of equations so that some desired exact information can be more directly read from the system. The sort of questions of interest would include whether the system had a finite or infinite number of solutions, or what is the dimension of the solution space? The specific areas within this category related to methods for extracting information from systems of equations: algorithms based on critical-pair completion, algorithms for computing Gröbner bases based on linear algebra, algorithms based on resultants and duality, and polyalgorithms based on compositions of other methods.
The numerical solving category addressed problems relating to approximate numerical solution of polynomial equations. While a considerable corpus of research has been devoted over the years to the fixed-precision solution of univariate polynomials, the territory of multivariate systems and extended precision methods has had less attention. Accordingly, the project pursued methods for univariate polynomials in extended precision and multivariate methods in machine and extended precision. Nine univariate problems were selected for detailed investigation, including a number of specific algorithms, root isolation, cluster analysis, approximate GCD computation and the treatment of parametric polynomials. The work on multivariate systems covered several completely different approaches, adapted to particular settings. These included homotopy methods, simultaneous approximations, eigenvalues, and iterative methods, among others.
The real solving category addressed problems relating to the geometry of real solutions to polynomial systems. In this context, questions may relate to inequalities as well as equations. The real solving category has been organised broadly into basic algorithms for real equalities and inequalities and real geometry with more advanced algorithms for topological questions and quantifier elimination.
A detailed survey of the algorithms work is provided in chapter 6. There, a summary is presented of the algorithms investigated in the project and a list of resulting publications is given. A follow-on activity of the project is a detailed book with a coherent view of all the algorithms researched in the project, and their relation to each other. The details of the individual algorithms have been provided over the course of the project in the form of reports.
A selection of the algorithms developed within the project were chosen for inclusion in the core libraries delivered. Other algorithms were developed within the framework of the project, but their implementations were preliminary and not stable enough to be incorporated into project libraries.
The core libraries developed by or substantially enhanced for the project include the Aldor algebra libraries (Aldor), the MPSolve package (C), the PoSSo library and ALP (both C++). These libraries implement the most desired of the algorithms developed within the project. Each of these libraries is described in detail in its own sub-section of chapter 7. This chapter also describes how the RealSolving and GB components have been interfaced to Aldor and MuPAD.
Three activities contributed to the relation of the infrastructure and algorithmic work to application areas: an industry needs analysis, the development of demonstrator applications, and workshops and other dissemination activities.
The needs of industry were assessed through a survey and individual interview process described in section 8.1. A number of cases were examined in depth, as described in section 8.1.3. The input received from this analysis led to a greater understanding of the sorts of problems which are of interest in industrial problem solving and drove the strategic choice of mathematical algorithms to be investigated and the prioritisation for their implementation.
The demonstrator applications were developed at partner sites, in collaboration with third parties. These were developed over the lifetime of the project rather than all at the end, in order to provide interim feed-back and to test a number of different software component models. These three applications are described in detail in section 8.3.