Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite

Ignoring eigenvectors, the shifted QR algorithm for computing eigenvalues in the symmetric tridiagional case costs $O(n)$ per iteration, converges globally, and converges cubically near the end. What is its worst case complexity (which presumably depends on the desired error)?

share|improve this question

1 Answer

up vote 4 down vote accepted

With the right shift stategy (mixing RQ and W shift appropriately), it is globally cubically convergent, with a guaranteed linear convergence factor, which makes its complexity of the order of $N$ times the logarithm of the off-diagonal entries. Unfortunately,

See http://www.springerlink.com/content/f1w76x84463l52t7/ for local cubic convergence.

share|improve this answer
Does that mean there is no entry-independent worst case upper bound? – Geoffrey Irving Aug 13 '12 at 20:18
Probably no known one. But my knowledge about this is about 10 years old, so you should check more recent literature. – Arnold Neumaier Aug 14 '12 at 7:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.