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

[Georgi Guninski]

> I suggest that you separate the time taken for the change_ring() operation

Thanks. You are right, the .change_ring() was written in a hurry.
If the sage overlords want more systematic QA, they will need moderate budget.
I need to compute large m-th powers of matrices for m > 100 and if I
work over ZZ, the integer entries are very large, slowing the wall
time computation.
pari/gp has decent performance for matrix multiplication over finite fields.

[Nils Bruin]

On Monday, 30 March 2026 at 09:00:32 UTC-7 Georgi Guninski wrote:

> I suggest that you separate the time taken for the change_ring() operation

Thanks. You are right, the .change_ring() was written in a hurry.
If the sage overlords want more systematic QA, they will need moderate budget.
I need to compute large m-th powers of matrices for m > 100 and if I
work over ZZ, the integer entries are very large, slowing the wall
time computation.

For such high powers you may well be better off first computing the Jordan Normal Form of the matrix. Then you only need to take extremely high powers of diagonal matrices, which is *way* faster. It can easily be worth the cost of the base field extension.