|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
from collections import defaultdict |
|
|
|
from sympy.core.add import Add |
|
from sympy.core.mul import Mul |
|
from sympy.core.singleton import S |
|
|
|
from sympy.polys.constructor import construct_domain |
|
from sympy.polys.solvers import PolyNonlinearError |
|
|
|
from .sdm import ( |
|
SDM, |
|
sdm_irref, |
|
sdm_particular_from_rref, |
|
sdm_nullspace_from_rref |
|
) |
|
|
|
from sympy.utilities.misc import filldedent |
|
|
|
|
|
def _linsolve(eqs, syms): |
|
|
|
"""Solve a linear system of equations. |
|
|
|
Examples |
|
======== |
|
|
|
Solve a linear system with a unique solution: |
|
|
|
>>> from sympy import symbols, Eq |
|
>>> from sympy.polys.matrices.linsolve import _linsolve |
|
>>> x, y = symbols('x, y') |
|
>>> eqs = [Eq(x + y, 1), Eq(x - y, 2)] |
|
>>> _linsolve(eqs, [x, y]) |
|
{x: 3/2, y: -1/2} |
|
|
|
In the case of underdetermined systems the solution will be expressed in |
|
terms of the unknown symbols that are unconstrained: |
|
|
|
>>> _linsolve([Eq(x + y, 0)], [x, y]) |
|
{x: -y, y: y} |
|
|
|
""" |
|
|
|
nsyms = len(syms) |
|
|
|
|
|
eqsdict, const = _linear_eq_to_dict(eqs, syms) |
|
Aaug = sympy_dict_to_dm(eqsdict, const, syms) |
|
K = Aaug.domain |
|
|
|
|
|
|
|
|
|
if K.is_RealField or K.is_ComplexField: |
|
Aaug = Aaug.to_ddm().rref()[0].to_sdm() |
|
|
|
|
|
Arref, pivots, nzcols = sdm_irref(Aaug) |
|
|
|
|
|
if pivots and pivots[-1] == nsyms: |
|
return None |
|
|
|
|
|
P = sdm_particular_from_rref(Arref, nsyms+1, pivots) |
|
|
|
|
|
|
|
V, nonpivots = sdm_nullspace_from_rref(Arref, K.one, nsyms, pivots, nzcols) |
|
|
|
|
|
sol = defaultdict(list) |
|
for i, v in P.items(): |
|
sol[syms[i]].append(K.to_sympy(v)) |
|
for npi, Vi in zip(nonpivots, V): |
|
sym = syms[npi] |
|
for i, v in Vi.items(): |
|
sol[syms[i]].append(sym * K.to_sympy(v)) |
|
|
|
|
|
sol = {s: Add(*terms) for s, terms in sol.items()} |
|
|
|
|
|
zero = S.Zero |
|
for s in set(syms) - set(sol): |
|
sol[s] = zero |
|
|
|
|
|
return sol |
|
|
|
|
|
def sympy_dict_to_dm(eqs_coeffs, eqs_rhs, syms): |
|
"""Convert a system of dict equations to a sparse augmented matrix""" |
|
elems = set(eqs_rhs).union(*(e.values() for e in eqs_coeffs)) |
|
K, elems_K = construct_domain(elems, field=True, extension=True) |
|
elem_map = dict(zip(elems, elems_K)) |
|
neqs = len(eqs_coeffs) |
|
nsyms = len(syms) |
|
sym2index = dict(zip(syms, range(nsyms))) |
|
eqsdict = [] |
|
for eq, rhs in zip(eqs_coeffs, eqs_rhs): |
|
eqdict = {sym2index[s]: elem_map[c] for s, c in eq.items()} |
|
if rhs: |
|
eqdict[nsyms] = -elem_map[rhs] |
|
if eqdict: |
|
eqsdict.append(eqdict) |
|
sdm_aug = SDM(enumerate(eqsdict), (neqs, nsyms + 1), K) |
|
return sdm_aug |
|
|
|
|
|
def _linear_eq_to_dict(eqs, syms): |
|
"""Convert a system Expr/Eq equations into dict form, returning |
|
the coefficient dictionaries and a list of syms-independent terms |
|
from each expression in ``eqs```. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.matrices.linsolve import _linear_eq_to_dict |
|
>>> from sympy.abc import x |
|
>>> _linear_eq_to_dict([2*x + 3], {x}) |
|
([{x: 2}], [3]) |
|
""" |
|
coeffs = [] |
|
ind = [] |
|
symset = set(syms) |
|
for e in eqs: |
|
if e.is_Equality: |
|
coeff, terms = _lin_eq2dict(e.lhs, symset) |
|
cR, tR = _lin_eq2dict(e.rhs, symset) |
|
|
|
|
|
coeff -= cR |
|
for k, v in tR.items(): |
|
if k in terms: |
|
terms[k] -= v |
|
else: |
|
terms[k] = -v |
|
|
|
terms = {k: v for k, v in terms.items() if v} |
|
c, d = coeff, terms |
|
else: |
|
c, d = _lin_eq2dict(e, symset) |
|
coeffs.append(d) |
|
ind.append(c) |
|
return coeffs, ind |
|
|
|
|
|
def _lin_eq2dict(a, symset): |
|
"""return (c, d) where c is the sym-independent part of ``a`` and |
|
``d`` is an efficiently calculated dictionary mapping symbols to |
|
their coefficients. A PolyNonlinearError is raised if non-linearity |
|
is detected. |
|
|
|
The values in the dictionary will be non-zero. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.matrices.linsolve import _lin_eq2dict |
|
>>> from sympy.abc import x, y |
|
>>> _lin_eq2dict(x + 2*y + 3, {x, y}) |
|
(3, {x: 1, y: 2}) |
|
""" |
|
if a in symset: |
|
return S.Zero, {a: S.One} |
|
elif a.is_Add: |
|
terms_list = defaultdict(list) |
|
coeff_list = [] |
|
for ai in a.args: |
|
ci, ti = _lin_eq2dict(ai, symset) |
|
coeff_list.append(ci) |
|
for mij, cij in ti.items(): |
|
terms_list[mij].append(cij) |
|
coeff = Add(*coeff_list) |
|
terms = {sym: Add(*coeffs) for sym, coeffs in terms_list.items()} |
|
return coeff, terms |
|
elif a.is_Mul: |
|
terms = terms_coeff = None |
|
coeff_list = [] |
|
for ai in a.args: |
|
ci, ti = _lin_eq2dict(ai, symset) |
|
if not ti: |
|
coeff_list.append(ci) |
|
elif terms is None: |
|
terms = ti |
|
terms_coeff = ci |
|
else: |
|
|
|
|
|
raise PolyNonlinearError(filldedent(''' |
|
nonlinear cross-term: %s''' % a)) |
|
coeff = Mul._from_args(coeff_list) |
|
if terms is None: |
|
return coeff, {} |
|
else: |
|
terms = {sym: coeff * c for sym, c in terms.items()} |
|
return coeff * terms_coeff, terms |
|
elif not a.has_xfree(symset): |
|
return a, {} |
|
else: |
|
raise PolyNonlinearError('nonlinear term: %s' % a) |
|
|