Reordering strategies and LU-decomposition of block tridiagonal matrices for parallel processing

Solution of large sparse systems of linear equations continues to be a major research area with widespread application. In many applications, the unknowns appear in groups, and the coefficient matrix has a block structure corresponding to these groups. For example, in discretised incompressible Navier-Stokes equations the velocities and the pressure belonging to the same grid point form such a group. Another example arises in molecular hydrodynamics computations when a combination of a finite element discretisation in a given spatial direction and a Fourier decomposition in other directions is used. In many cases, it appears to be important to be able to solve block tridiagonal systems efficiently. A possible strategy for obtaining parallelism is to apply a reordering of the unknowns before a decomposition of the coefficient matrix is constructed. In this paper, we compare reordering strategies based on block cyclic reduction and on domain decomposition. Estimates of the number of floating point operations and the amount of data transport will be discussed, and results on a CRAY C90 and CRAY T3D will be presented.