Tuesday, November 18, 2003

"Of course, just knowing that these work on such a small matrix doesn’t mean that we can determine absolute worth. For example, the dynamic shifted inverse power method of doom takes significantly more steps per iteration than the shifted inverse power method, but tends to converge much, much faster. If one were to simply look at time, it turns out that, in fact, it depends. Of course. The nondynamic method went faster (though possibly just due to machine speed – a larger matrix would be a better test, however the larger matrix felt it was it’s patriotic duty to kill the machine. Twice.) "

"Of course, right off, one has to be suspicious of a matrix which looks so very, very sketchy in terms of order. There does not seem to be any real, rational reason why we would use this matrix to test our code. There is.

By running this matrix through our original power method code, we get the following as an eigenvalue:

-0.8748

This is, well, not one. The eigenvalues (as calculated by, again, our friend eig(A) in Matlab) are ¼, -1/3, ½, 1, and –1. Of course, the problem we can see right off is that |1| = |-1|, so the code is simply unable to converge upon an eigenvalue, even after 100 iterations. It is lost like a penguin in a lava flow. Thankfully, we have all sorts of code to throw at this – and the other method we’ll try is the QR-factorization method"

Obviously, as you take such a ratio raised to successively higher powers, one becomes dominant, and the code can return it. Lovely. Except that it requires us to have both: A) An eigenvalue which is larger in magnitude than every other eigenvalue and B) A clearly dominant eigenvalue, or else it could take (to steal from Carl Sagan) billions, and billions, and billions of iterations