Ask Your Question

Revision history [back]

I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications (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

I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications (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 iprocessing as mp

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
    a, b = comb
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

I couldn't run your original code as-is, I had to make some modifications to it. After that I've made some modifications 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 iprocessing as mp

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
    a, b = comb
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

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 iprocessing as mp

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
    a, b = comb
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

Here is the new code:

import multiprocessing as mp
import itertools

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

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 iprocessing multiprocessing as mp
import itertools

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(comb):
    a, b = comb
check_combination(a, b):
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

Here is the new code:

import multiprocessing as mp
import itertools

# 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

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

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 multiprocessing as mp
import itertools

# 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

# Add check to make sure num_nonpos is non-negative
if num_nonpos < 0:
    num_nonpos = 0
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

# Define a function to check a single combination of positive and negative matrices
def check_combination(a, b):
    if (sum(a+b) == M) and all(mat_to_vector(m1 * m2) in V for m1, m2 in itertools.product(a+b, repeat=2)):
        show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

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 multiprocessing as mp
import itertools

# Given Matrix
M #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

# Add check to make sure num_nonpos is non-negative
if num_nonpos < 0:
    num_nonpos = 0
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

# Define a function to check a single combination Iterate over all combinations of positive and negative matrices
def check_combination(a, b):
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)):
        show("(", Counter, ").", a+b)  # Pass a and b as arguments to show
        return True
    return False

# Iterate over all combinations of positive and negative matrices in parallel using multiprocessing
with mp.Pool() as pool:
    for result in pool.starmap(check_combination, itertools.product(nonneg_comb, nonpos_comb)):
        if result:
            Counter += 1
            show("(", Counter, ").", a+b)
        if Counter == 5:
            break

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.
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59