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
Abstract
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.
Last update: May 22, 2001.