Symbolic Computation Group
David R. Cheriton School of Computer Science


Friday, February 9, 2007, at U. of Western Ontario.
Abstract:
Since the introduction of subcubic matrix multiplication algorithms,
block algorithms have been designed to reduce the complexity of most
classical problems in linear algebra to that of the matrix multiplication:
O(n^omega).However the best known algorithm for the computation of the
characteristic polynomial, by KellerGehrig, still involves a logarithmic
number of matrix multiplications resulting in O(n^omega log n) field
operations. KellerGehrig also proposed a O(n^omega) algorithm, but
this was only valid with generic matrices.

Last modified on Sunday, 04 November 2012, at 20:42 hours.