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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00270753
Contributor : Gilles Villard <>
Submitted on : Monday, April 7, 2008 - 2:12:56 PM
Last modification on : Tuesday, April 24, 2018 - 1:55:27 PM
Long-term archiving on : Thursday, May 20, 2010 - 11:01:23 PM

Files

diff.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

248

Files downloads

101