CODEWITHSUNDEEP
pythonmathlinear-algebrawolfram-mathematicaequation-solving
Antonio Morales
Antonio Morales

Reputation: 1

How can I obtain all possible solutions for an underdetermined system of linear equations in Python?

I was interested in obtaining all possible solutions for a under-determined linear problem in Python. To be more specific, let us assume we have only one equation, several variables and we want to solve it in the positive integers. This can be expressed in Python using SymPy. Let me introduce an example:

import numpy as np
import sympy as sp

coeff = [2, 2, 4, 6, 6, 4, 4, 4, 4, 8, 8, 4, 4, 4, 4, 8, 8, 6, 6, 6, 6, 12, 12, 12, 12]

symbol_names = [f'x{i}' for i in range(len(coeff))]
xvec = sp.symbols(symbol_names, integer=True, positive=True)

Using this notation, the linear problem can be easily expressed as a dot product. If we wanted the equation to be equal to 2, for example, the equation will be np.dot(dim_ebrs, xvec)-2].

Using the library SymPy I tried to solve the equation, obtaining the following

sp.solve([np.dot(dim_ebrs, xvec)-2], xvec, dict=True)

[{x0: -x1 - 4*x10 - 2*x11 - 2*x12 - 2*x13 - 2*x14 - 4*x15 - 4*x16 - 3*x17 - 3*x18 - 3*x19 - 2*x2 - 3*x20 - 6*x21 - 6*x22 - 6*x23 - 6*x24 - 3*x3 - 3*x4 - 2*x5 - 2*x6 - 2*x7 - 2*x8 - 4*x9 + 1}]

It just solved it for one variable instead of giving actual values for every variable. I was expecting something more similar as obtained in Mathematica:

Solve[{xvec . dim == 2, xvec >= 0}, xvec, Integers]

{{x1 -> 0, x2 -> 1, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 0, 
  x8 -> 0, x9 -> 0, x10 -> 0, x11 -> 0, x12 -> 0, x13 -> 0, x14 -> 0, 
  x15 -> 0, x16 -> 0, x17 -> 0, x18 -> 0, x19 -> 0, x20 -> 0, 
  x21 -> 0, x22 -> 0, x23 -> 0, x24 -> 0, x25 -> 0}, {x1 -> 1, 
  x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 0, x8 -> 0, 
  x9 -> 0, x10 -> 0, x11 -> 0, x12 -> 0, x13 -> 0, x14 -> 0, x15 -> 0,
   x16 -> 0, x17 -> 0, x18 -> 0, x19 -> 0, x20 -> 0, x21 -> 0, 
  x22 -> 0, x23 -> 0, x24 -> 0, x25 -> 0}}

It is possible to obtain all possible values that satisfy the equation in Python?

Thanks in advance

Upvotes: 0

Views: 139

Answers (1)

Antonio Morales
Antonio Morales

Reputation: 1

I managed to perform a little code that does the work for the case I exposed. I generalized a bit for any system of the type: xvec . v == 2*t, where xvec is the solution we seek. I post it over here:

def sols(v, t):      
    
    x_max = 2*t // np.array(v)
    l = [range(i+1) for i in x_max]
    A_vec = np.array([list(elem) for elem in it.product(*l)])
    x_vec = A_vec[(A_vec @ dim ==2*t), :]
    return np.array(x_vec)

However, as soon as t grows the algorithm takes a lot of time. Is there a possible way of optimizing it?

Thanks

Upvotes: 0

Related Questions