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.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2011, 46 (7), pp.773-790. 〈10.1016/j.jsc.2010.08.012〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00270753
Contributeur : Gilles Villard <>
Soumis le : lundi 7 avril 2008 - 14:12:56
Dernière modification le : mardi 24 avril 2018 - 13:55:27
Document(s) archivé(s) le : jeudi 20 mai 2010 - 23:01:23

Fichiers

diff.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

89