next up previous

7 Gaussian Elimination on Band Matrices     continued...

Most of the parallel approaches perform more arithmetic operations than standard (sequential) Gaussian elimination (typically times as many), twisted factorization being the only exception. In twisted factorization the Gaussian elimination process is carried out in parallel from both sides. This method was first proposed in [39] for tridiagonal systems Tx=b as a means to compute a specified component of x more accurately. For a tridiagonal matrix twisted factorization leads to the following decomposition of T:

or T=PQ, where we have assumed that no zero diagonal element is created in P or Q. Such decompositions exist if A is symmetric positive definite, or if A is an M-matrix, or when A is diagonally dominant. The twisted factorization and subsequent forward and back substitutions with P and Q take as many arithmetic operations as the standard factorization, and can be carried out with twofold parallelism by working from both ends of the matrix simultaneously. For an analysis of this process for tridiagonal systems, see [40]. Twisted factorization can be combined with any of the following techniques, often doubling the parallelism.