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