Spaces:
Sleeping
Sleeping
File size: 7,534 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 |
#
# sympy.polys.matrices.linsolve module
#
# This module defines the _linsolve function which is the internal workhorse
# used by linsolve. This computes the solution of a system of linear equations
# using the SDM sparse matrix implementation in sympy.polys.matrices.sdm. This
# is a replacement for solve_lin_sys in sympy.polys.solvers which is
# inefficient for large sparse systems due to the use of a PolyRing with many
# generators:
#
# https://github.com/sympy/sympy/issues/20857
#
# The implementation of _linsolve here handles:
#
# - Extracting the coefficients from the Expr/Eq input equations.
# - Constructing a domain and converting the coefficients to
# that domain.
# - Using the SDM.rref, SDM.nullspace etc methods to generate the full
# solution working with arithmetic only in the domain of the coefficients.
#
# The routines here are particularly designed to be efficient for large sparse
# systems of linear equations although as well as dense systems. It is
# possible that for some small dense systems solve_lin_sys which uses the
# dense matrix implementation DDM will be more efficient. With smaller systems
# though the bulk of the time is spent just preprocessing the inputs and the
# relative time spent in rref is too small to be noticeable.
#
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}
"""
# Number of unknowns (columns in the non-augmented matrix)
nsyms = len(syms)
# Convert to sparse augmented matrix (len(eqs) x (nsyms+1))
eqsdict, const = _linear_eq_to_dict(eqs, syms)
Aaug = sympy_dict_to_dm(eqsdict, const, syms)
K = Aaug.domain
# sdm_irref has issues with float matrices. This uses the ddm_rref()
# function. When sdm_rref() can handle float matrices reasonably this
# should be removed...
if K.is_RealField or K.is_ComplexField:
Aaug = Aaug.to_ddm().rref()[0].to_sdm()
# Compute reduced-row echelon form (RREF)
Arref, pivots, nzcols = sdm_irref(Aaug)
# No solution:
if pivots and pivots[-1] == nsyms:
return None
# Particular solution for non-homogeneous system:
P = sdm_particular_from_rref(Arref, nsyms+1, pivots)
# Nullspace - general solution to homogeneous system
# Note: using nsyms not nsyms+1 to ignore last column
V, nonpivots = sdm_nullspace_from_rref(Arref, K.one, nsyms, pivots, nzcols)
# Collect together terms from particular and nullspace:
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))
# Use a single call to Add for each term:
sol = {s: Add(*terms) for s, terms in sol.items()}
# Fill in the zeros:
zero = S.Zero
for s in set(syms) - set(sol):
sol[s] = zero
# All done!
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)
# there were no nonlinear errors so now
# cancellation is allowed
coeff -= cR
for k, v in tR.items():
if k in terms:
terms[k] -= v
else:
terms[k] = -v
# don't store coefficients of 0, however
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:
# since ti is not null and we already have
# a term, this is a cross term
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)
|