Towards the effective parallel computation of matrix pseudospectra

Given a matrix A, the computation of its pseudospectrum Λ_ε(A) is a far more expensive task than the computation of characteristics such as the condition number and the matrix spectrum. As research of the last 15 years has shown, however, the matrix pseudospectrum provides valuable information that is not included in other indicators. So, we ask how to compute it efficiently and build a tool that would facilitate engineers and scientists to make such analyses? In this paper we focus on parallel algorithms for computing pseudospectra. The most widely used algorithm for computing pseudospectra is embarassingly parallel; nevertheless, it is extremely costly and one cannot hope to achieve absolute high performance with it. We describe algorithms that have drastically improved performance while maintaining a high degree of large grain parallelism. We evaluate the effectiveness of these methods in the context of a MATLAB-based environment for parallel programming using MPI on small, off-t he-shelf parallel systems.