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

```

• Prev by Date: E^A , A is a matrix, summary
• Next by Date: Limits to Det Function
• Previous by thread: E^A , A is a matrix, summary
• Next by thread: Re: how to compute determinants