| The eigenvalues and eigenvectors of a Hessenberg matrix H are computed with a combination of homotopy increments and the Arnoldi method. Given a set, O, of approximate eigenvalues of H, there exists a unique vector f = f (H ,O) ∈ Rn where lambda(H -- e 1 ft) = O. A diagonalization of the homotopy H(t) = H -- (1--t)e1f t at t = 0 provides a prediction of the eigenvalues of H(t) at later times. These predictions define a new O that defines a new homotopy. The correction for each eigenvalue has an O(t 2) error estimate, enabling variable step size and efficient convergence tests. Computations are done primarily in real arithmetic, and bifurcations are avoided by restarting the homotopy with Arnoldi eigenvalues. Although the method is neither as elegant nor as robust as the QR algorithm, it is about twice as fast in the randomly generated examples considered and is highly parallelizable. |
