ZLS kernel, m=1, zero shift or NULL

[gilvillard]

Using nmod_poly_mat_kernel, for the left kernel of a m x 1 matrix (or very small n)

With NULL input shift, the default shift (nmod_poly_mat_row_degree) that is chosen may prove ineffective compared to a zero shift, especially when row degrees are unbalanced. With maximum degree 320 for example, and m=100, a time ratio of nearly 20 can be observed.

This suggests that the default shift may be worth considering, at least in some cases.

[vneiger]

Thanks for reporting. Indeed I get 3.6seconds for your suggested parameters (picking a 60 bit prime modulus).

For a column vector (n = 1) with a gentle shift (e.g. uniform), the kernel should not be more expensive than a single call to approximant bases at order equal to twice the degree of the vector. Investigating this made me realize that the issue might be in the approximant bases: calling mbasis or pmbasis on such an example (100 x 1 vector with degree 319), I get about 0.1sec for approximation order 320, and 3.6sec for order 640. We definitely should not have such a 36x factor when doubling the order... to be fixed.

[vneiger]

Just to be more precise (and confirm the issue): 0.1sec for degree 319 and order 320 ; 3.6sec for degree 319 and order 640 ; but 0.3sec for degree 639 and order 640.

[vneiger]

After some more investigation, my above remarks led to a clear point to improve (cf #36), but are not directly relevant here since on input a vector of degree 319, kernel_zls will use an approximation order a tiny bit above that bound (say, 330). What happens is still the same phenomenon: for an input vector with unbalanced row degrees, when using a shift which follows these row degrees, this will lead to approximant bases of quite larger and more unbalanced degrees, and this is currently not well handled by mbasis/pmbasis.

In fact, more generally, mbasis/pmbasis is not as fast as it should for cases with one or a few vectors; it should rely more directly on fast Gaussian elimination, and at least somehow handle degree unbalancedness. I'll open an issue about this.