ASYMPTOTICALLY EFFICIENT ALGORITHMS FOR THE FROBENIUS FORM
Date
2000-05-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science