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]
`