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.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca