Ask Your Question

# 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/642...

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.

edit retag close merge delete

## 1 Answer

Sort by » oldest newest most voted

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.

more

## Comments

Thanks 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 ?

( 2022-12-31 16:25:34 +0200 )edit
1

I've edited my answer with a modfied code, have a go at it.

( 2022-12-31 18:32:49 +0200 )edit

Thanks 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.

( 2023-01-03 12:48:34 +0200 )edit

Also, 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/638...

Kindly guide me how to choose the resources for this code which you have made.

( 2023-01-03 12:57:38 +0200 )edit
1

There 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.

( 2023-01-03 18:04:58 +0200 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2022-12-08 06:13:33 +0200

Seen: 663 times

Last updated: Jan 05 '23