Skip to Main content Skip to Navigation
Journal articles

Differentiation of Kaltofen's division-free determinant algorithm

Abstract : 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Monday, April 7, 2008 - 2:12:56 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Thursday, May 20, 2010 - 11:01:23 PM


Files produced by the author(s)




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



Record views


Files downloads