Author 
Message 
Robert H. Lewis science forum beginner
Joined: 22 Jul 2005
Posts: 9

Posted: Sat Jul 01, 2006 5:11 pm Post subject:
Efficient Determinant Computation over Z/p



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

Posted: Tue Jul 11, 2006 12:52 pm Post subject:
Re: Efficient Determinant Computation over Z/p



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

Posted: Thu Jul 13, 2006 9:09 pm Post subject:
Re: Efficient Determinant Computation over Z/p



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 matrixvector product.
Look the web page of JeanGuillaume Dumas for efficient determinant
computation over finite field. 

Back to top 


Google


Back to top 



The time now is Tue Oct 17, 2017 2:50 pm  All times are GMT

