I'm familiar with the QR algorithm for eigen decomposition in symmetric matrices, which takes roughly O(n^3) time. But that O(n^3) only holds if you take a constant number of QR steps per eigenvalue, and I don't know of any convergence guarantees (say in Frobenius distance, or anything else sensible) within that time.

So are there any theoretical runtime guarantees I can make about an eigen decomposition (symmetric matrix or otherwise) for a given allowable numerical error?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.