Computation of the real Schur decomposition of nonsymmetric matrices and its hardware implementation

A VLSI-suited processor array is presented that performs a Jacobi-like parallel algorithm for computing the real Schur decomposition of real nonsymmetric (n×n) matrices. The array consists of n²/4 processor cells which only perform exchange operations and elementary (2×2) plane rotations. The underlying algorithm iterates on dense matrices, i.e., the matrices need not to be reduced to some canonical form in advance. The iteration algorithm is derived by a problem adapted discretization process of an equivalent dynamical system. The dynamical system belongs to the class of isospectral matrix flow equations, i.e. a matrix valued differential equation, whose time evolution converges for t→∞ to upper quasi triangular form. The integration scheme is performed by computing some highly regular orthogonal matrix-matrix multiplications