The Real Two Zero algorithm: A parallel algorithm to reduce an arbitrary matrix to a real Schur form, and, Jacobi-sets for parallel computations.

摘要

We describe, in this dissertation, our contribution to two important aspects of the eigenvalue problem. The most significant one: we introduce a new method to reduce a real matrix to a real Schur form by a sequence of orthogonal transformations where each orthogonal matrix is a 3-space symmetric matrix. Two significant features of this method are that, one, all the transformed matrices and all the computations are done in the real field and, two, it can be easily parallelized. This is the first such Jacobi-type parallel algorithm and we call it the Real Two Zero (RTZ) algorithm. Its serial and parallel implementations are described in detail. Our tests indicate that the rate of convergence to a real Schui form is quadratic for real near normal matrices with real distinct eigenvalues.;Our second contribution is in the area of parallel orderings. Some Jacobi-type algorithms use an ordering on the pairs in ;Lack of variety and clarity in the existing algorithms motivated us to develop new algorithms to generate Jacobi-sets. We present three new algorithms and prove that each generate complete Jacobi-sets. Our proofs are interesting in themselves, using combinatorial properties of the hypercube topology; further, they are novel in their approach. By relating complete Jacobi-sets to a 1-factorization of a complete graph, we establish that the orderings generated by these algorithms are non-isomorphic.