FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Symbolic
Efficient Determinant Computation over Z/p
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
Robert H. Lewis
science forum beginner


Joined: 22 Jul 2005
Posts: 9

PostPosted: Sat Jul 01, 2006 5:11 pm    Post subject: Efficient Determinant Computation over Z/p Reply with quote
Hi,

Given a fairly large square matrix (say rows = n >= 300) over Z/p what is the best way to compute its determinant?

So, the entries are in the finite field F(p) = Z/p. The matrix may be sparse or dense.

Is there any method better than Gaussian elimination, which is O(n^3), under any reasonable assumptions?

Robert H. Lewis
Fordham University
New York
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Tue Jul 11, 2006 12:52 pm    Post subject: Re: Efficient Determinant Computation over Z/p Reply with quote
Robert H. Lewis wrote:

Quote:
Given a fairly large square matrix (say rows = n >= 300) over Z/p
what is the best way to compute its determinant?

So, the entries are in the finite field F(p) = Z/p. The matrix may
be sparse or dense.

Is there any method better than Gaussian elimination, which is
O(n^3), under any reasonable assumptions?

None that I know of, unless you count assumptions about a
special structure, e.g. Toeplitz matrices or similar, for which
an O(n^2) algorithm is possible.

Sorry!

regards, chip
Back to top
avidad
science forum beginner


Joined: 21 Jul 2005
Posts: 6

PostPosted: Thu Jul 13, 2006 9:09 pm    Post subject: Re: Efficient Determinant Computation over Z/p Reply with quote
Chip Eastham wrote:
Quote:
Robert H. Lewis wrote:


Given a fairly large square matrix (say rows = n >= 300) over Z/p
what is the best way to compute its determinant?

So, the entries are in the finite field F(p) = Z/p. The matrix may
be sparse or dense.

Is there any method better than Gaussian elimination, which is
O(n^3), under any reasonable assumptions?


None that I know of, unless you count assumptions about a
special structure, e.g. Toeplitz matrices or similar, for which
an O(n^2) algorithm is possible.

Sorry!

regards, chip

If the matrix is space (or structured as Toeplitz Hankel or low

deplacement rank) yes, look for a method based on matrix-vector product.
Look the web page of Jean-Guillaume Dumas for efficient determinant
computation over finite field.
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Sun Dec 09, 2018 7:20 pm | All times are GMT
Forum index » Science and Technology » Math » Symbolic
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts sign of the determinant of an augmented matrix? Mark Math 4 Thu Jul 20, 2006 1:30 am
No new posts help with symbolic matrix computation in maple csviks Symbolic 0 Fri Jul 07, 2006 8:58 pm
No new posts A computation José Carlos Santos Math 15 Mon Jun 26, 2006 3:37 pm
No new posts is there an efficient algorithm for switching representat... apc Math 11 Sun Jun 25, 2006 11:31 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.0119s ][ Queries: 16 (0.0020s) ][ GZIP on - Debug on ]