Please use this identifier to cite or link to this item:
|Title:||ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM|
|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 , 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.|
|Appears in Collections:||Eberly, Wayne|
Files in This Item:
|2000-649-01.pdf||412.41 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.