MathGroup Archive 1992

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

Search the Archive

Re: how to compute determinants

  • To: mathgroup at yoda.physics.unc.edu
  • Subject: Re: how to compute determinants
  • From: David Withoff <withoff>
  • Date: Thu, 23 Apr 1992 09:59:36 -0500

Just a few comments in response to Richard Fateman's response to my response
to the earlier discussion about the Det function in Mathematica....

First, regarding Det:

> 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.
> 
> 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.

The general symbolic Det algorithm doesn't maintain factored forms, and
exploits sparsity by expanding in minors along the row or column with
the most zeros.  I don't know of a reference for cacheing of minors, but
it's a simple optimization that would likely occur to anyone who tried
expanding a large determinant by hand.  Other than that, the code does
simple expansion by minors.

For better or worse, since the general symbolic Det code doesn't use ideas
from specialized research literature, such references don't seem necessary.

I suspect that part of the issue is a general request for additional
documentation of internal algorithms, or at least additional references,
and with that I fully concur.  Although there is already lots of documentation,
including hundreds of references, documentation writers (such as me)
invariably make decisions about what to include and what to leave out.
The answers to several commonly asked questions have apparently been left out.

For now, people who want information not contained in the documentation
can contact Technical Support, and beyond that can contact developers
directly.  The Technical Support Department continuously answers questions
about internal algorithms, and I have communicated myself with hundreds
of people (including Prof. Fateman) about internals of the program. When
an algorithm is described in available literature, the answer to a question
about the algorithm will often include a reference.

Still, the fact that there are so many requests for such information is itself
an indication of a need for improvement.  Additional documentation will almost
certainly become available as the product matures, and everyone will benefit.
Users will have better information, and the Technical Support Department
(and people like me) will be free to deal with other tasks.

While I agree that additional references and documentation are needed, the
general symbolic Det algorithm probably isn't the best example of the problem.
Since the algorithm used is quite elementary, I don't agree that giving an
elementary linear algebra book as a reference serves to "promulgate the myth
that Mathematica's symbolic algorithms bear no relation to any other symbolic
system of the past", and I'm not sure what to make of the intriguing
anthropomorphization contained in the statement that "the Mathematica book
refuses to provide references to algorithms".

If there are references that have been overlooked, let me know and I'll do
what I can to see that they are included in future documentation.  In the
meantime, you can continue to send questions about internal algorithms to
Technical Support, or to developers.

Dave Withoff
withoff at wri.com





  • Prev by Date: determinants
  • Next by Date: Signal Processing ftp server update
  • Previous by thread: how to compute determinants
  • Next by thread: Limits to Det Function