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.

Numerical Linear Algebra (acm G.1.3), PHYSICAL SCIENCES AND ENGINEERING (acm J.2)
Direct methods for linear systems and matrix inversion (msc 65F05), Iterative methods for linear systems (msc 65F10), Sparse matrices (msc 65F50), Parallel computation (msc 65Y05)
CWI
Department of Numerical Mathematics [NM]

van der Ploeg, A. (1996). Reordering strategies and LU-decomposition of block tridiagonal matrices for parallel processing. Department of Numerical Mathematics [NM]. CWI.