On swapping diagonal blocks in real Schur form (Q1801449)

The authors consider the following problem which arises in computational algebra. Suppose that a real square matrix has been reduced by conjugation to an upper block-triangular matrix \(T\) where the diagonal blocks of \(T\) are either \(1\times 1\) (corresponding to the real eigenvalues) or \(2\times 2\) (corresponding to pairs of complex conjugate eigenvalues). In some cases it may be important to conjugate further in order to reorder the diagonal blocks of \(T\) into some prescribed order. Two general techniques for doing this have been proposed: one uses \(QR\) iterations [see \textit{G. W. Stewart}, \(HQR3\) and \(EXCHNG\): Fortran subroutines for calculating and ordering the eigenvalues of a real upper Hessenberg matrix \([F2]\). ACM Trans. Math. Software, 2, 275-280 (1976)] and the other is called the ``direct swapping method'' [see \textit{J. J. Dongarra}, \textit{S. Hammarling} and \textit{J. H. Wilkinson}, SIAM J. Matrix Anal. Appl. 13, No. 1, 145-161 (1992; Zbl 0754.65038)]. Both methods have some disadvantages since the first sometimes fails to exchange blocks, and the latter sometimes fails to be stable. The present paper describes a modification of the latter method to improve its accuracy and robustness, and gives theoretical and experimental evidence to show that this modification is superior to the earlier algorithms.