We present a parallel algorithm for the solution of tridiagonal linear systems based on the method of partitioning and backward elimination. A givenN#xD7;Nsystem is partitioned intorblocks each of sizen#xD7;n(N=rnneven). Within each block the system is rewritten by collecting pairs of equations from the top and bottom (written backwards); this makes it suitable to solve the subsystem by a UL-factorization of its coefficient matrix. Once a core system of size 2r#xD7; 2rhas been solved, solutions of thersubsystems can be computed in parallel. Interestingly, the serial arithmetical operations count for the present algorithm is 0(1612;N); this makes it faster than the quadrant interlocking factorization method of Chawla and Passi 1, the partitioning method of Wang 7 and cyclic reduction (see Hockney and Jesshope 6, p. 479), each of which has a serial count of 0(17N).
展开▼
