On the computational effectiveness of transfer function approximations to the matrix pseudospectrum.

C. Bekas and E. Gallopoulos
Department of Computer Engineering and Informatics University of Patras Greece

V. Simoncini
IAN-CNR Pavia, Italy


ABSTRACT

The e- pseudospectrum of a matrix, defined for example as

Le (A) = {z: z Î L(A+E) for some   E Î Cn x n with || E || £ e}
where L(A) denotes the spectrum of A, is acknowledged to be a powerful mechanism for investigating the behavior of several (nonnormal) matrix-dependent algorithms, ranging from iterative methods for large linear systems to time-stepping algorithms; note the inclusion of specific functions to that effect in the popular Test Matrix Toolbox of MATLAB. The standard workhorse method for computing pseudospectra is the following: i) Discretize the region of interest in the complex plane and ii) compute the minimum singular value of the matrix zI-A at every gridpoint z. This algorithm is simple, robust, embarassingly parallel and extremely expensive even for medium sized matrices: Much more expensive than having to compute matrix spectral information, such as eigenvalues and singular values. In other words, pseudospectra are powerful but we must find ways for obtaining them at lesser cost. ``Domain oriented'' methods for computing pseudospectra attempt to reduce the number of gridpoints while ``matrix oriented'' methods attempt to obtain the singular values faster. Toh and Trefethen (SIAM J. Sci. Comput. 17(1)1-15, 1996) have studied the following matrix oriented approach: Apply Arnoldi to compute from A a Hessenberg matrix of smaller dimension and approximate the pseudospectrum from the singular values of H or the corresponding augmented Hessenberg matrix. This has the potential to offer great computational savings as it only requires SVD calculations for a Hessenberg matrix of smaller size, but as shown in the aforementioned article, there are cases where the method does not perform well. In recent work we have shown, based on the equivalent definition of the matrix pseudospectrum that is based on resolvents Le(A) = {z Î Cn x n  :     ||(zI-A)-1|| ³ e-1} , that one promising improvement to the Arnoldi approaches is to utilize a transfer function formulation that provides a better approximation to the pseudospectrum. In this talk we will present computational issues related to this method and investigate its effectiveness compared to existing approaches for computing pseudospectra.