> < ^ From:

< ^ Subject:

Dear GAP-Forum,

On Thu, 23 Aug 2001, Derek Holt wrote:

There is a polynomial time fraction-free method of computing determinants

due to Bareiss that works in an arbitrary integral domain. It is described

in Sections 9.2, 9.3 of "Algorithms for Computer Algebra" by Geddes,

Czapor and Labahn. I don't have any direct knowledge or experience of it

myself though!

I think the current generic algorithm in GAP is close to the one given in

the citation. These algorithms are *fraction-free* in the sense that

whenever a division of elements in an integral domain occurs it is

guaranteed that the quotient exists in this ring.

But the formula with the Laplace expansion is even *division free* and works

over any commutative ring.

I have found a reference for a better *division free* algorithm which needs

~n^4 ring operations for an nxn-matrix, see for example:

http://scholar.lib.vt.edu/ejournals/CJTCS/cjtcs-mirror/articles/1997/5/cj97-05.pdf

Is there anybody who wants to have a look at this and maybe implement this

for GAP's library? (If yes, tell me or gap-trouble@dcs.st-and.ac.uk)

Best regards,

Frank Lübeck

PS.: We currently have a similar request for a good "discrete logarithm"

algorithm: Given a generator a of a cyclic group and an element x in <a>,

find n such that x = a^n. Does anyone have implemented algorithms for this

(Pollard Rho Method, elliptic curve method for x mod p, ...) or wants to

have a look at it?

/// Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64, /// \\\ 52062 Aachen, Germany \\\ /// E-mail: Frank.Luebeck@Math.RWTH-Aachen.De /// \\\ WWW: http://www.math.rwth-aachen.de/~Frank.Luebeck/ \\\

Miles-Receive-Header: reply

> < [top]