Günter Rote:

Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches

In: "Computational Discrete Mathematics." Editor: Helmut Alt. Lecture Notes in Computer Science 2122, Springer-Verlag, 2001, pp. 119–135. doi:10.1007/3-540-45506-X_9


The most common algorithm for computing the determinant of an n×n-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 (gzipped)
TeX .dvi file (gzipped)
other papers about this subject
Last update: May 22, 2001.