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:
# 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
This should allow the code to run significantly faster on a machine with multiple CPU cores. Please see the new code:
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
My final iteration, using the 'parallel' module:
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
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:
@parallel(ncpus=4)
def process_combinations(
You can give this a go, too.
