Karim Belabas on Mon, 17 Dec 2012 18:40:57 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: matdet vs. matdetint for large square matrices |
* Max Alekseyev [2012-12-17 17:27]: > Dear pari-users, > > Description of matdetint(x) says that "when x is square, the exact > determinant is obtained". > I noticed that for large binary square matrices (of order several > hundreds), matdetint(x) gives roughly a triple speedup. > > Btw, it turns out that for square matrices, matdetint(x) gives the > value of determinant up to a sign not exact (the description should > have reflected this fact). Agreed: matdetint() returns a non-negative multiple of the determinant, which is exactly |det| for a square matrix. I'll fix the documentation. > In general, I'm interested in a fast way of testing whether matdet(x) > == 0 for an integer matrix x. > In my case among > matdet(x) == 0 > matrank(x) < matsize(x)[1] > matdetint(x) == 0 > the best performance is given by the last variant. > Is there anything better? As Bill mentioned, In the testing branch 2.6.*, ZM_det() computes the determinant using a modular algorithm + Chinese remaindering (+ Dixon's p-adic lifting). It should already be much faster than stable. A trivial modification can be used to very quickly check that det != 0 (when it is indeed non-zero): abort as soon as (det mod p) != 0 for one of the successive primes used. I'm not sure how efficient the function is when det = 0: it's never used in this case ! Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `