A parallel programme for robust eigenvalue localization

International audienceFor localizing some eigenvalues of a given large sparse matrix in a domain of the complex, and taking into account possible perturbations of the matrix, the notion of the of $\epsilon$-spectrum or pseudospectrum of a matrix $A \in \IRnn$ was separately defined by Godunov and Trefethen. Determining an $\epsilon$-spectrum consists of determining a level curve of the 2-norm of the resolvent $R(z)=(zI-A)^{-1}$. A dual approach can be considered: given some curve $(\Gamma)$ in the complex plane, count the number of eigenvalues of the matrix $A$ that are surrounded by $(\Gamma)$. The number of surrounded eigenvalues is determined by evaluating the integral $\frac{1}{2i\pi} \int_{\Gamma}{\frac{d}{dz}\log \det (zI-A) dz}$. This problem was considered in [Bertrand and Philippe, 2001] where several procedures were proposed and more recently in [Kamgnia and Philippe, 2013] where the stepsize control in the quadrature is thoroughly studied. The present goal is to combine the following two approaches: (i) consider the method {\sc pat} [Mezher and Philippe, Parallel Comput., 2002],[[Mezher and Philippe, Numer. Algorithms, 2002] which is a path following method that determines a level curve of the function $s(z)=\sigma_{\min}(zI-A)$; (ii) apply the method {\sc eigencnt} of [Kamgnia and Philippe, 2013] for computing the number of eigenvalues included. The combined procedure will be based on a computational kernel which provides both $(\sigma_{\min}(zI-A)$, and $\det (zI-A))$ for any complex number $z\in \IC$. These two numbers are obtained making use of a unique LU factorization of $(zI-A)$. The approach implements a multilevel parallelism: the first level of parallelism involves the independent computations of LU factorizations; the second level is introduced through a preprocessing transformation similar to the approach developed in {\sc spike} [Polizzi and Sameh, 2006], [Kamgnia, Nguenang, and Philippe, 2012]