Matrix squaring and multiplication significantly faster over ZZ versus GF(p)

[Georgi Guninski]

I believed that matrix multiplication and squaring to be significantly
faster over GF(p) instead over ZZ.

Numerical evidence supports the opposite, is it a bug or reality?

Session:

def randmat(N,K): return Matrix(K,N,N,[K.random_element() for _ in range(N^2)])
N=200
Kq=GF(next_prime(2^200))
M1=randmat(N,Kq)
%time MsZZ=M1.change_ring(ZZ)^2 #Wall time: 188 ms
%time Msqu=M1^2 #Wall time: 7.75 s

[Fredrik Johansson]

I would expect matrix multiplication to be around as fast over GF(p) and ZZ if the entries are the same. Large-p GF(p) matrices being a lot slower in Sage is surely because they use a generic matrix implementation rather than a specialized one.

With current FLINT on my machine squaring a 200x200 matrix with 200-bit entries costs as follows:

0.032 seconds over ZZ with fmpz_mat

0.035 seconds over GF(p) with fmpz_mod_mat

0.029 seconds over GF(p) with mpn_mod_mat

Fredrik

 

[Georgi Guninski]

On Sat, Mar 28, 2026 at 4:02 PM Fredrik Johansson
<fredrik....@gmail.com> wrote:
>
> I would expect matrix multiplication to be around as fast over GF(p) and ZZ if the entries are the same. Large-p GF(p) matrices being a lot slower in Sage is surely because they use a generic matrix implementation rather than a specialized one.
>
> With current FLINT on my machine squaring a 200x200 matrix with 200-bit entries costs as follows:
>
> 0.032 seconds over ZZ with fmpz_mat
> 0.035 seconds over GF(p) with fmpz_mod_mat
> 0.029 seconds over GF(p) with mpn_mod_mat
>

Thanks. What code are you doing for benchmarking?

Both on my boxen and sagecell the obvious implementation is slower.

What do you get for the following code?

Session on sagecell:

def randmat(N,K): return Matrix(K,N,N,[K.random_element() for _ in range(N^2)])
N=200

set_random_seed(1)
Kq=GF(next_prime(2^200))
M1=randmat(N,Kq)
%time MsZZ=M1.change_ring(ZZ)^2 #Wall time: 145 ms
%time Msqu=M1^2 #Wall time: 10.6 s

[Vincent Delecroix]

I confirm Fredrik diagnostic

sage: type(M1)
<class 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>

It is a pity that flint fmpz_mod_mat and mpn_mod_mat are not
interfaced (and used) in Sagemath!

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/5bd108cd-ca0c-4b45-8193-dc1f51b010e2n%40googlegroups.com.

[Trevor Karn]

What is the general procedure for implementing an interface with flint?

[Dima Pasechnik]

On March 29, 2026 8:37:54 AM CDT, 'Trevor Karn' via sage-devel <sage-...@googlegroups.com> wrote:
>What is the general procedure for implementing an interface with flint?

Basically, adding more cython code.

But perhaps Sage can switch to using
<https://github.com/flintlib/python-flint/>?

[Trevor Karn]

What is the advantage of using this python/flint?

[Dima Pasechnik]

On March 29, 2026 9:52:30 AM CDT, 'Trevor Karn' via sage-devel <sage-...@googlegroups.com> wrote:
>What is the advantage of using this python/flint?

Less code to support?

[Georgi Guninski]

Is the main problem C is significantly faster than python code?
(I doubt the reason is multiplication with complexity O(n^2.6...))

[Vincent Delecroix]

Hi Trevor, Dima,

Interfacing python-flint as we do with cypari2 (over PARI/GP) might be
interesting. It would indeed allow anyone to make a computation
directly in flint via a conversion "sage object" -> "python-flint
object". But it would not solve the problem that the default finite
field sage matrix in the OP has slow multiplication. For that purpose,
it is necessary to have a sage matrix object with a flint backend.
Whether this backend uses flint or python-flint seems secondary to me.

@Trevor: if you want examples, you could have a look at integer or
rational matrices which are wrappers over the flint types fmpz_mat or
fmpq_mat.

On Mon, 30 Mar 2026 at 11:34, Georgi Guninski <ggun...@gmail.com> wrote:
>
> Is the main problem C is significantly faster than python code?
> (I doubt the reason is multiplication with complexity O(n^2.6...))
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8jAz7r5OgLsvcv_ge0AjKyTCBQ3C_nHweY1RcETNxQCQ%40mail.gmail.com.

[John Cremona]

Returning to the original question,  I suggest that you separate the time taken for the change_ring() operation, which in my experience can take a long time, from the actual computation over ZZ.

John