##
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.*
###
Abstract

The most common algorithm for computing the determinant of an *n*x*n*-matrix
is Gaussian elimination and needs
*O*(*n*^{3}) 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*(*n*^{4})
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.