Differentiation of Kaltofen's division-free determinant algorithm

Gilles Villard (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Kaltofen has proposed a new approach in [Kaltofen 1992] for computing matrix determinants. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determinant as the constant term of a characteristic polynomial. For matrices over an abstract field and 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 [Kaltofen 1992]. However, the latter is obtained by the reverse mode of automatic differentiation and somehow is not ``explicit''. We study this adjoint algorithm, show how it can be implemented (without resorting to an automatic transformation), and demonstrate its use on polynomial matrices.

Keywords: matrix adjoint algorithm; matrix determinant algorithm; automatic differentiation; exact algorithm

Domains: Symbolic Computation [cs.SC]; Mathematical Software [cs.MS]

Gilles Villard. Differentiation of Kaltofen's division-free determinant algorithm. Journal of Symbolic Computation, 2011, 46 (7), pp.773-790. ⟨10.1016/j.jsc.2010.08.012⟩. ⟨ensl-00270753⟩