Division-free algorithms for determinants and Pfaffians: algebraic and
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.