 Forum index » Science and Technology » Math » Symbolic
Author Message
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. 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 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  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 19, 2019 10:20 am | All times are GMT Forum index » Science and Technology » Math » Symbolic
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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