Author 
Message 
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 


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 


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 


Google


Back to top 



The time now is Tue Mar 19, 2019 10:20 am  All times are GMT

