| 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