Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-15 Thread Dima Pasechnik 
Flint also has dense matrices over rings in general, so one can use any
Flint ring, not only Z mod n.



On Thu, 15 Jun 2023, 14:07 Edgar Costa,  wrote:

> Indeed, that is what we should use for single-word modulus.
> I think David and I wrote a wrapper at some point, but then we did not use
> it?
>
> On Thu, Jun 15, 2023 at 8:26 AM Dima Pasechnik  wrote:
>
>> Flint has matrices mod n, see  https://flintlib.org/doc/nmod_mat.html
>> I guess they should be fast - but they need Sage interface to be provided.
>>
>> On Thu, Jun 15, 2023 at 1:01 PM Georgi Guninski 
>> wrote:
>> >
>> > On Wed, Jun 14, 2023 at 8:15 PM David Roe  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
>> .
>>
>> --
>> 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/CAAWYfq3-w6FFNeDpvgD84wJSHMnx9gvPoAP%3Dwf%2BhbxBYu3RzMQ%40mail.gmail.com
>> .
>>
> --
> 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/CA%2BiQ7x6PN9%2B2CqXN5mjcCNu2i9rdwXAM%3D2pYs09dPsOCjx4_ag%40mail.gmail.com
> 
> .
>

-- 
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/CAAWYfq0c0GvqhLfMZ-z%3DUFPoxT3c11LmN8zJqqt672S1fL2hVw%40mail.gmail.com.

Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-15 Thread Edgar Costa 
Indeed, that is what we should use for single-word modulus.
I think David and I wrote a wrapper at some point, but then we did not use
it?

On Thu, Jun 15, 2023 at 8:26 AM Dima Pasechnik  wrote:

> Flint has matrices mod n, see  https://flintlib.org/doc/nmod_mat.html
> I guess they should be fast - but they need Sage interface to be provided.
>
> On Thu, Jun 15, 2023 at 1:01 PM Georgi Guninski 
> wrote:
> >
> > On Wed, Jun 14, 2023 at 8:15 PM David Roe  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
> .
>
> --
> 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/CAAWYfq3-w6FFNeDpvgD84wJSHMnx9gvPoAP%3Dwf%2BhbxBYu3RzMQ%40mail.gmail.com
> .
>

-- 
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/CA%2BiQ7x6PN9%2B2CqXN5mjcCNu2i9rdwXAM%3D2pYs09dPsOCjx4_ag%40mail.gmail.com.

Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-15 Thread Dima Pasechnik 
Flint has matrices mod n, see  https://flintlib.org/doc/nmod_mat.html
I guess they should be fast - but they need Sage interface to be provided.

On Thu, Jun 15, 2023 at 1:01 PM Georgi Guninski  wrote:
>
> On Wed, Jun 14, 2023 at 8:15 PM David Roe  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.

-- 
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/CAAWYfq3-w6FFNeDpvgD84wJSHMnx9gvPoAP%3Dwf%2BhbxBYu3RzMQ%40mail.gmail.com.

Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-15 Thread Georgi Guninski 
On Wed, Jun 14, 2023 at 8:15 PM David Roe  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

Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-14 Thread William Stein 
On Wed, Jun 14, 2023 at 10:15 AM David Roe  wrote:
>
> The problem is that Sage doesn't have a specialized type for integers mod N:
> sage: type(M3)
> 


More precisely, Sage doesn't have a specialized type for matrices over
integers mod N, for N *large*.  For smaller N it does, e.g.,

sage: p=next_prime(2**22)
sage: M3=Matrix(GF(p),n,na,l)
sage: type(M3)

sage: time a=M3**n
CPU times: user 96.5 ms, sys: 0 ns, total: 96.5 ms Wall time: 112 ms

It's obviously very important to be aware of the range of the rings
where matrices are extremely fast, if you're implementing a
multi-modular algorithm. I don't know what your application is though.

-- 
William (http://wstein.org)

-- 
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/CACLE5GDP9kta1P7%3Db9vhPCC33vcFE34ns%2B5SjkUFapDZyj4u0w%40mail.gmail.com.

Re: [sage-devel] Re: Why matrix powers are slower over Integers(p) than in ZZ?

2023-06-14 Thread David Roe 
The problem is that Sage doesn't have a specialized type for integers mod N:
sage: type(M3)


The best solution would be to create one, but of course that's a lot of
work.  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.
David

On Wed, Jun 14, 2023 at 9:18 AM Georgi Guninski  wrote:

> pari/gp appears significantly faster:
>
> sage: time M31=M3**n
> CPU times: user 11.2 s, sys: 8.11 ms, total: 11.2 s
> Wall time: 11.3 s
> sage: M3g=gp(M3)
> sage: time M32=M3g**n
> CPU times: user 617 µs, sys: 2.79 ms, total: 3.41 ms
> Wall time: 119 ms
> sage: M32==gp(M31)
> 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/CAGUWgD829%2BHC5D-YpvdR6hab7gHAfc9cGQTN%2BGft-DsW8T526A%40mail.gmail.com
> .
>

-- 
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/CAChs6_mMXR%3D_TxZnTYLBFpM2v1d8K74qJZvV78iiTZ0vOyNisQ%40mail.gmail.com.