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