Title :
Deterministic computation of the Frobenius form
Author :
Storjohann, Arne
Author_Institution :
Ontario Res. Centre for Comput. Algebra, Univ. of Western Ontario, London, Ont., Canada
Abstract :
A deterministic algorithm for computing the Frobenius canonical-form of a matrix over a field is described. A similarity transformation-matrix is recovered in the same time. The algorithm is nearly optimal, requiring about the same number of field operations as required for matrix multiplication. Previously-known reductions to matrix multiplication are probabilistic.
Keywords :
computational complexity; deterministic algorithms; matrix multiplication; optimisation; Frobenius canonical-form; Frobenius form; deterministic algorithm; deterministic computation; field operations; matrix multiplication; probabilistic reductions; similarity transformation matrix; Algebra; Algorithms; Application software; Bismuth; Computer science; Costs; Polynomials; Shape; Testing;
Conference_Titel :
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN :
0-7695-1116-3
DOI :
10.1109/SFCS.2001.959911
