We study complexity estimates for computing n×n matrix determinants and adjoints over an abstract ring R. Using a block Krylov approach, together with Strassen's avoidance of divisions, Kaltofen (1992) and Kaltofen & Villard (2004) propose an algorithm for computing the determinant in O(n^2.7) additions, subtractions, and multiplications. This is currently the best known complexity estimate for the problem. We will give an insight into the method, especially into its baby steps/giant steps strategy.

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. However, the latter adjoint algorithm is obtained by the reverse mode of automatic differentiation, hence somehow is not "explicit". We present an alternative (still closely related) algorithm for the adjoint that can be implemented directly, by which we mean without resort to an automatic transformation. The algorithm is deduced by applying program differentiation techniques "by hand" to the determinant program, and is completely described.