|
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 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 |
|
 |
|
The time now is Tue Feb 19, 2019 6:34 am | All times are GMT
|
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
|
|