PARALLEL FACTORIZATIONS FOR TRIDIAGONAL MATRICES

The authors analyze the problem of solving tridiagonal linear systems on parallel computers. A wide class of efficient parallel solvers is derived by considering different parallel factorizations of partitioned matrices. These solvers have a minimum requirement of data transmission. In fact, communication is only needed for solving a ''reduced system,'' whose dimension depends on the number of parallel processors used. Moreover, for a given partitioned tridiagonal matrix, the reduced system (which is again tridiagonal) is the same, and represents the only sequential part of the corresponding parallel solver. Three examples are discussed in more detail; one of them derives a very efficient parallel method based on the cyclic reduction algorithm.