Re: computing rank of big dense matrices over number fields

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Apr 07, 2020 at 06:37:16PM +0200, Karim Belabas wrote:
> * 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

Maybe we should hack matker so that Mod(xxx,polcyclo()) is recognized
and ZabM_ker is called automaticaly.

Cheers,
Bill.