Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45471
Title: EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS
Authors: Eberly, Wayne
Keywords: Computer Science
Issue Date: 1-Aug-1990
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.
URI: http://hdl.handle.net/1880/45471
Appears in Collections:Eberly, Wayne

Files in This Item:
File Description SizeFormat 
1990-399-23.pdf3.52 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.