Can someone help understand this error ? (that is generated for large inputs)

[Phoenix]

So I have this SAGE code which takes in two integers q and n and it generates ~ (q^3)^(n^2) 0/1 matrices and does a sum of their characteristic polynomials. 

I got answers for (q = 3, n = 2), (q =2 , n = 3) and (q=2, n=2)

For any higher number the code runs for ~1hr and then it says,

"

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_2.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UA=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpPiPIoq/___code___.py", line 2, in <module>
    exec compile(u'P
  File "", line 1, in <module>

"


Can someone help understand what is going on? 

Like any suggestion about how to go about it? 



EDIT:

This is basically the main time-consuming step. 

At this point "rep" comes in as a ~q^3 size list of q^2 dimensional 0/1 permutation matrices. 
And "Edge" is a list of integer tuples where each tuple is of the form (a,b) with a,b being from the set {0,1,2,3...,(2n-1)} 

P = 0 
from itertools import product
from itertools import izip

for X in product(rep,repeat = len (Edge)):
    k = izip(Edge,X)
    M = [[matrix(q^2, q^2, 0)]*(2*n) for _ in range(2*n)]
    for ((a,b),Y) in k:
      M [a][b] = Y
      M [b][a] = Y.inverse()
    Z = block_matrix(M)
    P = P + Z.charpoly(x)

The polynomial P is the final expected answer. 

(and for any larger value of q and n than the 3 cases mentioned the program basically stops with no output for P and with the above pasted message) 

[David Joyner]

Please include rep and Edge, if if it's in a simple case.

> The polynomial P is the final expected answer.
>
> (and for any larger value of q and n than the 3 cases mentioned the program
> basically stops with no output for P and with the above pasted message)
>

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Phoenix]

I am not sure how to include "rep".
Its a list generated by a set of operations somewhere else.
I am generating "Edge" by extracting the edges of the graph K_{n,n}

[David Joyner]

On Wed, May 13, 2015 at 9:43 PM, Phoenix <anirbit....@gmail.com> wrote:
>
> I am not sure how to include "rep".

Can you type in a short example of what it could be?

> Its a list generated by a set of operations somewhere else.
> I am generating "Edge" by extracting the edges of the graph K_{n,n}
>

Can you type in a short example of what it could be?

[Phoenix]

For the q=2 , n =2 (the smallest test case) we have,

Edge = [(0, 2), (0, 3), (1, 2), (1, 3)]

rep = 

[
[1 0 0 0]  [1 0 0 0]  [1 0 0 0]  [1 0 0 0]  [1 0 0 0]  [1 0 0 0]
[0 0 1 0]  [0 0 1 0]  [0 1 0 0]  [0 1 0 0]  [0 0 0 1]  [0 0 0 1]
[0 1 0 0]  [0 0 0 1]  [0 0 1 0]  [0 0 0 1]  [0 0 1 0]  [0 1 0 0]
[0 0 0 1], [0 1 0 0], [0 0 0 1], [0 0 1 0], [0 1 0 0], [0 0 1 0]
]

[David Joyner]

On Wed, May 13, 2015 at 9:54 PM, Phoenix <anirbit....@gmail.com> wrote:
>
>
> For the q=2 , n =2 (the smallest test case) we have,
>
> Edge = [(0, 2), (0, 3), (1, 2), (1, 3)]
>
> rep =
>
> [
> [1 0 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0] [1 0 0 0]
> [0 0 1 0] [0 0 1 0] [0 1 0 0] [0 1 0 0] [0 0 0 1] [0 0 0 1]
> [0 1 0 0] [0 0 0 1] [0 0 1 0] [0 0 0 1] [0 0 1 0] [0 1 0 0]
> [0 0 0 1], [0 1 0 0], [0 0 0 1], [0 0 1 0], [0 1 0 0], [0 0 1 0]
> ]
>
>

This cannot be copy+pasted into Sage.
Please type it in so that someone who wants to help you can copy+paste.

[Phoenix]

This is really weird that SAGE output that I copy pasted here can't be copy-pasted back into SAGE as an input!

So here it is again written differently!

rep = [ matrix ([[1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1, 0]] ), matrix ([[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0]] ) ,  matrix ([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]] ) , matrix ( [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]] ) ,  matrix ( [[1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0, 0]]) , matrix ([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]] )  ]

Edge = [(0, 2), (0, 3), (1, 2), (1, 3)]

BTW, just curious : isn't there a way by which you could have just randomly generated a set of q^3 permutation matrices each of dimension q^2 instead of looking for a specific example? Can't SAGE randomly generate one such set? 

[Nils Bruin]

On Wednesday, May 13, 2015 at 8:06:16 PM UTC-7, Phoenix wrote:

BTW, just curious : isn't there a way by which you could have just randomly generated a set of q^3 permutation matrices each of dimension q^2 instead of looking for a specific example? Can't SAGE randomly generate one such set?

That's really straightforward:

sage: q=4
sage: G=SymmetricGroup(q^2)
sage: L=[G.random_element().matrix() for i in [1..q^3]]

The distribution with which the elements are selected from G is whatever Gap uses. I'd assume it's the uniform distribution.

[Dima Pasechnik]

On Thursday, 14 May 2015 04:06:16 UTC+1, Phoenix wrote:

This is really weird that SAGE output that I copy pasted here can't be copy-pasted back into SAGE as an input!

no, not at all. It's very typical that the human-readable output (e.g. think of formulae with indices, inegrals, etc) is not the same as machine-readable output 

[David Joyner]

On Wed, May 13, 2015 at 9:13 PM, Phoenix <anirbit....@gmail.com> wrote:
>
>

> So I have this SAGE code which takes in two integers q and n and it
> generates ~ (q^3)^(n^2) 0/1 matrices and does a sum of their characteristic
> polynomials.
>
> I got answers for (q = 3, n = 2), (q =2 , n = 3) and (q=2, n=2)
>
> For any higher number the code runs for ~1hr and then it says,
>
> "
>
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> File "_sage_input_2.py", line 10, in <module>
> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8
> -*-\\n" +
> _support_.preparse_worksheet_cell(base64.b64decode("UA=="),globals())+"\\n");
> execfile(os.path.abspath("___code___.py"))
> File "", line 1, in <module>
>
> File "/tmp/tmpPiPIoq/___code___.py", line 2, in <module>
> exec compile(u'P
> File "", line 1, in <module>
>
> "
>
>
> Can someone help understand what is going on?
>
> Like any suggestion about how to go about it?
>

I cannot reproduce this error:


q=2; n =2

rep = [ matrix ([[1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 0, 1,
0]] ), matrix ([[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0,
0]] ) , matrix ([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1,
0]] ) , matrix ( [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0,
1]] ) , matrix ( [[1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 0,
0]]) , matrix ([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0,
1]] ) ]

Edge = [(0, 2), (0, 3), (1, 2), (1, 3)]

P = 0
from itertools import product
from itertools import izip

for X in product(rep,repeat = len (Edge)):
k = izip(Edge,X)
M = [[matrix(q^2, q^2, 0)]*(2*n) for _ in range(2*n)]
for ((a,b),Y) in k:
M[a][b] = Y
M[b][a] = Y.inverse()
Z = block_matrix(M)
P = P + Z.charpoly(x)

print P


gives

1296*x^16 - 20736*x^14 + 129600*x^12 - 393984*x^10 + 584496*x^8 -
362880*x^6 + 62208*x^4

>
>
> EDIT:
>
> This is basically the main time-consuming step.
>
> At this point "rep" comes in as a ~q^3 size list of q^2 dimensional 0/1
> permutation matrices.
> And "Edge" is a list of integer tuples where each tuple is of the form (a,b)
> with a,b being from the set {0,1,2,3...,(2n-1)}
>
> P = 0
> from itertools import product
> from itertools import izip
>
> for X in product(rep,repeat = len (Edge)):
> k = izip(Edge,X)
> M = [[matrix(q^2, q^2, 0)]*(2*n) for _ in range(2*n)]
> for ((a,b),Y) in k:
> M [a][b] = Y
> M [b][a] = Y.inverse()
> Z = block_matrix(M)
> P = P + Z.charpoly(x)
>
> The polynomial P is the final expected answer.
>
> (and for any larger value of q and n than the 3 cases mentioned the program
> basically stops with no output for P and with the above pasted message)
>

[Dima Pasechnik]

The poster has not provided an example producing the error.

One needs to increase q and/or n, as it is mentioned in the post.  

[David Joyner]

On Thu, May 14, 2015 at 6:59 AM, Dima Pasechnik <dim...@gmail.com> wrote:
> The poster has not provided an example producing the error.
> One needs to increase q and/or n, as it is mentioned in the post.
>

I missed that. Is it possible that the error is entirely due to the
way sagecell writes it to a file for execution in Python, and not the
code itself?

[Phoenix]

Try q=2 n=4 or q=3 n=3 to see the "error" :) 

[David Joyner]

On Thu, May 14, 2015 at 1:45 PM, Phoenix <anirbit....@gmail.com> wrote:
>
> Try q=2 n=4 or q=3 n=3 to see the "error" :)
>

Perhaps you can post rep and Edge in that case (in a format that can
be copy+pasted), or put them into a file and attach it or upload it
somewhere.

[Phoenix]

This is how "Edge" is created, 

g = graphs.CompleteBipartiteGraph(n, n)

Edge = []
for (a,b,c) in g.edges ():
    Edge.append ( (a,b) )

This is how "rep" is created, 

Fq2 = []
for i in range (q):
    for j in range (q):
      Fq2.append (matrix([[i],[j]]))

SL2Fq = []
for i1 in range (q):
    for i2 in range (q):
       for i3 in range(q):
         for i4 in range (q):
                if (i4*i1-i2*i3)% q == 1 :
                    SL2Fq.append ( matrix( [ [i1, i2],[i3,i4] ] ) )

rep = []
for Y in SL2Fq:
    M = []
    for A in Fq2:
        B = (Y*A)%q
        row = []
        for C in Fq2:
            if B == C :
                row.append ([1])
            else :
                row.append ([0])
        M.append(flatten(row))
    rep.append (matrix(M).transpose())

[Dima Pasechnik]

On Thursday, 14 May 2015 19:20:43 UTC+1, Phoenix wrote:

This is how "Edge" is created, 

g = graphs.CompleteBipartiteGraph(n, n)

Edge = []
for (a,b,c) in g.edges ():
    Edge.append ( (a,b) )

This is how "rep" is created, 

Fq2 = []
for i in range (q):
    for j in range (q):
      Fq2.append (matrix([[i],[j]]))

SL2Fq = []
for i1 in range (q):
    for i2 in range (q):
       for i3 in range(q):
         for i4 in range (q):
                if (i4*i1-i2*i3)% q == 1 :
                    SL2Fq.append ( matrix( [ [i1, i2],[i3,i4] ] ) )

how about

SL2Fq=list(SL(2,q))

for q prime this is the same...
 

[Dima Pasechnik]

d

In short, rep is the list of permutation matrices obtained from the elements of SL(2,q) in its natural action
on F_q^2.

Well, we can spend more time understanding how (mathematically) you obtain your polynomials, but perhaps
it would be more efficient if you explain it yourself?

[Phoenix]

The time trouble starts at the point in the code where it doesn't matter where the permutation matrices comes from. 

What the main part does is basically this.

Given any set of matrices of dimensional k it produces by the "product" and "zip" command all possible ways of distributing those matrices over the set of edges of the graph of size n .
One fixes some arbitrary orientation for each of the edges. It doesn't matter what.
Now it creates a matrix M of size kn as a n x n array of size k matrices as follows : for the (a,b) edge is in the oriented edge list it (1) places into the (a,b) array position the matrix that was assigned to that edge and (2) it places into the (b,a) position the inverse of that matrix.  Now it calculates the characteristic polynomial of this M and keeps adding it up over all possible ways of distributing the matrices over the edges. 

[Anton Sherwood]

Is it only because I'm old that I see something inelegant about a post
that re-quotes (without commenting on any but the newest) eight
generations of quoted matter, including ninety blank lines and four
copies of "You received this message because"?

--
*\\* Anton Sherwood *\\* www.bendwavy.org

[Vincent Delecroix]

On 14/05/15 23:04, Anton Sherwood wrote:
> Is it only because I'm old that I see something inelegant about a post
> that re-quotes (without commenting on any but the newest) eight
> generations of quoted matter, including ninety blank lines and four
> copies of "You received this message because"?

I am getting old as well then ;-)

[David Joyner]

I ran the block below and it ran without error until I killed it (note
the additional print statement at the end) To me this suggests there
is no problem with your code. There might be a problem managing a
large list. If that is the case, you'll need to think more about other
ways to do the computation.


To the OP: if you had simply supplied the block below initially, as
William Stein suggested, you would have saved both your time and ours.



q=2; n=4

g = graphs.CompleteBipartiteGraph(n, n)

Edge = []
for (a,b,c) in g.edges ():
Edge.append ( (a,b) )

#This is how "rep" is created,

Fq2 = []
for i in range (q):
for j in range (q):
Fq2.append (matrix([[i],[j]]))

SL2Fq = []
for i1 in range (q):
for i2 in range (q):
for i3 in range(q):
for i4 in range (q):
if (i4*i1-i2*i3)% q == 1 :
SL2Fq.append ( matrix( [ [i1, i2],[i3,i4] ] ) )

rep = []
for Y in SL2Fq:
M = []
for A in Fq2:
B = (Y*A)%q
row = []
for C in Fq2:
if B == C:
row.append ([1])
else:
row.append ([0])
M.append(flatten(row))
rep.append (matrix(M).transpose())

P = 0
from itertools import product
from itertools import izip

for X in product(rep,repeat = len (Edge)):
k = izip(Edge,X)

M = [[matrix(q^2, q^2, 0)]*(2*n) for ell in range(2*n)]

for ((a,b),Y) in k:
M [a][b] = Y
M [b][a] = Y.inverse()
Z = block_matrix(M)
P = P + Z.charpoly(x)
print P

[Phoenix]

I initially didn't think that its necessary to talk about the source of the lists "rep" and "Edge" and hence I didn't include those in the question.
I thought the question could be answered in the abstract. 

But then for me it gives me this "error" message quoted in the first post for q=2, n=3 or q=2, n=4 or q=3, n=3.
And hence I was wondering as to what is the error that SAGE is complaining about.

If it is just a matter of a long running time then leaving it to run for hours or days should have produced the answer.
But that is not the case.

Or can you suggest any optimization that can help the running time of the last block ?