Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45467
Title: ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM
Authors: Eberly, Wayne
Keywords: Computer Science
Issue Date: 3-May-2000
Abstract: A 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.
URI: http://hdl.handle.net/1880/45467
Appears in Collections:Eberly, Wayne

Files in This Item:
File Description SizeFormat 
2000-649-01.pdf412.41 kBAdobe PDFView/Open
2000-649-01.ps579.05 kBPostscriptView/Open


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