An introspective algorithm for the integer determinant

Details An introspective algorithm for the integer determinant An introspective algorithm for the integer determinant

2005-11-17

arxiv.org/abs/cs/0511066v5

Computer Science

Symbolic Computation

Published in Transgressive Computing 2006, Grenade : Espagne (2006)

Scientific paper

We present an algorithm computing the determinant of an integer matrix A. The algorithm is introspective in the sense that it uses several distinct algorithms that run in a concurrent manner. During the course of the algorithm partial results coming from distinct methods can be combined. Then, depending on the current running time of each method, the algorithm can emphasize a particular variant. With the use of very fast modular routines for linear algebra, our implementation is an order of magnitude faster than other existing implementations. Moreover, we prove that the expected complexity of our algorithm is only O(n^3 log^{2.5}(n ||A||)) bit operations in the dense case and O(Omega n^{1.5} log^2(n ||A||) + n^{2.5}log^3(n||A||)) in the sparse case, where ||A|| is the largest entry in absolute value of the matrix and Omega is the cost of matrix-vector multiplication in the case of a sparse matrix.

Affiliated with

Also associated with

No associations

Rating

An introspective algorithm for the integer determinant does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An introspective algorithm for the integer determinant, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An introspective algorithm for the integer determinant will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-587952