EFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRAS

Simple item page
dc.contributor.authorEberly, Wayneeng
dc.date.accessioned2008-02-26T20:31:26Z
dc.date.available2008-02-26T20:31:26Z
dc.date.computerscience1999-05-27eng
dc.date.issued1990-08-01eng
dc.description.abstractWe 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.eng
dc.description.notesWe 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.caeng
dc.identifier.department1990-399-23eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30589
dc.identifier.urihttp://hdl.handle.net/1880/45471
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleEFFICIENT ALGORITHMS FOR THE DECOMPOSITION OF MATRIX ALGEBRASeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
1990-399-23.pdf
Size:
3.44 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications