×

zbMATH — the first resource for mathematics

Fast algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of a matrix. (English) Zbl 1248.65034
The paper presents new algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of an \(n\times n\) matrix, based on the computing only the spectral abscissa or radius of a sequence of matrices, generating a sequence of lower bounds for the pseudospectral abscissa or radius.
The first section is an introductory one.
In the second section, the authors give some definitions, basic lemmas and an assumption representing the main hypothesis of the paper.
The third section presents a new algorithm which generates a sequence of lower bounds for the pseudospectral abscissa, mainly intended for large sparse matrices.
The fourth section focuses on the characterization of the fixed points of the map associated with the iterative method. The authors argue that, at least in practice, the only attractive fixed points correspond to local maximizers of the \(\varepsilon\)-\(pseudospectral\; abscissa\) of an \(n\times n\) real or complex matrix \(A:\) \[ \alpha_\varepsilon(A)=\max\{Re\,z:\sigma_n(A-zI)\leq\varepsilon\},\tag{1} \] \(\sigma_k(A)\) denoting the \(k\)th largest singular value of \(A.\)
The fifth section derives a local convergence analysis which depends on a perturbation theorem for the normalized eigenprojection of the matrix and on a characterization of the group inverse (reduced solvent) of a singular matrix defined by a rank-one perturbation. The results establish that the algorithm is linearly convergent to local maximizers of ({1}) for sufficiently small \(\varepsilon,\) but in practice the authors find that convergence takes place for much larger values of \(\varepsilon.\)
The sixth section presents a modification of the algorithm which guarantees that it generates a monotonically increasing sequence of lower bounds for the spectral abscissa, independent of \(\varepsilon\).
In the seventh section the authors extend the ideas discussed for the pseudospectral abscissa to the computation of the pseudospectral radius.
The numerical implementation of the presented algorithms for computing the pseudospectral abscissa and pseudospectral radius is presented in the section eight on large dense matrices, respectively, in the section nine on large sparse matrices.
The main conclusions and the future work are presented in the last section.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
Software:
Eigtool; ARPACK; PSAPSR
PDF BibTeX Cite
Full Text: DOI