EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS
Date
1990-08-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science