6.1 Elimination by rotation matrices

We want to solve the system of linear equations

$$A_{n\times n} \cdot \underline{x}\;=\;\underline{b}\enspace .$$ (6.1)

The first step of the Gauß elimination

$$\begin{pmatrix}1 & 0 & 0 & \cdots \ - \tfrac{a_{21}}{a_{11}} & ... ... 1 & \cdots \ \vdots & \vdots & & \ddots \end{pmatrix} \cdot \underline{b}$$ (6.2)

$\bullet$ is easy to vectorize by means of the DAXPY operation and
$\bullet$ also well to parallelize if an appropriate distribution of the matrix has been chosen.

However the procedure is numerically unstable !

Therefore an additional Pivot search with line/column permutation is accomplished for stabilization. This approach
$\bullet$ is easy to vectorize but
$\bullet$ causes a lot of communication on a distributed memory computer.

Solution $\Rightarrow$ elimination via Givens rotation