On Wed, Jun 14, 2023 at 8:15 PM David Roe <roed.m...@gmail.com> wrote:
>
> Another possibility would be to change the __pow__ method for integer
> matrices to not ignore the modulus argument. As a workaround you can either
> use pari (as you discovered), or use an integer matrix and occasionally
> reduce the coefficients.
I implemented something very close to efficiently reduction modulo integers
when working over ZZ and probably it can implemented in __pow__().
check the attached file.
sage: time M1f=matpowermodp(M,n,p)
CPU times: user 528 ms, sys: 2.98 ms, total: 531 ms
Wall time: 362 ms
sage: time M1s=M1p**n
CPU times: user 21.3 s, sys: 4.01 ms, total: 21.3 s
Wall time: 21.4 s
sage: M1s==M1f
True
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/CAGUWgD8FPZQPJ_THJnzhiS80%3D%2BjwGZYC-%2BFoG5eXNuQQc1JNQw%40mail.gmail.com.
def matpowermodp(M,n,p):
"""
Author Georgi Guninski
in the public domain
M**n mod p
M: matrix over the integers
p=next_prime(2**100)
n=200;l=list(range(n**2))
M=Matrix(ZZ,n,n,l)
M1p=Matrix(Integers(p),n,n,l)
M1f=matpowermodp(M,n,p)
M1s=M1p**n
M1s==M1f
sage: time M1f=matpowermodp(M,n,p)
CPU times: user 528 ms, sys: 2.98 ms, total: 531 ms
Wall time: 362 ms
sage: time M1s=M1p**n
CPU times: user 21.3 s, sys: 4.01 ms, total: 21.3 s
Wall time: 21.4 s
sage: M1s==M1f
True
"""
assert n>0,"n>0"
R=M
n=n-1
x=M
N=M.nrows()
while n:
if n%2==1: R *= x
x=x**2
n=n//2
for i in range(N):
for j in range(N):
R[i,j]=R[i,j]%p
x[i,j]=x[i,j]%p
return R
