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
IANCNR
Pavia, Italy
ABSTRACT
The e
pseudospectrum of a matrix,
defined for example as
L_{e} (A) =
{z: z Î L(A+E)
for some E Î C^{n 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)
matrixdependent algorithms, ranging from iterative methods for large linear
systems to timestepping 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 zIA 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)115, 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 L_{e}(A) = {z Î C^{n x n} : (zIA)^{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.