COMPUTATION OF PSEUDOSPECTRA USING ARPACK AND EIGS

Thomas Wright

Oxford University Computing Laboratory,
Wolfson Building, Parks Road,
Oxford, OX1 3QD, England.


Abstract

For highly non-normal matrices, pseudospectra may provide useful information in addition to eigenvalues. Unfortunately, computing pseudospectra is expensive for large matrices; the straightforward algorithm for an N by N matrix using a grid of size v by v takes O(v2N3) time. This can often be improved by a factor of around N/4 using a variety of methods, but even with this saving the algorithm is still too slow to make it a practical tool for large matrices.

In light of the above, one might think that pseudospectra could be computed more efficiently using iterative rather than direct methods. It has already been shown that the upper Hessenberg matrix constructed during an Arnoldi iteration can be used to give a reasonable approximation to the pseudospectra of the original matrix. Here, I consider an extension to the Matlab iterative eigenvalue solver `eigs' (based on the Fortran code ARPACK), which allows the pseudospectra to be computed in a region around the eigenvalues calculated. This will provide the user of eigs with graphical information that may highlight cases in which the accuracy of the eigenvalues returned should be carefully investigated. Due to the size of the Hessenberg matrices constructed, this method is much more efficient than the direct method (locally, at least), and for large matrices an approximation to the pseudospectra can be computed along with the eigenvalues for a relatively small additional cost.

We plan to demonstrate the above idea using an interactive Matlab GUI.