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