EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS

Abstract

We consider the bit-complexity of the decomposition of semi-simple algebras over finite fields and number fields, and of simple algebras over C and R, for matrix algebras with bases consisting of matrices over a number field. Exact computations in number fields are performed symbolically. We present new probabilistic and deterministic polynomial-time algorithms for the decomposition of semi-simple algebras over the above concrete fields. The algorithms are somewhat simpler than the algorithm previously given by Friedl and Ronyai; the probabilistic algorithm suggests a modification that might improve the performance of the original algorithm in the average case. The new methods also provide parallel (NC) reductions from the decomposition of semi-simple algebras to the problem of factoring polynomials over fields, as well as efficient parallel algorithms for the decomposition of semi-simple algebras over (small) finite fields. We also extend the methods of Eberly [8] and Babai and Ronyai [1] for the decomposition of simple algebras over C, to obtain a new probabilistic polynomial-time algorithm for the decomposition of simple algebras over R. This is the first (Boolean) polynomial-time algorithm for this problem.