ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 08 Jan 2023 18:45:02 +0100How to speed up this codehttps://ask.sagemath.org/question/65274/how-to-speed-up-this-code/Given a square matrix M, to find (say) five sets of, (say) 4 matrices A1,A2,A3,A4 such that
(i) each Ai is a unique 0,1 or 0,-1 matrix
(ii) each Ai is not - all zeroes or all ones or all minus ones matrix(that is, matrices with all entries same are not allowed)
(iii) M= A1+A2+A3+A4
(iv) Each matrix product AiAj (i,j=1,2,3,4)is a linear combination of A1,A2,A3,A4 with integer coefficients.
This is the same problem which was discussed in :
https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/
But there we wanted “all possible combinations” satisfying the required conditions. There we basically discussed the process for first getting all combinations satisfying (iii) and then checked condition(iv). But for 3rd order and above no output even after one week.
So thought that rather than first collecting all combinations satisfying(iii) it would be better to check (iv) alongside individually and after say, five outputs , the program ends, as even this much would also help me for my work .
I have made the following code:
#Given Matrix
M = matrix(2,2, [1, 2, 2, -1])
show("M=",M)
n = int(input("Enter the order of the matrix M : "))
T = Tuples((0,1),(n^2))
#Removing all-zero and all-one tuples as not needed for our case"
R=T.list()[1:-1]
#Forming n by n matrices from list in R. Contains all {0,1 }matrices.
P = []
for v in R:
P.append(matrix(ZZ,n,n,v))
#Forming all n by n , {0,-1} matrices.
N=[]
for a in P:
b=-a
N.append(b)
test_sum = int(input("In how many matrices you want to break M :"))
num_nonneg = int(input("How many matrices with non-negative entries you want :"))
num_nonpos = (test_sum)-(num_nonneg)
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos )
#Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector( sum(map(list,m.rows()), []), immutable=True )
Counter=0
X = ZZ^(n^2)
for a in nonneg_comb:
for b in nonpos_comb:
flag=0
V = X.span(mat_to_vector((a+b)[i]) for i in range(len((a+b))))
for i in range(test_sum):
for j in range(test_sum):
if( (sum(a+b)!=M) or (mat_to_vector((a+b)[i]*(a+b)[j]) not in V)):
flag=1
if(flag==0):
Counter+=1
show("(",Counter,").", a+b)
if Counter==5:
break;
But this is also time taking for higher orders. So, wanted to know how it can be speeded up or how the code given by Max Alekseyev in the above link can accordingly be edited.Thu, 08 Dec 2022 06:13:33 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/Answer by cmark for <p>Given a square matrix M, to find (say) five sets of, (say) 4 matrices A1,A2,A3,A4 such that</p>
<p>(i) each Ai is a unique 0,1 or 0,-1 matrix</p>
<p>(ii) each Ai is not - all zeroes or all ones or all minus ones matrix(that is, matrices with all entries same are not allowed)</p>
<p>(iii) M= A1+A2+A3+A4 </p>
<p>(iv) Each matrix product AiAj (i,j=1,2,3,4)is a linear combination of A1,A2,A3,A4 with integer coefficients.</p>
<p>This is the same problem which was discussed in :</p>
<p><a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/">https://ask.sagemath.org/question/642...</a></p>
<p>But there we wanted “all possible combinations” satisfying the required conditions. There we basically discussed the process for first getting all combinations satisfying (iii) and then checked condition(iv). But for 3rd order and above no output even after one week.</p>
<p>So thought that rather than first collecting all combinations satisfying(iii) it would be better to check (iv) alongside individually and after say, five outputs , the program ends, as even this much would also help me for my work .
I have made the following code:</p>
<pre><code>#Given Matrix
M = matrix(2,2, [1, 2, 2, -1])
show("M=",M)
n = int(input("Enter the order of the matrix M : "))
T = Tuples((0,1),(n^2))
#Removing all-zero and all-one tuples as not needed for our case"
R=T.list()[1:-1]
#Forming n by n matrices from list in R. Contains all {0,1 }matrices.
P = []
for v in R:
P.append(matrix(ZZ,n,n,v))
#Forming all n by n , {0,-1} matrices.
N=[]
for a in P:
b=-a
N.append(b)
test_sum = int(input("In how many matrices you want to break M :"))
num_nonneg = int(input("How many matrices with non-negative entries you want :"))
num_nonpos = (test_sum)-(num_nonneg)
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos )
#Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector( sum(map(list,m.rows()), []), immutable=True )
Counter=0
X = ZZ^(n^2)
for a in nonneg_comb:
for b in nonpos_comb:
flag=0
V = X.span(mat_to_vector((a+b)[i]) for i in range(len((a+b))))
for i in range(test_sum):
for j in range(test_sum):
if( (sum(a+b)!=M) or (mat_to_vector((a+b)[i]*(a+b)[j]) not in V)):
flag=1
if(flag==0):
Counter+=1
show("(",Counter,").", a+b)
if Counter==5:
break;
</code></pre>
<p>But this is also time taking for higher orders. So, wanted to know how it can be speeded up or how the code given by Max Alekseyev in the above link can accordingly be edited.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?answer=65436#post-id-65436I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:
<pre>
# Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:
<pre>
import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
My final iteration, using the 'parallel' module:
<pre>
import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:
<pre>
@parallel(ncpus=4)
def process_combinations(
</pre>
You can give this a go, too.Wed, 21 Dec 2022 17:28:11 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?answer=65436#post-id-65436Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65827#post-id-65827Yes, thanks, I know you have put in a lot of time and efforts. Thanks from the bottom of my heart for all that.
Thought of informing you about the latest developments, hence had posted the last comment. Thanks again.Sun, 08 Jan 2023 18:45:02 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65827#post-id-65827Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65825#post-id-65825I've done everything I could, please use the code which works best for you.Sun, 08 Jan 2023 17:07:53 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65825#post-id-65825Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65824#post-id-65824When I ran the last code you have posted here on this page, in Jupyter and supercomputer got no output
and on Sagemath Console got the following outputs which is long one , output being printed for more than 90 seconds
..............................................................
............................................................
<generator object p_iter_fork.__call__ at 0x6fff50264c50>
<generator object p_iter_fork.__call__ at 0x6fff50264dd0>
<generator object p_iter_fork.__call__ at 0x6fff50264f50>Sun, 08 Jan 2023 16:12:51 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65824#post-id-65824Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65822#post-id-65822I ran the earlier code(No.6, Revision, second one in Revision History) on Sagemath Console instead of Jupyter notebook and for the same input, that is:
"M = matrix(2, 2, [1, 1, 1, -1])
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2"
And got 30 outputs (all numbered '0') and checked that out of these there are 18 which are the valid total number of required outputs((30th output being the 18th required valid one). That means it stops at the last required valid output.
When I ran the same on supercomputer, I got the same output in the output file and in the error file got the "name error" message.Sun, 08 Jan 2023 15:44:15 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65822#post-id-65822Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65782#post-id-65782Alright, I couldn't contain myself and had one last idea, using Sage's very own 'parallel' module, please check it out, I've updated my answer. I tested it with your matrices so far, without error.Thu, 05 Jan 2023 19:31:56 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65782#post-id-65782Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65769#post-id-65769No, what I meant is the actual code (that's what I wrote :)), what you changed in the script. The original, what I'm using is this:
<pre>
M = matrix(2,2, [1, 2, 2, -1])
</pre>
This works, as you can see in my output. So plesase give me the actual line for `M`, what you are using in the new setup.Thu, 05 Jan 2023 13:59:31 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65769#post-id-65769Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65755#post-id-65755Are you quite sure you ran the new code? I ran it with test numbers and received no errors whatsoever.
However, I've adjusted the code a bit around how itertools works, but however I run it now, don't experience any errors. There are two codes no in my answer, please use the latter (the second) one.
If you still encounter errors, please give the the input you used so I can try the code with that myself, as at the moment I don't see where the problem could be.Thu, 05 Jan 2023 09:58:11 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65755#post-id-65755Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65777#post-id-65777Yup, I noted that, but as it seems, I can't make this code faster and still work reliably. These two codes are my best output.
If you want to tinker with it, you can try and implement the multiprocessing module as I've tried, but I'm afraid I can't help anymore.Thu, 05 Jan 2023 16:36:12 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65777#post-id-65777Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65776#post-id-65776Yes, your first code was indeed very good and fast, as I have mentioned in my very first comment. I am getting the same output as you have got in this last comment of yours. But, as for higher orders it was time-taking so had requested in my first comment for ways to make it faster and how to write in parallel to make optimum use of supercomputer.Thu, 05 Jan 2023 16:32:46 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65776#post-id-65776Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65774#post-id-65774The previously mentioned code is now the second code in my answer. I think this is the end of the road for me; also, I wanted to leave a working code in the answer, now both does.Thu, 05 Jan 2023 16:18:41 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65774#post-id-65774Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65773#post-id-65773I don't know. At some point I've introduced an ifninite loop but couldn't find to so I took a step back and went back to one of my previous solutions, this works alright:
<pre>
user@host ~ % sage ask.sage
'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 2
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2
'(' 1 ').' [
[1 0] [1 1] [-1 0] [ 0 0]
[0 0], [1 0], [ 0 0], [ 0 -1]
]
'(' 2 ').' [
[0 1] [1 1] [ 0 -1] [ 0 0]
[0 0], [1 0], [ 0 0], [ 0 -1]
]
'(' 3 ').' [
[1 1] [1 0] [-1 0] [ 0 0]
[0 0], [1 0], [ 0 0], [ 0 -1]
]
'(' 4 ').' [
[1 1] [0 1] [ 0 -1] [ 0 0]
[0 0], [1 0], [ 0 0], [ 0 -1]
]
'(' 5 ').' [
[1 1] [1 1] [-1 0] [ 0 -1]
[0 0], [1 0], [ 0 0], [ 0 -1]
]
</pre>
Please check how well it works out for you.Thu, 05 Jan 2023 16:17:37 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65773#post-id-65773Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65772#post-id-65772What could be possible reasons behind vast diifference between your output and mine? What to do now?Thu, 05 Jan 2023 14:43:32 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65772#post-id-65772Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65771#post-id-65771Thanks, I didn't notice. However, I can't seem to run the input you gave me (an example run before the problem):
<pre>
user@host ~ % sage ask.sage
'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 1
In how many matrices you want to break M: 2
How many matrices with non-negative entries you want: 3
user@host ~ %
user@host ~ % sage ask.sage
'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 2
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2
'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M: 'M=' [ 1 1]
[ 1 -1]
Enter the order of the matrix M:
</pre>
It seems to loop. However, I don't see any NameError problems.Thu, 05 Jan 2023 14:26:03 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65771#post-id-65771Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65770#post-id-65770As I have mentioned in my previous two comments, I have taken M as follows:`
M = matrix(2, 2, [1, 1, 1, -1])`Thu, 05 Jan 2023 14:09:03 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65770#post-id-65770Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65768#post-id-65768My input and output for M = matrix(2, 2, [1, 1, 1, -1]) are as follows:
𝙼=(111−1)
Enter the order of the matrix M: 2
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
<ipython-input-2-019b8e8093bc> in <module>
56 if result:
57 Counter += Integer(1)
---> 58 show("(", Counter, ").", a+b)
59 if Counter == Integer(5):
60 break
NameError: name 'a' is not definedThu, 05 Jan 2023 13:49:06 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65768#post-id-65768Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65763#post-id-65763I just ran my latest code (with the original data in your very first script, you can see I never changed it), please see that I experience no issues:
<pre>
user@host ~ % sage ask.sage
'M=' [ 1 2]
[ 2 -1]
Enter the order of the matrix M: 1
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2
user@host ~ %
</pre>
So I couldn't reproduce the errors. If you would want me to try it with another set of matrices, please send me the variable "M" exactly as you used it (I never used any other values so my code works for "M = matrix(2, 2, [1, 2, 2, -1])"). Please give me something easy to compute, I don't want to run this for hours to test. :)Thu, 05 Jan 2023 12:14:25 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65763#post-id-65763Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65757#post-id-65757I tried the following input:
M = matrix(2, 2, [1, 1, 1, -1])
In how many matrices you want to break M: 4
How many matrices with non-negative entries you want: 2Thu, 05 Jan 2023 10:19:44 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65757#post-id-65757Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65748#post-id-65748Sorry, but I am getting the same error now also.Thu, 05 Jan 2023 06:44:47 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65748#post-id-65748Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65743#post-id-65743Sorry about that, the 'a' and 'b' variables were defined out of scope, now I've edited the code again (also could ran this time, it did run just fine for me), please give it a try (now you see two codes in my answer, use the one under "Please see new code").Wed, 04 Jan 2023 22:13:07 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65743#post-id-65743Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65718#post-id-65718Thanks a lot again. I really appreciate the time and effort you are devoting to my problem, I ran the latest code and getting this error message "name 'a' is not defined", pointing towards the line 'show("(", Counter, ").", a+b)'. I tried to make some changes and work it out, but failed to do so.Wed, 04 Jan 2023 07:21:00 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65718#post-id-65718Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65695#post-id-65695There was indeed a typo in the beginning of the code. The itertools module was indeed missing, sorry about them (I'm working on this code off the top of my head). Please see the new iteration, I've changed the necessary lines.Tue, 03 Jan 2023 18:04:58 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65695#post-id-65695Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65691#post-id-65691Also, the specifications of the supercomputer I will be using and the commands for requesting the resources in mentioned in the link
https://ask.sagemath.org/question/63878/making-code-faster-by-splitting-and-use-of-supercomputer/
Kindly guide me how to choose the resources for this code which you have made.Tue, 03 Jan 2023 12:57:38 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65691#post-id-65691Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65690#post-id-65690Thanks a lot again for looking into my problem and modifying the code. Let me mention that I have only elementary knowledge of sagemath and absolutely no knowledge of parallel processing. But I think there is typo error in the first line. If I am not mistaken it should be 'multiprocessing' instead of 'iprocessing'. Also 'import itertools' is to be added. When I ran the code after making these changes, I got the error that "check_combination() takes 1 positional argument but 2 were given". I am not able to figure it out. Kindly look into it. Also, right now there is some problem with the supercomputer,I will be able to use it most probably by this weekend.Tue, 03 Jan 2023 12:48:34 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65690#post-id-65690Comment by cmark for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65639#post-id-65639I've edited my answer with a modfied code, have a go at it.Sat, 31 Dec 2022 18:32:49 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65639#post-id-65639Comment by sgmth for <p>I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some more (mostly vectorizations) to speed it up, I think it's siginificant (it also goes easier on the machine due to the aforementioned changes). There you go, give it a try:</p>
<pre># Given Matrix
M = matrix(2, 2, [1, 2, 2, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:</p>
<pre>import itertools
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Defining a function which converts matrix to vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
for a in nonneg_comb:
for b in nonpos_comb:
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
if Counter == 5:
break
</pre>
<p>My final iteration, using the 'parallel' module:</p>
<pre>import itertools
from sage.parallel.decorate import parallel
# Given Matrix
#M = matrix(2, 2, [1, 2, 2, -1])
M = matrix(2, 2, [1, 1, 1, -1])
show("M=", M)
n = int(input("Enter the order of the matrix M: "))
T = Tuples((0, 1), (n**2))
# Removing all-zero and all-one tuples as not needed for our case
R = T.list()[1:-1]
# Forming n by n matrices from list in R. Contains all {0, 1} matrices.
P = [matrix(ZZ, n, n, v) for v in R]
# Forming all n by n, {0, -1} matrices.
N = [-a for a in P]
test_sum = int(input("In how many matrices you want to break M: "))
num_nonneg = int(input("How many matrices with non-negative entries you want: "))
num_nonpos = test_sum - num_nonneg
nonneg_comb = Combinations(P, num_nonneg)
nonpos_comb = Combinations(N, num_nonpos)
# Define a function to convert a matrix to a vector
def mat_to_vector(m):
return vector(sum(map(list, m.rows()), []), immutable=True)
# Convert all matrices in P and N to vectors
P_vectors = [mat_to_vector(m) for m in P]
N_vectors = [mat_to_vector(m) for m in N]
# Create the span of all possible vectors
X = ZZ**(n**2)
V = X.span(P_vectors + N_vectors)
# Initialize counter
Counter = 0
# Iterate over all combinations of positive and negative matrices
@parallel
def process_combinations(a, b):
global Counter
# Check if the sum of the matrices is equal to M and all possible pairwise products are in the span
if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
Counter += 1
show("(", Counter, ").", a+b)
for a in nonneg_comb:
for b in nonpos_comb:
process_combinations(a, b)
if Counter == 5:
break
</pre>
<p>Please note that you may need to adjust the number of worker processes used by the parallel decorator depending on the number of CPU cores available on your machine, like so:</p>
<pre>@parallel(ncpus=4)
def process_combinations(
</pre>
<p>You can give this a go, too.</p>
https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65638#post-id-65638Thanks a lot for your effort and time. Yes , this is certainly faster. Tried for 2nd order matrix. Now have run for 4th order. It is still running for the last few hours. Lets' see how long does it take. Can we break the code into , (say) two parts, so that we may first run the first part and then taking its output as input for the second part ? Because I have access to a supercomputer , but there is time limit for running a code. Or can the code be written in parallel to make optimum use of supercomputer ?Sat, 31 Dec 2022 16:25:34 +0100https://ask.sagemath.org/question/65274/how-to-speed-up-this-code/?comment=65638#post-id-65638