LoÃc Grenià on Thu, 04 Oct 2012 14:41:01 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Kernel mod prime power


     Hello pari users,

     I have a routine that computes often the HNF basis of the kernel
  of a matrix modulo a prime power. More precisely once per iteration
  it computes the kernel of a matrix A modulo a prime p and the kernel
  of a second matrix B modulo a prime power p^k (with k > 1).

   The situation is the following:

  p is small (<= 1500)
  p^k is small (around 10^6 or 10^7)
  A and B are *very small* (right now two columns, maybe more later,
  and most of the time they have only one row, I seriously doubt they
  go over 6 rows, even with following wind).
  A and B are Flm (and B does not necessarily reduce to A mod p,
  even though it does most of the time).

   What I've tried is to take matsolvemod0 (i.e. gaussmoduloall),
  remove the part that finds the solution and keep the kernel part
  (+HNF at the end), wrapped with a Flm_to_ZM+ZM_to_Flm.
  I thought this would be ok but it happens that it takes a lot more
  time than I expected.

    I've now modified my algorithm: I now use Flm_ker when I compute
  modulo p, I do it by hand when B has only one row and use my
  modified matsolvemod0 when B has more than one row. The speed
  is now ok but the code is dirty. I can hide everything inside an
  ad-hoc function, but I'd like something better, if possible.

    Does somebody know how to compute the HNF basis of a kernel
  mod prime power for an Flm in some relatively efficient way ?

        Thanks,

              LoÃc