Copyright 2022 by John Halleck.
All rights reserved except as modified by the
GNU Free Documentation License version 1.3 or later.
Last Edited July 29th, 2023 - John Halleck Minor terminology fixes.
*** This page is truely a work in progress, expect it to change from time to time.
Requires:
Knowing what a triangular matrix is.
Basic familiarity with Matrices (transposes, inverses, identities, ...)
Basic familiarity with Orthogonal Matrices, At least for the definition.
Knowledge of what a "Least Squares" solution is.
Very Basic familiarity with the
Givens Rotation
Some understanding of the "fill in" properties of Givens Rotations.
As shown in my "fill in" properties of Givens Rotations paper. If you do a givens rotation using any two rows of a triangular matrix, trying to zero out one of non-diagonal non-zeros then you WILL introduce non-zeros into the zeros half of triangular matrix. This makes it non-triangular, and loses all the nice mathematical properties of triangular matrices. This therefore defeats the purpose of having triangular matrices in the first place.
Some people might assume that this means that Givens Rotations are not appropriate for triangular matrices.
Here is the critical observation: If you pick two rows, *In Different triangles* of the same
size, and in the same column, and they are both the same numbered row of the respective triangles,
they will have *EXACTLY* the same sparcity pattern. This is true both before and after the Givens rotation.
Fill in can only happen (see the sparsity post referenced above) in the case that one row has a non-zero
value, and the other doesn't. In those specific cases, the zero item becomes non-zero.
For example, using "*" for a value that can possibly be non-zero:
$\begin{bmatrix}
* & & \\
* & * & \\
* & * & * \\
\\
* & & \\
* & * & \\
* & * & * \\
\end{bmatrix}
$
Consider a Givens Rotation of the first row of each triangle to zero out the first item in the first row of the other. The givens rotation is seeing
$\begin{bmatrix}
* & 0 & 0 \\
* & 0 & 0
\end{bmatrix}$
Which can not possibly cause any fill in.
The same reasoning applies to the 2nd row of each... only the first two values can end up with non-zeros.
and so one to the end of whatever size the matrix is.
Of course, if the outer matrix has zero matrices, then there can be fill in when one matrix is zero:
Consider:
$\begin{bmatrix}
* & & \\
* & * & \\
* & * & * \\
\\
0 & & \\
0 & 0 & \\
0 & 0 & 0 \\
\end{bmatrix}
$
In this case,
A Givens of the first row of each will only fill in column 1 in the zeroed matrix.
A Givens of the second row of each will only fill in columns 1, and 2 in the zeroed matrix.
A Givens of the third row of each will only fill in columns 1, 2, and 3 in the zeroed matrix.
So the fillin only makes the zero matrix into another triangular matrix.
Of course, Givens rotation applications need to be applied to the paired rows of every single triangular matrix all the way across the two rows of matrix housing these triangular matrices.
Why triangular matrices? Because they have much lower operation counts for almost anything you would like to do with them. (Even finding the inverse of such a matrix is near trivial.]
Footnotes
1) A massive amount of mathematics is has Gauss' name attached to it. The Gauss in question is Karl Friedrich Gauss, a German Mathematian, who lived 30 April 1777 – 23 February 1855
No comments:
Post a Comment