I've been writing a small library in C to perform various matrix operations, and one of them involves finding the eigenvalues of the matrix.
I've decided to use a shifted variant of the QR-Factorization algorithm to do this. I've chosen the Wilkinson shift because of it ensures convergence in special cases where a Rayleigh-shift does not.
The algorithm I'm using is as follows:
$A^0$ = Hessenberg(A)
for k = 1 : ...
Select $\mu^{k}$ (Shift)
[$Q^{k},R^{k}$] = qr($A^{k-1} - \mu^{k} \cdot I$)
$A^{k} = R^{k} Q^{k} + \mu^{k} \cdot I$
End For
As I mentioned, the shift used is the Wilkinson Shift. It is defined as follows. Given a $2\times 2$ sub-matrix $B$ of $A$:
$\begin{matrix} a_{m-1} & b_{m-1} \\ b_{m-1} & a_{m} \end{matrix}$
I attempt to compute the closest estimate to the eigenvalue of the sub matrix using the following equation ($\mu$):
$\mu_{k} = a_{m} - \frac{sign(\delta)\ b_{m-1}^{2} }{ |\delta | + \sqrt{\delta^{2} + b_{m-1}^{2}}}$
Where $\delta = \frac{a_{m-1} - a_{m}}{2}$
Here's where my first problem arises. For one, I can have different values for both of the $b_{m-1}$'s in the Matrix B, so the equation I'm using (From this resource on slides 11,16,17) is ambiguous. How do I know which one to pick?!
I currently pick the upper one for the top of the equation and the lower one for the bottom, since nothing seems to affect the performance of my algorithm so far. The only problem arises when actually solving for eigenvalues. Given a matrix like:
$\begin{matrix} 14 & -11 & -146 & -120 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}$
My algorithm takes a good couple seconds to find the answer. While an online solver can find it near instantly. I'm not sure where I'm underperforming here. I do know though, that I do not perform a so-called deflation on the problem matrix when I've found an eigenvalue. The thing is, I'm not actually sure when to perform this deflation.
Do I do it right after computing my estimate for the eigenvalue of sub matrix B? I guess I'm just a little lacking in understanding exactly what situations need to transpire in order to perform a deflation. If anyone can assist in clarifying on this point and provide some explanation for my problem with the ambiguity about the shift equation, I'd be very grateful!
Thank you for your time.