archive/share/trash/determ.usg

   1                 The Bareiss Two-Step Determinant
   2
   3     This is a proposal for a new determinant routine.  This method
   4 is a non-fraction-producing method designed to minimize the complex-
   5 ity of the coefficients in the subexpressions generated.  The space
   6 requirements in list storage space are minimized by overwriting and
   7 avoiding unnecessary storage.  This is an absolutely stable elimina-
   8 tion method.  This method in the general case returns the absolute
   9 smallest possible coefficients.  This algorithm has been developed to
  10 provide for the expansion of a determinant of general commutative ele-
  11 ments (such as elements of an Abelian group).  Note:  for maximum
  12 efficiency the elements of all the rows and columns respectively
  13 should be made relatively prime to each other.
  14
  15     This is a two-step method.  I have chosen a fraction-free rather
  16 than a division-free algorithm to avoid the large expressions gener-
  17 ated by the division-free method.  To preserve fraction-free arith-
  18 metic, the divisions must usually be carried out as the last arithme-
  19 tic operation in determining the lower-order determinants.  However I
  20 have decided to carry out the divisions after calculating the cofact-
  21 ors.  The advantage of this method is that smaller expressions are
  22 generated.  The penalty in efficiency caused by the divisions is rel-
  23 atively small for large systems.
  24
  25     Divisions are performed after calling EZGCD.  If greatest common
  26 divisor calculations are unneccessary, then TAKEGCD should be set to
  27 FALSE.  No other simplifications are performed.
  28
  29     This method has been taken from the paper "Sylvester's Identity
  30 and Multistep Integer-Preserving Gaussian Elimination"  by
  31 Erwin H. Bareiss.
  32
  33     This algorithm has been programmed by Martin Cole.  The function
  34 is called as  det(m)  where m is a matrix or array.  Any comments
  35 or suggestions should be mailed to MSC@MIT-MC.