Polynomials/matrices/vectors mod n, random generation: add uniform random?

[vneiger]

Currently, most objects (polynomials, vectors, matrices, ...) composed of nmod or fmpz_mod coefficients offer some functions for filling coefficients with random entries that have a special property (typically calling n_randtest, with the probability of special values or sparsity increased, see https://flintlib.org/doc/ulong_extras.html#c.n_randtest ).

Would there be any objections against adding functions for filling objects in a dense way and with uniformly random coefficients? I often such "uniformly random generation" e.g. for benchmarks or in the writing of randomized algorithms, and was wondering whether its absence from FLINT is deliberate.

[albinahlback]

No, I don't think it is deliberate. You can use n_randint for the backend, which generates a uniformly random integer in the given range.

[fredrik-johansson]

Highly desired!

[vneiger]

Thanks for the feedback, will work on it then.

[dlesnoff]

I am working on the fmpz_mod_mat case:
the randtest actually generates a uniform dense matrix and should be called randfull. An actual randtest should be added, and implementations should switch names.

[dlesnoff]

Is there a reason why nmod_mat_randfull never generates a zero ?
nmod_mat_entry(mat, i, j) = FLINT_MAX(1, n_randint(state, mat->mod.n));

[vneiger]

Is there a reason why nmod_mat_randfull never generates a zero ? nmod_mat_entry(mat, i, j) = FLINT_MAX(1, n_randint(state, mat->mod.n));

The doc is saying that this is supposed to insert entries "close to the modulus" notably for overflow issues detection, so I suppose it is ok to have them nonzero (?).

[vneiger]

I am working on the fmpz_mod_mat case: the randtest actually generates a uniform dense matrix and should be called randfull. An actual randtest should be added, and implementations should switch names.

I don't think it is uniform, there is some fmpz_randtest running in. But indeed I don't see some sparsity being introduced (unlike in nmod_mat_randtest).

[fredrik-johansson]

Yes, randfull is not the same as uniformly random. It's specifically designed to detect overflow cases.

[dlesnoff]

Places where a rand (and not randtest) has been implemented so far:

• nmod (base type, I guess that would be a unuseful wrapper around n_randint)
• nmod_vec
• nmod_mat
• nmod_poly
• nmod_poly_mat
• nmod_mpoly
• mpn_mod
• fmpz_mod (base type, unuseful?)
• fmpz_mod_mat
• fmpz_mod_poly
• fmpz_mod_mpoly
• fmpz_mod_mpoly_q

fmpz_mod_poly uses randm as backend, which is the equivalent of n_randint for fmpz_t. It does generate uniform coefficients in a dense manner.
Should I add a rand function and change randtest to generate sparse polynomials for fmpz_mod_poly as well? Is there a need for a randfull (non-zero coefficients generated in an almost uniform manner) in all the above modules?

EDIT: random functions are sometimes spread in multiple source files, sometimes gathered in a single randtest.c. Should I put them all in a rand.c file or let them as they are ?

[fredrik-johansson]

Should I add a rand function and change randtest to generate sparse polynomials for fmpz_mod_poly as well?

That would make sense.

Is there a need for a randfull (non-zero coefficients generated in an almost uniform manner) in all the above modules?

I don't think so. This is only really needed to test some specific algorithms.

Besides, I think randfull could be superseded by mat_randtest and vec_randtest functions that occasionally generate vectors of nearly full entries.