SMS scnews item created by (unknown) at Tue 25 Nov 2008 1523
Type: Seminar
Distribution: World
Expiry: 27 Nov 2008
Calendar1: 27 Nov 2008 1500-1600
CalLoc1: Eastern Ave 311
Auth: ( ERROR )

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

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