Computational Algebra Seminar: Villard -- Computing matrix determinants and adjoints without divisions

Speaker: Gilles Villard (CNRS, U. Lyon, INRIA)
Title: On computing matrix determinants and adjoints without divisions
Time & Place: 3-4pm, Thursday 27 November, Eastern Ave Seminar Rm 311

Abstract:
We study complexity estimates for computing nxn matrix determinants
and adjoints over an abstract ring R. Using a block Krylov
approach, together with Strassen’s avoidance of divisions, Kaltofen
(1992) and Kaltofen & Villard (2004) propose an algorithm for
computing the determinant in O(n^(2.7))  additions, subtractions,
and multiplications. This is currently the best known complexity
estimate for the problem. We will give an insight into the method,
especially into its  baby steps/giant steps strategy.

By the results of Baur and Strassen (1983), the determinant
algorithm, actually a straight-line program, leads to an algorithm
with the same complexity for computing the adjoint of a matrix.
However, the latter adjoint algorithm is obtained by the reverse
mode of automatic differentiation, hence somehow is not
"explicit".  We present an alternative (still closely related)
algorithm for the adjoint that can be implemented directly, by
which we mean without resort to an automatic transformation.
The algorithm is deduced by applying program differentiation
techniques "by hand" to the determinant program, and is completely
described.