Fast Parallel Algorithms for Matrix Reduction to Normal Forms

摘要

We investigate fast parallel algorithms to compute normal forms of matrices and the corresponding transformations. Given a matrix B in ?n,n(K), where K is an arbitrary commutative field, we establish that computing a similarity transformation P such that F=P-1BP is in Frobenius normal form can be done in —C2K. Using a reduction to this first problem, a similar fact is then proved for the Smith normal form S(x) of a polynomial matrix A(x) in ?n,m(K[x]); to compute unimodular matrices U(x) and V(x) such that S(x)=U(x)A(x)V(x) can be done in —C2K. We get that over concrete fields such as the rationals, these problems are in —C2. Using our previous results we have thus established that the problems of computing transformations over a field extension for the Jordan normal form, and transformations over the input field for the Frobenius and the Smith normal form are all in —C2K. As a corollary we establish a polynomial-time sequential algorithm to compute transformations for the Smith form over K[x].