[plt-scheme] Matrix Determinants

Geoffrey S. Knauth : 

> Not sure if this helps:  Aubrey Jaffer's SLIB has determinant in  
> determ.scm. 
> 
> On Mar 28, 2008, at 01:39, Henk Boom wrote: 
> 
>> On 28/03/2008, John Clements <clements at brinckerhoff.org> wrote:
>>> Wikipedia suggests gaussian elimination...
>> 
>> Yup, that's more or less the algorithm I'm using, except that I
>> discard the first row and column of the matrix when they are no longer
>> needed. ...

If I am not mistaken, the SLIB matrix package uses the Laplace expansion
for the determinant. So, ~ n!. (At least, the version I saw used that,
looping over the first line and recurring through cofactor & determinant. 

Apparently the orig. poster doesn't want this. Now, the question is: why
not? Do you really want to compute determinants for n>, say 6 or 7? 

Another issue is the precision. The standard Gauss elimination uses - of
course - the division. But John Clements said that his matrices use
exact numbers. So, either the precision is lost if a conversion into
inexact sneaks in, or it is necessary to perform the rational arith.,
which is not extremely efficient, knowing that the determinant is anyway
a polynomial operation. 

I am hair-splitting now, since most of you are not interested in numerical
stuff, but if somebody wants a *serious* approach to exact det computation,
he should look at the Bareiss algorithm, or similar. Look here. 

http://page.inf.fu-berlin.de/~rote/Papers/pdf/Division-free+algorithms.pdf 


Jerzy Karczmarczuk