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.