Supervisor: Jagdish Modi

Special Resources: None

Dijkstra’s algorithm (see [2]) is essentially serial and does not parallelise well to lead to a performance improvement. An alternative method involves using an analogue of matrix multiplication, in which we find the minimum of a sum of weights (route-lengths), instead of forming a sum of products. By repeatedly ‘multiplying’ the route matrix with itself, we can find the lengths of the shortest paths between all pairs of destinations. Since matrix multiplication is a highly parallel operation, this method is well suited to parallel computation.

The aim of the project is to implement such an algorithm, applying it to part of the National rail network. Furthermore, if possible to consider such developments as improving the efficiency of computation by avoiding large sparse areas in order to minimise data movements using the Fox-Otto algorithm [3,4].

Further developments might include:

- If there are two or more lines through any particular station S then for journeys via S with a possible change of trains there, S must be treated as S1, S2, …, one for each line , with time from, for example, S1 to S2 referring to the expected wait, calculated from the frequencies of services, when changing trains.
- Identifying and temporarily removing nodes that are not necessary for computing the shortest paths can reduce the processor connectivity.

Parallel computers have as a core structure a set of interconnected processors. The optimal choice of interconnection for a particular problem may not always be available. In fact, in practice the interconnection usually takes place within some sort of plane two- dimensional lattice. In the consideration of the parallel algorithm, it would be interesting to explore the features of the two-dimensional graph arising from the connections between destinations (edges), and to relate this to the lattice of processor connectivity. If the student is mathematically inclined, it may be worthwhile to investigate certain properties possessed by the processor graph, such as degree of symmetry and homogeneity [5], as well as the extent to which it can be embedded in a lattice.

[2] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, second edition, 2003.

[3] Grama, Gupta, Karypis, Kumar. Introduction to Parallel Computing, Pearson Education, second edition, 2005.

[4] Akpan, O. Efficient parallel implementation of the Fox algorithm. Computer Science Department, Bowie State University, 2003.

[5] Modi J. Parallel Algorithms and Matrix Computation, OUP, 1988.