[Date Index] [Thread Index] [Author Index]

how to compute determinants

• To: mathgroup at yoda.physics.unc.edu
• Subject: how to compute determinants
• From: fateman at peoplesparc.berkeley.edu (Richard Fateman)
• Date: Wed, 22 Apr 92 10:54:21 PDT

Elementary linear algebra books generally ignore computation
time analysis. Those that DO talk about times would say that Gaussian
elimination is far superior to expansion by minors. This is quite true
of matrices with numeric entries, but FALSE for smallish matrices
of symbols.  

It is clear that Dave Withoff knows this because he says that "Other
algorithms are used for matrices of reals, integers, rationals, etc."
(by Mathematica).

I think that people seriously interested in this problem should
look further than Withoff said, as well.  The strategy for expansion
by minors is non-obvious, and even within the context of your
note, questions remain about  maintaining factored form and
sparsity.

For an eye-opener, see the paper by W. M. Gentleman and S.C. Johnson,
"The evaluation of determinants by expansion by minors and the general
problem of substitution," in Mathematics of Computation, vol 28 number
126 April 1974, 543-548.
 
There are lots of more recent articles on the topic, but this one
explains why expansion by minors might be a good tactic.

I repeat:
> Since the Mathematica book 
> refuses to provide references to algorithms, people who want to know
> more will have to look elsewhere.  

Although I think Withoff's note provides useful information,
"Almost any elementary linear algebra book" seems to me to be
an inappropriate reference for a computer algebra system determinant
algorithm. 

Perhaps unintentionally, such references promulgate the myth that
Mathematica's symbolic algorithms bear no relation to any other
symbolic system of the past.  Gentleman and Johnson worked on ALTRAN.
It didn't keep the people who wrote the Macsyma manual from referring
to the paper explicitly.

And for Maple, the on-line documentation for determinant 
starts out...

FUNCTION: linalg[det] - determinant of a matrix
   
CALLING SEQUENCE:
   det(A)   
   det(A, sparse)
   
PARAMETERS:
   A      - a two-dimensional square matrix
   sparse - optional directive
   
SYNOPSIS:   
- The function det computes the determinant of the given matrix.
   
- The second argument (optional) specifies that the computational method of
  minor expansion should be used.  This works well for sparse matrices.
   
- With no extra argument, a decision is made automatically whether to use minor
  expansion or Gaussian elimination (or a combination of both).  Specifying the
  extra argument eliminates the overhead of the decision process if you happen
  to know ahead of time that minor expansion will work best.

.....etc. 

 (also note you can look at the code to see how the determination of
the method is done).




 RJF