Parallelization and vectorization aspects of the solution of tridiagonal linear systems

We are concerned with the parallel solution of large tridiagonal systems on message-based MIMD computers with vector processors. A subset of equations is assigned to eacg process. The algorithms we present consist of 'local', fully parallel parts (based on a modified cyclic reduction), and a 'global' part. The latter requires the solution of an 'interface system' with couplings between all processes; only here is communication required. We present several strategies and compare them theoretically as well as by concrete tests on the iPSC2-VX.