| Karim Belabas on Tue, 07 Apr 2020 18:37:21 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: computing rank of big dense matrices over number fields |
* Vincent Delecroix [2020-04-07 18:16]:
> Dear pari team,
>
> I have dense matrices defined over number fields. The target size
> (rows and columns) and number field degree are around 30. In other
> words, as a matrix over the rationals it looks like a 1000 x 1000
> dense matrix. I would like to compute its rank. Very quickly
> matrank seems stuck whereas it reasonably works for 1000 x 1000
> rational matrices. Is there any alternative approach that
> could be used?
Pick a few maximal ideals, map to the residue field and compute the rank
there. The rank is bounded from below by the maximal residual rank
and almost certainly equal to it (and you get a provably invertible
square submatrix of that rank).
If you need a guaranteed result you must then prove that the extra rows
or columns are linear combinations of the submatrix and there's no fast
algorithm implemented in PARI for this: you can (install and) use nfM_det
but it is slow.
If your fields are cyclotomic, (install and) use ZabM_indexrank
Cheers,
K.B.
--
Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP]
`