RealPSPA

Criss-cross type algorithms for computing real pseudospectral abscissa.

Description

RealPSPA implements in MATLAB, the criss-cross algorithm for computing the real \(\varepsilon\)–pseudospectral abscissa of a real matrix \(A\in {\mathbb R}^{n\times n}\):

\[ \alpha_\varepsilon^{\mathbb R}(A) =\max \left\{\mbox{Re}(\lambda)\, \colon\, \lambda \in \Lambda_{\varepsilon}^\mathbb R(A)\right\}, \]

where

\[ \Lambda_{\varepsilon}^ \mathbb R (A) = \left\{\lambda \in \mathbb C: \lambda \in \Lambda(A+E) \mbox{ with }E\in \mathbb R^{n\times n}, \|E\|_2\leq \varepsilon \right\}, \]

and \(\Lambda(A)\) denotes the eigenvalues of a matrix.

This package contains functions suitable for both dense and large sparse matrices \(A\). A detailed description of the algorithms can be found in the paper Ref. [1].

Authors

Contents

Main files

Auxiliary files

Data and demo routines for numerical examples in Ref. [1].

Use of the code

Permission to use, copy,and modify this software for any purpose and without fee is hereby granted. For publications that uses this software, a reference to the paper, Ref. [1] below, will be appreciated.

Examples

See Ref. [1] for details.

I. Criss-cross methods: rpsa

RPSA: Demmel 3 

Fig. I.a: Demmel 3–by–3 matrix, \(\varepsilon=10^{-3.2}\).

  • Black line: boundary of \(\Lambda_{\varepsilon}^{\mathbb R}(A)\);

  • Colored line: boundary of supersets used in each criss-cross iteration;

  • Mark \(\mathtt o\): approximate rightmost point.

RPSA: Demmel 5 

Fig. I.b: Demmel 5–by–5 matrix, \(\varepsilon=10^{-2}\). First 3 iterations, same figure setting as above.

II. Criss-cross + subspace methods: rpsas — (eig mode)

RPSAS Grcar 100 

Fig. II.a: Grcar(100) matrix, \(\varepsilon=0.3\), iterations k= 1, 2, 4.

  • Black line: boundary of \(\Lambda_\varepsilon^\mathbb R(A)\);

  • Blue line: boundary of the reduced \(\Lambda_\varepsilon^\mathbb R(AV_k,V_k)\);

  • Mark +: approximate rightmost point in kth itration.

RPSAS -Grcar 100 

Fig. II.b: \(-\)Grcar(100) matrix, \(\varepsilon=0.2\), iterations k= 1, 2, 5.

Same figure setting as above.

References

  1. Criss-cross type algorithms for computing the real pseudospectral abscissa
    by Ding Lu and Bart Vandereycken
    SIAM J. Matrix Anal. Appl., 2017. 38(3):891–923. (paper)

Release notes

Contact

Email: Ding.Lu@uky.edu
Homepage: http://www.ms.uky.edu/~dlu245/