ABSTRACT
This chapter examines the algorithms that are suitable for the solution of a range of common problems on parallel computers. If the parallelism in the algorithm matches the parallelism of the computer it is almost certain that a high-performance code can be written by an experienced programmer. The objective of a good programmer/numerical analyst is to find a method of solution that makes the best match between the parallelism of the algorithm and the natural parallelism of the computer. The parallelisation of a program for mimd computation is likely to require much more programmer intervention than the vectorisation of a program for simd computation, and might even necessitate the complete restructuring of the whole program. The chapter discusses the problem of introducing parallelism into Buneman direct methods and alternatively the adoption of new algorithms, such as cyclic reduction, that are inherently more parallel.
