ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM

Simple item page
dc.contributor.authorEberly, Wayneeng
dc.date.accessioned2008-02-26T20:31:05Z
dc.date.available2008-02-26T20:31:05Z
dc.date.computerscience2000-05-03eng
dc.date.issued2000-05-03eng
dc.description.abstractA new randomized algorithm is presented for computation of the Frobenius form of an n x n matrix over a field. A version of the algorithm is presented that uses standard arithmetic whose asymptotic expected complexity matches the worst case complexity of the best known deterministic algorithm for this problem, recently given by Storjohann and Villard [25], and that seems to be superior when applied to sparse or structured matrices with a small number of invariant factors. A version that uses asymptotically fast matrix multiplication is also presented. This is the first known algorithm for this computation over small fields whose asymptotic complexity matches that of the best algorithm for computations over large fields and that also provides a Frobenius transition matrix over the ground field. As an application, it is shown that a "rational Jordan form" of an n x n matrix over a finite field can also be computed asymptotically efficiently.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.department2000-649-01eng
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/30585
dc.identifier.urihttp://hdl.handle.net/1880/45467
dc.language.isoEngeng
dc.publisher.corporateUniversity of Calgaryeng
dc.publisher.facultyScienceeng
dc.subjectComputer Scienceeng
dc.titleASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORMeng
dc.typeunknown
thesis.degree.disciplineComputer Scienceeng
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
2000-649-01.pdf
Size:
412.41 KB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
2000-649-01.ps
Size:
579.05 KB
Format:
Postscript Files
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.86 KB
Format:
Plain Text
Description:
Download
Collections
Science Research & Publications