The real two-zero algorithm: a parallel algorithm to reduce a real matrix to a real Schur form

摘要

We introduce a new method to reduce a real matrix to a real Schur form by a sequence of similarity transformations that are 3D orthogonal transformations. Two significant features of this method are that: all the transformed matrices and all the computations are done in the real field; and it can be easily parallelized. We call the algorithm that uses this method the real two-zero (RTZ) algorithm. We describe both serial and parallel implementations of the RTZ algorithm. Our tests indicate that the rate of convergence to a real Schur form is quadratic for real near-normal matrices with real distinct eigenvalues. Suppose n is the order of a real matrix A. In order to choose a sequence of 3D orthogonal transformations on A, we need to determine some ordering on triples in T={(k,l,m)|1/spl les/k>l>m/spl les}, where (k,l,m) defines the three coordinates under the 3D transformation. We show how the ordering of the triples used in our implementations can be generated cyclically in an algorithm.