Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation - Computer Science > Symbolic ComputationReportar como inadecuado




Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation - Computer Science > Symbolic Computation - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Kaltofen has proposed a new approach in 1992 for computing matrixdeterminants without divisions. The algorithm is based on a baby steps-giantsteps construction of Krylov subspaces, and computes the determinant as theconstant term of a characteristic polynomial. For matrices over an abstractring, by the results of Baur and Strassen, the determinant algorithm, actuallya straight-line program, leads to an algorithm with the same complexity forcomputing the adjoint of a matrix. However, the latter adjoint algorithm isobtained by the reverse mode of automatic differentiation, hence somehow is not-explicit-. We present an alternative still closely related algorithm for theadjoint thatcan be implemented directly, we mean without resorting to anautomatic transformation. The algorithm is deduced by applying programdifferentiation techniques -by hand- to Kaltofen-s method, and is completelydecribed. As subproblem, we study the differentiation of programs that computeminimum polynomials of lineraly generated sequences, and we use a lazypolynomial evaluation mechanism for reducing the cost of Strassen-s avoidanceof divisions in our case.



Autor: Gilles Villard LIP

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados