Günter Rote:

Division-free algorithms for determinants and Pfaffians: algebraic and combinatorial approaches

In: "Computational Discrete Mathematics" (preliminary version). Editor: Helmut Alt. July 2000; pp. 59-75.
Final version to appear in Lecture Notes in Computer Science, Springer-Verlag.


The most common algorithm for computing the determinant of an nxn-matrix is Gaussian elimination and needs O(n3) arithmetic operations. On the other hand, the explicit definition of the determinant as the sum of n! products shows that the determinant can be computed without divisions. In this introductory survey, we will describe an O(n4) algorithm that works without divisions and goes back to Faddeyev and Faddeyeva. We will look at this algorithm from a combinatorial and an algebraic viewpoint. We will also consider the Pfaffian of a skew-symmetric matrix, a quantity closely related to the determinant. The results are in many ways analogous to those for the determinant, but the algebraic aspect of the algorithms is not explored yet.

  PostScript file (gzippedpdf file   TeX .dvi file (gzipped)
other papers about this subject