Search

The Collected Algorithms of the ACM (CALGO) is now the longest running journal-published series of algorithms. After placing CALGO in the context of other journal algorithm series, we discuss the factors that we believe have made CALGO the well respected means of publishing mathematical software that it is today. We report on how moving with the times and technology has ensured the survival of CALGO, and we look briefly at how we may continue this in the near future.

Software engineering is not an empirically based discipline. As a result, many of its practices are based on little more than a generally agreed feeling that something may be true. Part of the problem is that it is both relatively young and unusually rich in new and often competing methodologies. As a result, there is little time to infer important empirical patterns of behaviour before the technology moves on. Very occasionally an opportunity arises to study the defect growth and patterns in a well-specified software system which is also well-documented and heavily-used over a long period. Here we analyse the defect growth and structural patterns in just such a system, a numerical library written in Fortran evolving over a period of 30 years. This is important to the wider community for two reasons. First, the results cast significant doubt on widely-held long standing beliefs and second, some of these beliefs are perpetuated in more modern technologies. Since we obviously generalise from older languages to new, it makes good sense to use empirical long-term data when it becomes available to re-calibrate those generalisations. At the same time, the results contain intriguing glimpses into defect behaviour which may transcend whatever technology is in use.

We look in detail at the implementation of a simulation of the spread of Barley Yellow Dwarf Virus in a barley field. The model considers explicitly each individual plant and aphid, therefore it requires special care to reduce the amount of storage used whilst still producing a computationally efficient code. We attempt to quantify the cost of some of the decisions made in terms of their memory and processor time requirements. Finally we briefly consider the visualisation of the results and how the amount of data produced by the model may be reduced to a manageable level.

<< This reports is an updated version of 2-94 >> We describe PIM (Parallel Iterative Methods), a collection of Fortran 77 routines to solve systems of linear equations on parallel computers using iterative methods. A number of iterative methods for symmetric and nonsymmetric systems are available, including * Conjugate-Gradients (CG), * Bi-Conjugate-Gradients (Bi-CG), * Conjugate-Gradients squared (CGS), * the stabilised version of Bi-Conjugate-Gradients (Bi-CGSTAB), * the restarted stabilised version of Bi-Conjugate-Gradients (RBi-CGSTAB), * generalised minimal residual (GMRES), * generalised conjugate residual (GCR), * normal equation solvers (CGNR and CGNE), * quasi-minimal residual (QMR) with coupled two-term recurrences, * transpose-free quasi-minimal residual (TFQMR) and * Chebyshev acceleration. The PIM routines can be used with user-supplied preconditioners, and left-, right- or symmetric-preconditioning are supported. Several stopping criteria can be chosen by the user. In this user's guide we present a brief overview of the iterative methods and algorithms available. The use of PIM is introduced via examples. We also present some results obtained with PIM concerning the selection of stopping criteria and parallel scalability. A reference manual can be found at the end of this report with specific details of the routines and parameters.

We describe the parallelisation of the GMRES(c) method and its implementation on distributed-memory architectures, using both networks of transputers and networks of workstations under the PVM message-passing system. The test systems of linear equations considered are those derived from five-point finite-difference discretisations of partial differential equations.

We show how highly efficient parallel implementations of basic linear algebra routines may be used as building blocks to implement efficient higher level algorithms. We discuss the solution of systems of linear equations using a preconditioned Conjugate-Gradients iterative method on a network of transputers. Results are presented for the solution of both dense and sparse systems; the latter being derived from the finite-difference approximation of partial differential equations.

We present an implementation of a finite-difference approximation for the solution of partial differential equations on transputer networks. The grid structure associated with the finite-difference approximation is exploited by using geometric partitioning of the data among the processors. This provides a very low degree of communication between the processors. The resultant system of linear equations is then solved by a variety of Conjugate Gradient methods. Care has been taken to ensure that the basic linear algebra operations are implemented as efficiently as possible for the particular geometric partitioning used.