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.
