Numerical Analysis HT24, Givens rotations
Flashcards
Suppose we are using Givens rotations. A typical problem boils down to solving
\[\begin{bmatrix}
c & -s \\\\
s & c
\end{bmatrix}
\begin{bmatrix}
a \\\\
b
\end{bmatrix}
=
\begin{bmatrix}
r \\\\
0
\end{bmatrix}\]
where $r = \sqrt{a^2 + b^2}$ ($\pm r$ are the only possible choices since Givens rotations are orthogonal and so preserve the length).
What values of $c = \cos \theta$ and $s = \sin \theta$ can be used here?
How can you convert an $n \times n$ tridiagonal matrix into an upper triangular matrix using $(n-1)$ Givens rotations?
Iteratively introduce zeroes below the main diagonal.
Bite-sized
What’s the difference in scope between a Givens rotation and a Householder reflector?
A Givens rotation acts locally on two rows/columns at a time. A Householder reflector acts globally on every row/column of the active block. For dense matrices, Householder is more efficient (fewer total ops). For sparse or structured matrices (Hessenberg, tridiagonal, banded), Givens lets you target individual nonzeros and is preferred.
QR on an upper Hessenberg matrix via Givens: $n - 1$ rotations zero the subdiagonal entries at total cost $O(n^2)$, vs Householder QR’s $O(n^3)$ on a dense matrix.