441 lines
13 KiB
Python
441 lines
13 KiB
Python
"""Solvers of systems of polynomial equations. """
|
|
import itertools
|
|
|
|
from sympy.core import S
|
|
from sympy.core.sorting import default_sort_key
|
|
from sympy.polys import Poly, groebner, roots
|
|
from sympy.polys.polytools import parallel_poly_from_expr
|
|
from sympy.polys.polyerrors import (ComputationFailed,
|
|
PolificationFailed, CoercionFailed)
|
|
from sympy.simplify import rcollect
|
|
from sympy.utilities import postfixes
|
|
from sympy.utilities.misc import filldedent
|
|
|
|
|
|
class SolveFailed(Exception):
|
|
"""Raised when solver's conditions were not met. """
|
|
|
|
|
|
def solve_poly_system(seq, *gens, strict=False, **args):
|
|
"""
|
|
Return a list of solutions for the system of polynomial equations
|
|
or else None.
|
|
|
|
Parameters
|
|
==========
|
|
|
|
seq: a list/tuple/set
|
|
Listing all the equations that are needed to be solved
|
|
gens: generators
|
|
generators of the equations in seq for which we want the
|
|
solutions
|
|
strict: a boolean (default is False)
|
|
if strict is True, NotImplementedError will be raised if
|
|
the solution is known to be incomplete (which can occur if
|
|
not all solutions are expressible in radicals)
|
|
args: Keyword arguments
|
|
Special options for solving the equations.
|
|
|
|
|
|
Returns
|
|
=======
|
|
|
|
List[Tuple]
|
|
a list of tuples with elements being solutions for the
|
|
symbols in the order they were passed as gens
|
|
None
|
|
None is returned when the computed basis contains only the ground.
|
|
|
|
Examples
|
|
========
|
|
|
|
>>> from sympy import solve_poly_system
|
|
>>> from sympy.abc import x, y
|
|
|
|
>>> solve_poly_system([x*y - 2*y, 2*y**2 - x**2], x, y)
|
|
[(0, 0), (2, -sqrt(2)), (2, sqrt(2))]
|
|
|
|
>>> solve_poly_system([x**5 - x + y**3, y**2 - 1], x, y, strict=True)
|
|
Traceback (most recent call last):
|
|
...
|
|
UnsolvableFactorError
|
|
|
|
"""
|
|
try:
|
|
polys, opt = parallel_poly_from_expr(seq, *gens, **args)
|
|
except PolificationFailed as exc:
|
|
raise ComputationFailed('solve_poly_system', len(seq), exc)
|
|
|
|
if len(polys) == len(opt.gens) == 2:
|
|
f, g = polys
|
|
|
|
if all(i <= 2 for i in f.degree_list() + g.degree_list()):
|
|
try:
|
|
return solve_biquadratic(f, g, opt)
|
|
except SolveFailed:
|
|
pass
|
|
|
|
return solve_generic(polys, opt, strict=strict)
|
|
|
|
|
|
def solve_biquadratic(f, g, opt):
|
|
"""Solve a system of two bivariate quadratic polynomial equations.
|
|
|
|
Parameters
|
|
==========
|
|
|
|
f: a single Expr or Poly
|
|
First equation
|
|
g: a single Expr or Poly
|
|
Second Equation
|
|
opt: an Options object
|
|
For specifying keyword arguments and generators
|
|
|
|
Returns
|
|
=======
|
|
|
|
List[Tuple]
|
|
a list of tuples with elements being solutions for the
|
|
symbols in the order they were passed as gens
|
|
None
|
|
None is returned when the computed basis contains only the ground.
|
|
|
|
Examples
|
|
========
|
|
|
|
>>> from sympy import Options, Poly
|
|
>>> from sympy.abc import x, y
|
|
>>> from sympy.solvers.polysys import solve_biquadratic
|
|
>>> NewOption = Options((x, y), {'domain': 'ZZ'})
|
|
|
|
>>> a = Poly(y**2 - 4 + x, y, x, domain='ZZ')
|
|
>>> b = Poly(y*2 + 3*x - 7, y, x, domain='ZZ')
|
|
>>> solve_biquadratic(a, b, NewOption)
|
|
[(1/3, 3), (41/27, 11/9)]
|
|
|
|
>>> a = Poly(y + x**2 - 3, y, x, domain='ZZ')
|
|
>>> b = Poly(-y + x - 4, y, x, domain='ZZ')
|
|
>>> solve_biquadratic(a, b, NewOption)
|
|
[(7/2 - sqrt(29)/2, -sqrt(29)/2 - 1/2), (sqrt(29)/2 + 7/2, -1/2 + \
|
|
sqrt(29)/2)]
|
|
"""
|
|
G = groebner([f, g])
|
|
|
|
if len(G) == 1 and G[0].is_ground:
|
|
return None
|
|
|
|
if len(G) != 2:
|
|
raise SolveFailed
|
|
|
|
x, y = opt.gens
|
|
p, q = G
|
|
if not p.gcd(q).is_ground:
|
|
# not 0-dimensional
|
|
raise SolveFailed
|
|
|
|
p = Poly(p, x, expand=False)
|
|
p_roots = [rcollect(expr, y) for expr in roots(p).keys()]
|
|
|
|
q = q.ltrim(-1)
|
|
q_roots = list(roots(q).keys())
|
|
|
|
solutions = [(p_root.subs(y, q_root), q_root) for q_root, p_root in
|
|
itertools.product(q_roots, p_roots)]
|
|
|
|
return sorted(solutions, key=default_sort_key)
|
|
|
|
|
|
def solve_generic(polys, opt, strict=False):
|
|
"""
|
|
Solve a generic system of polynomial equations.
|
|
|
|
Returns all possible solutions over C[x_1, x_2, ..., x_m] of a
|
|
set F = { f_1, f_2, ..., f_n } of polynomial equations, using
|
|
Groebner basis approach. For now only zero-dimensional systems
|
|
are supported, which means F can have at most a finite number
|
|
of solutions. If the basis contains only the ground, None is
|
|
returned.
|
|
|
|
The algorithm works by the fact that, supposing G is the basis
|
|
of F with respect to an elimination order (here lexicographic
|
|
order is used), G and F generate the same ideal, they have the
|
|
same set of solutions. By the elimination property, if G is a
|
|
reduced, zero-dimensional Groebner basis, then there exists an
|
|
univariate polynomial in G (in its last variable). This can be
|
|
solved by computing its roots. Substituting all computed roots
|
|
for the last (eliminated) variable in other elements of G, new
|
|
polynomial system is generated. Applying the above procedure
|
|
recursively, a finite number of solutions can be found.
|
|
|
|
The ability of finding all solutions by this procedure depends
|
|
on the root finding algorithms. If no solutions were found, it
|
|
means only that roots() failed, but the system is solvable. To
|
|
overcome this difficulty use numerical algorithms instead.
|
|
|
|
Parameters
|
|
==========
|
|
|
|
polys: a list/tuple/set
|
|
Listing all the polynomial equations that are needed to be solved
|
|
opt: an Options object
|
|
For specifying keyword arguments and generators
|
|
strict: a boolean
|
|
If strict is True, NotImplementedError will be raised if the solution
|
|
is known to be incomplete
|
|
|
|
Returns
|
|
=======
|
|
|
|
List[Tuple]
|
|
a list of tuples with elements being solutions for the
|
|
symbols in the order they were passed as gens
|
|
None
|
|
None is returned when the computed basis contains only the ground.
|
|
|
|
References
|
|
==========
|
|
|
|
.. [Buchberger01] B. Buchberger, Groebner Bases: A Short
|
|
Introduction for Systems Theorists, In: R. Moreno-Diaz,
|
|
B. Buchberger, J.L. Freire, Proceedings of EUROCAST'01,
|
|
February, 2001
|
|
|
|
.. [Cox97] D. Cox, J. Little, D. O'Shea, Ideals, Varieties
|
|
and Algorithms, Springer, Second Edition, 1997, pp. 112
|
|
|
|
Raises
|
|
========
|
|
|
|
NotImplementedError
|
|
If the system is not zero-dimensional (does not have a finite
|
|
number of solutions)
|
|
|
|
UnsolvableFactorError
|
|
If ``strict`` is True and not all solution components are
|
|
expressible in radicals
|
|
|
|
Examples
|
|
========
|
|
|
|
>>> from sympy import Poly, Options
|
|
>>> from sympy.solvers.polysys import solve_generic
|
|
>>> from sympy.abc import x, y
|
|
>>> NewOption = Options((x, y), {'domain': 'ZZ'})
|
|
|
|
>>> a = Poly(x - y + 5, x, y, domain='ZZ')
|
|
>>> b = Poly(x + y - 3, x, y, domain='ZZ')
|
|
>>> solve_generic([a, b], NewOption)
|
|
[(-1, 4)]
|
|
|
|
>>> a = Poly(x - 2*y + 5, x, y, domain='ZZ')
|
|
>>> b = Poly(2*x - y - 3, x, y, domain='ZZ')
|
|
>>> solve_generic([a, b], NewOption)
|
|
[(11/3, 13/3)]
|
|
|
|
>>> a = Poly(x**2 + y, x, y, domain='ZZ')
|
|
>>> b = Poly(x + y*4, x, y, domain='ZZ')
|
|
>>> solve_generic([a, b], NewOption)
|
|
[(0, 0), (1/4, -1/16)]
|
|
|
|
>>> a = Poly(x**5 - x + y**3, x, y, domain='ZZ')
|
|
>>> b = Poly(y**2 - 1, x, y, domain='ZZ')
|
|
>>> solve_generic([a, b], NewOption, strict=True)
|
|
Traceback (most recent call last):
|
|
...
|
|
UnsolvableFactorError
|
|
|
|
"""
|
|
def _is_univariate(f):
|
|
"""Returns True if 'f' is univariate in its last variable. """
|
|
for monom in f.monoms():
|
|
if any(monom[:-1]):
|
|
return False
|
|
|
|
return True
|
|
|
|
def _subs_root(f, gen, zero):
|
|
"""Replace generator with a root so that the result is nice. """
|
|
p = f.as_expr({gen: zero})
|
|
|
|
if f.degree(gen) >= 2:
|
|
p = p.expand(deep=False)
|
|
|
|
return p
|
|
|
|
def _solve_reduced_system(system, gens, entry=False):
|
|
"""Recursively solves reduced polynomial systems. """
|
|
if len(system) == len(gens) == 1:
|
|
# the below line will produce UnsolvableFactorError if
|
|
# strict=True and the solution from `roots` is incomplete
|
|
zeros = list(roots(system[0], gens[-1], strict=strict).keys())
|
|
return [(zero,) for zero in zeros]
|
|
|
|
basis = groebner(system, gens, polys=True)
|
|
|
|
if len(basis) == 1 and basis[0].is_ground:
|
|
if not entry:
|
|
return []
|
|
else:
|
|
return None
|
|
|
|
univariate = list(filter(_is_univariate, basis))
|
|
|
|
if len(basis) < len(gens):
|
|
raise NotImplementedError(filldedent('''
|
|
only zero-dimensional systems supported
|
|
(finite number of solutions)
|
|
'''))
|
|
|
|
if len(univariate) == 1:
|
|
f = univariate.pop()
|
|
else:
|
|
raise NotImplementedError(filldedent('''
|
|
only zero-dimensional systems supported
|
|
(finite number of solutions)
|
|
'''))
|
|
|
|
gens = f.gens
|
|
gen = gens[-1]
|
|
|
|
# the below line will produce UnsolvableFactorError if
|
|
# strict=True and the solution from `roots` is incomplete
|
|
zeros = list(roots(f.ltrim(gen), strict=strict).keys())
|
|
|
|
if not zeros:
|
|
return []
|
|
|
|
if len(basis) == 1:
|
|
return [(zero,) for zero in zeros]
|
|
|
|
solutions = []
|
|
|
|
for zero in zeros:
|
|
new_system = []
|
|
new_gens = gens[:-1]
|
|
|
|
for b in basis[:-1]:
|
|
eq = _subs_root(b, gen, zero)
|
|
|
|
if eq is not S.Zero:
|
|
new_system.append(eq)
|
|
|
|
for solution in _solve_reduced_system(new_system, new_gens):
|
|
solutions.append(solution + (zero,))
|
|
|
|
if solutions and len(solutions[0]) != len(gens):
|
|
raise NotImplementedError(filldedent('''
|
|
only zero-dimensional systems supported
|
|
(finite number of solutions)
|
|
'''))
|
|
return solutions
|
|
|
|
try:
|
|
result = _solve_reduced_system(polys, opt.gens, entry=True)
|
|
except CoercionFailed:
|
|
raise NotImplementedError
|
|
|
|
if result is not None:
|
|
return sorted(result, key=default_sort_key)
|
|
|
|
|
|
def solve_triangulated(polys, *gens, **args):
|
|
"""
|
|
Solve a polynomial system using Gianni-Kalkbrenner algorithm.
|
|
|
|
The algorithm proceeds by computing one Groebner basis in the ground
|
|
domain and then by iteratively computing polynomial factorizations in
|
|
appropriately constructed algebraic extensions of the ground domain.
|
|
|
|
Parameters
|
|
==========
|
|
|
|
polys: a list/tuple/set
|
|
Listing all the equations that are needed to be solved
|
|
gens: generators
|
|
generators of the equations in polys for which we want the
|
|
solutions
|
|
args: Keyword arguments
|
|
Special options for solving the equations
|
|
|
|
Returns
|
|
=======
|
|
|
|
List[Tuple]
|
|
A List of tuples. Solutions for symbols that satisfy the
|
|
equations listed in polys
|
|
|
|
Examples
|
|
========
|
|
|
|
>>> from sympy import solve_triangulated
|
|
>>> from sympy.abc import x, y, z
|
|
|
|
>>> F = [x**2 + y + z - 1, x + y**2 + z - 1, x + y + z**2 - 1]
|
|
|
|
>>> solve_triangulated(F, x, y, z)
|
|
[(0, 0, 1), (0, 1, 0), (1, 0, 0)]
|
|
|
|
References
|
|
==========
|
|
|
|
1. Patrizia Gianni, Teo Mora, Algebraic Solution of System of
|
|
Polynomial Equations using Groebner Bases, AAECC-5 on Applied Algebra,
|
|
Algebraic Algorithms and Error-Correcting Codes, LNCS 356 247--257, 1989
|
|
|
|
"""
|
|
G = groebner(polys, gens, polys=True)
|
|
G = list(reversed(G))
|
|
|
|
domain = args.get('domain')
|
|
|
|
if domain is not None:
|
|
for i, g in enumerate(G):
|
|
G[i] = g.set_domain(domain)
|
|
|
|
f, G = G[0].ltrim(-1), G[1:]
|
|
dom = f.get_domain()
|
|
|
|
zeros = f.ground_roots()
|
|
solutions = set()
|
|
|
|
for zero in zeros:
|
|
solutions.add(((zero,), dom))
|
|
|
|
var_seq = reversed(gens[:-1])
|
|
vars_seq = postfixes(gens[1:])
|
|
|
|
for var, vars in zip(var_seq, vars_seq):
|
|
_solutions = set()
|
|
|
|
for values, dom in solutions:
|
|
H, mapping = [], list(zip(vars, values))
|
|
|
|
for g in G:
|
|
_vars = (var,) + vars
|
|
|
|
if g.has_only_gens(*_vars) and g.degree(var) != 0:
|
|
h = g.ltrim(var).eval(dict(mapping))
|
|
|
|
if g.degree(var) == h.degree():
|
|
H.append(h)
|
|
|
|
p = min(H, key=lambda h: h.degree())
|
|
zeros = p.ground_roots()
|
|
|
|
for zero in zeros:
|
|
if not zero.is_Rational:
|
|
dom_zero = dom.algebraic_field(zero)
|
|
else:
|
|
dom_zero = dom
|
|
|
|
_solutions.add(((zero,) + values, dom_zero))
|
|
|
|
solutions = _solutions
|
|
|
|
solutions = list(solutions)
|
|
|
|
for i, (solution, _) in enumerate(solutions):
|
|
solutions[i] = solution
|
|
|
|
return sorted(solutions, key=default_sort_key)
|