1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

The Bareiss TwoStep Determinant
This is a proposal for a new determinant routine. This method
is a nonfractionproducing method designed to minimize the complex
ity of the coefficients in the subexpressions generated. The space
requirements in list storage space are minimized by overwriting and
avoiding unnecessary storage. This is an absolutely stable elimina
tion method. This method in the general case returns the absolute
smallest possible coefficients. This algorithm has been developed to
provide for the expansion of a determinant of general commutative ele
ments (such as elements of an Abelian group). Note: for maximum
efficiency the elements of all the rows and columns respectively
should be made relatively prime to each other.
This is a twostep method. I have chosen a fractionfree rather
than a divisionfree algorithm to avoid the large expressions gener
ated by the divisionfree method. To preserve fractionfree arith
metic, the divisions must usually be carried out as the last arithme
tic operation in determining the lowerorder determinants. However I
have decided to carry out the divisions after calculating the cofact
ors. The advantage of this method is that smaller expressions are
generated. The penalty in efficiency caused by the divisions is rel
atively small for large systems.
Divisions are performed after calling EZGCD. If greatest common
divisor calculations are unneccessary, then TAKEGCD should be set to
FALSE. No other simplifications are performed.
This method has been taken from the paper "Sylvester's Identity
and Multistep IntegerPreserving Gaussian Elimination" by
Erwin H. Bareiss.
This algorithm has been programmed by Martin Cole. The function
is called as det(m) where m is a matrix or array. Any comments
or suggestions should be mailed to MSC@MITMC.
