Divide-and-conquer eigenvalue algorithm: Difference between revisions

Revision as of 05:10, 25 January 2020

Revision as of 21:11, 1 January 2022

Line 4:

==Background==

As with most eigenvalue algorithms for Hermitian matrices, divide-and-conquer begins with a reduction to [[Tridiagonal matrix|tridiagonal]] form. For an <math>m \times m</math> matrix, the standard method for this, via [[Householder reflection]]s, takes <math>\frac{4}{3}m^{3}</math> [[flops]]floating point operations, or <math>\frac{8}{3}m^{3}</math> if [[eigenvector]]s are needed as well. There are other algorithms, such as the [[Arnoldi iteration]], which may do better for certain classes of matrices; we will not consider this further here.

In certain cases, it is possible to ''deflate'' an eigenvalue problem into smaller problems. Consider a [[block diagonal matrix]]