sympy solve method

[Sylvain Meunier]

Hello,

I'm trying to prove the following system has no solution using sympy (one of my first attempt to use sympy) :

a_1 = Symbol('a_1')
a_2 = Symbol('a_2')
a_3 = Symbol('a_3')
a_4 = Symbol('a_4')
b_1 = Symbol('b_1')
b_2 = Symbol('b_2')
b_3 = Symbol('b_3')
b_4 = Symbol('b_4')

system = [
    a_1*b_2 - a_2*b_1 - 1,
    a_1*b_3 - a_3*b_1,
    a_1*b_4 - a_4*b_1,
    a_2*b_3 - a_3*b_2,
    a_2*b_4 - a_4*b_2,
    a_3*b_4 - a_4*b_3 - 1
]

unknowns = [
    a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4
]

result = solve(system, unknowns)

I expect result would be an empty dictionary but an exception is raised :

Traceback (most recent call last):
  File "D:\Sandbox\galgebra\tests\test_chapter2.py", line 162, in test
    R = solve(system, unknowns)
  File "D:\Tools\WinPython-2.7\python-2.7.10.amd64\lib\site-packages\sympy\solvers\solvers.py", line 911, in solve
    solution = _solve_system(f, symbols, **flags)
  File "D:\Tools\WinPython-2.7\python-2.7.10.amd64\lib\site-packages\sympy\solvers\solvers.py", line 1522, in _solve_system
    raise NotImplementedError('no valid subset found')
NotImplementedError: no valid subset found

Best regards

Sylvain

[Kshitij Saraogi]

Hello Sylvian,

It seems `solve` is unable to handle this.

However, you can try using the `solve_poly_system` function in your case.

`In []: result = solve_poly_system(system, unknowns)`

This returns a NoneType result which is indicative of the system being inconsistent.
I think we need to  improve upon this in the codebase.

Thanks for pointing it out.

--------------------
Kshitij Saraogi

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at https://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/3af4090c-6e34-455a-afc0-7e11bf39c172%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Sylvain Meunier]

Thank you

[Aaron Meurer]

solve() is incapable of proving that solutions don't exist. If you get
NotImplementedError or even an empty dictionary, it doesn't
necessarily mean there are no solutions, only that it couldn't find
any. solveset is capable of doing this, but it doesn't support systems
yet.

I'm unsure if solve_poly_system returning None necessarily means that
there are no solutions, as Kshitij suggests. It may be the case, but
it isn't documented, so we would need to check the code to be sure.

Aaron Meurer

[Kshitij Saraogi]

Also, in order to prove a system of polynomials to be inconsistent, we can show that its reduced Gröbner basis is 1. [1]

In [13]: groebner(system, unknowns)

Out[13]: GroebnerBasis([1], a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4, domain='ZZ', order='lex')

In the problem at hand, we do get the desired result.
Thus, we can say that the system is inconsistent.

 

I'm unsure if solve_poly_system returning None necessarily means that
there are no solutions, as Kshitij suggests. It may be the case, but
it isn't documented, so we would need to check the code to be sure.

The `solve_poly_sys` is limited by the ability of the root finding algorithms.
And if no solutions are found, that doesn't necessarily mean that the system is inconsistent.

I shouldn't have been so bold to assume this.
Thanks for pointing this out. 

The algorithm we implement in `solve_generic` assumes the system to be zero-dimensional.

However, I think we need to refactor the code to reflect that cases where the system is inconsistent or not
using the reduced Groebner Basis of the system.
Also, wouldn't it be a good idea to check whether the system is zero-dimensional or not before running the algorithm ?

[1]: https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis#Solutions_of_a_system_of_algebraic_equations

--------------------
Kshitij Saraogi