Backward triangularization

From Glossary

Jump to: navigation, search

An algorithm to rearrange a matrix by recursively assigning a singleton column to the rear (with its only row as its pivot). The recursion applies to the submatrix defined by omitting the assigned column and row (and reducing remaining column counts accordingly). This results in a lower-triangular rearrangement if and only if such a rearrangement exists. Otherwise, the algorithm reaches a submatrix will all columns having more than one element, of which one is selected to be a spike that is assigned to the rear of the matrix. The process then continues on the submatrix.

Example 1: Let the nonzeros be denoted by *:

LaTeX: 
</p>
<pre> A = \begin{bmatrix}
               * &   &   &     \\
               * & * & * & *   \\
               * &   &   & *   \\
               * &   & * & *
           \end{bmatrix}
</pre>
<p>

The column counts are LaTeX: (4,1,2,3). We thus put column LaTeX: 2 at the rear, assigned to pivot on row LaTeX: 2, and consider the remaining LaTeX: 3\times 3 submatrix:

LaTeX: 
</p>
<pre>A^1 = \begin{bmatrix}
               * &   &   & \cdot &   \\
               * &   & * & \cdot &   \\
               * & * & * & \cdot &   \\
               \cdot & \cdot & \cdot & \cdot & \cdot \\
               * & * & * & \cdot & * 
           \end{bmatrix}
</pre>
<p>

The remaining column counts (for LaTeX: A^1) are LaTeX: (3,1,2), so column LaTeX: 2 is placed at the (new) rear, pivoting on row LaTeX: 3:

LaTeX: 
</p>
<pre>A^2 = \left[\begin{array}{cc|cc}
               * &   &   &     \\
               * & * &   &     \\  \hline
               * & * & * &     \\
               * & * & * & *
           \end{array}\right]
</pre>
<p>

The remaining column counts are LaTeX: (2,1), so we reach the final rearrangement, which is triangular:

LaTeX: 
</p>
<pre>A^3 = \left[\begin{array}{cc cc}
               * &   &   &     \\
               * & * &   &     \\
               * & * & * &     \\
               * & * & * & *
           \end{array}\right]
</pre>
<p>

Example 2: Column counts are shown below the matrix.

LaTeX: 
</p>
<pre>\begin{array}{l}
      A = \left[\begin{array}{cccc}
               * &   &   &     \\
               * & * & * & *   \\
               * & * &   & *   \\
               * &   & * & *
           \end{array}\right] \\
  \phantom{A = \left[\right.}~
           \begin{array}{cccc}
              4 & 2 & 2 & 3
           \end{array}
  \end{array}
</pre>
<p>

All column counts are greater than one, so we select a column to be a spike, and we assign it to the rear with a pivot row (some algorithms delay the pivot row assignment). For this example, we choose a column with minimum count and pick the pivot row with maximum count.

LaTeX: 
</p>
<pre>\begin{array}{l@{\,\Rightarrow\,}l}
      A^1 = \left[\begin{array}{ccc | c}
               * &   &   &     \\
               * & * &   &     \\
               * &   & * & *   \\ \hline
               * & * & * & *
           \end{array}\right]
    & A^2 = \left[\begin{array}{cc |cc}
               * &   &   &     \\
               * & * &   & *   \\ \hline
               * &   & * &     \\
               * & * & * & *
           \end{array}\right] = A^3.
  \end{array}
</pre>
<p>

The final rearrangement (LaTeX: A^3) has one spike.


Views
Personal tools