Coverage for /usr/lib/python3/dist-packages/sympy/polys/agca/modules.py: 31%

1"""

2Computations with modules over polynomial rings.

4This module implements various classes that encapsulate groebner basis

5computations for modules. Most of them should not be instantiated by hand.

6Instead, use the constructing routines on objects you already have.

8For example, to construct a free module over ``QQ[x, y]``, call

9``QQ[x, y].free_module(rank)`` instead of the ``FreeModule`` constructor.

10In fact ``FreeModule`` is an abstract base class that should not be

11instantiated, the ``free_module`` method instead returns the implementing class

12``FreeModulePolyRing``.

14In general, the abstract base classes implement most functionality in terms of

15a few non-implemented methods. The concrete base classes supply only these

16non-implemented methods. They may also supply new implementations of the

17convenience methods, for example if there are faster algorithms available.

18"""

21from copy import copy

22from functools import reduce

24from sympy.polys.agca.ideals import Ideal

25from sympy.polys.domains.field import Field

26from sympy.polys.orderings import ProductOrder, monomial_key

27from sympy.polys.polyerrors import CoercionFailed

28from sympy.core.basic import _aresame

29from sympy.utilities.iterables import iterable

31# TODO

32# - module saturation

33# - module quotient/intersection for quotient rings

34# - free resoltutions / syzygies

35# - finding small/minimal generating sets

36# - ...

38##########################################################################

39## Abstract base classes #################################################

40##########################################################################

43class Module:

44 """

45 Abstract base class for modules.

47 Do not instantiate - use ring explicit constructors instead:

49 >>> from sympy import QQ

50 >>> from sympy.abc import x

51 >>> QQ.old_poly_ring(x).free_module(2)

52 QQ[x]**2

54 Attributes:

56 - dtype - type of elements

57 - ring - containing ring

59 Non-implemented methods:

61 - submodule

62 - quotient_module

63 - is_zero

64 - is_submodule

65 - multiply_ideal

67 The method convert likely needs to be changed in subclasses.

68 """

70 def __init__(self, ring):

71 self.ring = ring

73 def convert(self, elem, M=None):

74 """

75 Convert ``elem`` into internal representation of this module.

77 If ``M`` is not None, it should be a module containing it.

78 """

79 if not isinstance(elem, self.dtype):

80 raise CoercionFailed

81 return elem

83 def submodule(self, *gens):

84 """Generate a submodule."""

85 raise NotImplementedError

87 def quotient_module(self, other):

88 """Generate a quotient module."""

89 raise NotImplementedError

91 def __truediv__(self, e):

92 if not isinstance(e, Module):

93 e = self.submodule(*e)

94 return self.quotient_module(e)

96 def contains(self, elem):

97 """Return True if ``elem`` is an element of this module."""

98 try:

99 self.convert(elem)

100 return True

101 except CoercionFailed:

102 return False

103

104 def __contains__(self, elem):

105 return self.contains(elem)

106

107 def subset(self, other):

108 """

109 Returns True if ``other`` is is a subset of ``self``.

110

111 Examples

112 ========

113

114 >>> from sympy.abc import x

115 >>> from sympy import QQ

116 >>> F = QQ.old_poly_ring(x).free_module(2)

117 >>> F.subset([(1, x), (x, 2)])

118 True

119 >>> F.subset([(1/x, x), (x, 2)])

120 False

121 """

122 return all(self.contains(x) for x in other)

123

124 def __eq__(self, other):

125 return self.is_submodule(other) and other.is_submodule(self)

126

127 def __ne__(self, other):

128 return not (self == other)

129

130 def is_zero(self):

131 """Returns True if ``self`` is a zero module."""

132 raise NotImplementedError

133

134 def is_submodule(self, other):

135 """Returns True if ``other`` is a submodule of ``self``."""

136 raise NotImplementedError

137

138 def multiply_ideal(self, other):

139 """

140 Multiply ``self`` by the ideal ``other``.

141 """

142 raise NotImplementedError

143

144 def __mul__(self, e):

145 if not isinstance(e, Ideal):

146 try:

147 e = self.ring.ideal(e)

148 except (CoercionFailed, NotImplementedError):

149 return NotImplemented

150 return self.multiply_ideal(e)

151

152 __rmul__ = __mul__

153

154 def identity_hom(self):

155 """Return the identity homomorphism on ``self``."""

156 raise NotImplementedError

157

158

159class ModuleElement:

160 """

161 Base class for module element wrappers.

162

163 Use this class to wrap primitive data types as module elements. It stores

164 a reference to the containing module, and implements all the arithmetic

165 operators.

166

167 Attributes:

168

169 - module - containing module

170 - data - internal data

171

172 Methods that likely need change in subclasses:

173

174 - add

175 - mul

176 - div

177 - eq

178 """

179

180 def __init__(self, module, data):

181 self.module = module

182 self.data = data

183

184 def add(self, d1, d2):

185 """Add data ``d1`` and ``d2``."""

186 return d1 + d2

187

188 def mul(self, m, d):

189 """Multiply module data ``m`` by coefficient d."""

190 return m * d

191

192 def div(self, m, d):

193 """Divide module data ``m`` by coefficient d."""

194 return m / d

195

196 def eq(self, d1, d2):

197 """Return true if d1 and d2 represent the same element."""

198 return d1 == d2

199

200 def __add__(self, om):

201 if not isinstance(om, self.__class__) or om.module != self.module:

202 try:

203 om = self.module.convert(om)

204 except CoercionFailed:

205 return NotImplemented

206 return self.__class__(self.module, self.add(self.data, om.data))

207

208 __radd__ = __add__

209

210 def __neg__(self):

211 return self.__class__(self.module, self.mul(self.data,

212 self.module.ring.convert(-1)))

213

214 def __sub__(self, om):

215 if not isinstance(om, self.__class__) or om.module != self.module:

216 try:

217 om = self.module.convert(om)

218 except CoercionFailed:

219 return NotImplemented

220 return self.__add__(-om)

221

222 def __rsub__(self, om):

223 return (-self).__add__(om)

224

225 def __mul__(self, o):

226 if not isinstance(o, self.module.ring.dtype):

227 try:

228 o = self.module.ring.convert(o)

229 except CoercionFailed:

230 return NotImplemented

231 return self.__class__(self.module, self.mul(self.data, o))

232

233 __rmul__ = __mul__

234

235 def __truediv__(self, o):

236 if not isinstance(o, self.module.ring.dtype):

237 try:

238 o = self.module.ring.convert(o)

239 except CoercionFailed:

240 return NotImplemented

241 return self.__class__(self.module, self.div(self.data, o))

242

243 def __eq__(self, om):

244 if not isinstance(om, self.__class__) or om.module != self.module:

245 try:

246 om = self.module.convert(om)

247 except CoercionFailed:

248 return False

249 return self.eq(self.data, om.data)

250

251 def __ne__(self, om):

252 return not self == om

253

254##########################################################################

255## Free Modules ##########################################################

256##########################################################################

257

258

259class FreeModuleElement(ModuleElement):

260 """Element of a free module. Data stored as a tuple."""

261

262 def add(self, d1, d2):

263 return tuple(x + y for x, y in zip(d1, d2))

264

265 def mul(self, d, p):

266 return tuple(x * p for x in d)

267

268 def div(self, d, p):

269 return tuple(x / p for x in d)

270

271 def __repr__(self):

272 from sympy.printing.str import sstr

273 return '[' + ', '.join(sstr(x) for x in self.data) + ']'

274

275 def __iter__(self):

276 return self.data.__iter__()

277

278 def __getitem__(self, idx):

279 return self.data[idx]

280

281

282class FreeModule(Module):

283 """

284 Abstract base class for free modules.

285

286 Additional attributes:

287

288 - rank - rank of the free module

289

290 Non-implemented methods:

291

292 - submodule

293 """

294

295 dtype = FreeModuleElement

296

297 def __init__(self, ring, rank):

298 Module.__init__(self, ring)

299 self.rank = rank

300

301 def __repr__(self):

302 return repr(self.ring) + "**" + repr(self.rank)

303

304 def is_submodule(self, other):

305 """

306 Returns True if ``other`` is a submodule of ``self``.

307

308 Examples

309 ========

310

311 >>> from sympy.abc import x

312 >>> from sympy import QQ

313 >>> F = QQ.old_poly_ring(x).free_module(2)

314 >>> M = F.submodule([2, x])

315 >>> F.is_submodule(F)

316 True

317 >>> F.is_submodule(M)

318 True

319 >>> M.is_submodule(F)

320 False

321 """

322 if isinstance(other, SubModule):

323 return other.container == self

324 if isinstance(other, FreeModule):

325 return other.ring == self.ring and other.rank == self.rank

326 return False

327

328 def convert(self, elem, M=None):

329 """

330 Convert ``elem`` into the internal representation.

331

332 This method is called implicitly whenever computations involve elements

333 not in the internal representation.

334

335 Examples

336 ========

337

338 >>> from sympy.abc import x

339 >>> from sympy import QQ

340 >>> F = QQ.old_poly_ring(x).free_module(2)

341 >>> F.convert([1, 0])

342 [1, 0]

343 """

344 if isinstance(elem, FreeModuleElement):

345 if elem.module is self:

346 return elem

347 if elem.module.rank != self.rank:

348 raise CoercionFailed

349 return FreeModuleElement(self,

350 tuple(self.ring.convert(x, elem.module.ring) for x in elem.data))

351 elif iterable(elem):

352 tpl = tuple(self.ring.convert(x) for x in elem)

353 if len(tpl) != self.rank:

354 raise CoercionFailed

355 return FreeModuleElement(self, tpl)

356 elif _aresame(elem, 0):

357 return FreeModuleElement(self, (self.ring.convert(0),)*self.rank)

358 else:

359 raise CoercionFailed

360

361 def is_zero(self):

362 """

363 Returns True if ``self`` is a zero module.

364

365 (If, as this implementation assumes, the coefficient ring is not the

366 zero ring, then this is equivalent to the rank being zero.)

367

368 Examples

369 ========

370

371 >>> from sympy.abc import x

372 >>> from sympy import QQ

373 >>> QQ.old_poly_ring(x).free_module(0).is_zero()

374 True

375 >>> QQ.old_poly_ring(x).free_module(1).is_zero()

376 False

377 """

378 return self.rank == 0

379

380 def basis(self):

381 """

382 Return a set of basis elements.

383

384 Examples

385 ========

386

387 >>> from sympy.abc import x

388 >>> from sympy import QQ

389 >>> QQ.old_poly_ring(x).free_module(3).basis()

390 ([1, 0, 0], [0, 1, 0], [0, 0, 1])

391 """

392 from sympy.matrices import eye

393 M = eye(self.rank)

394 return tuple(self.convert(M.row(i)) for i in range(self.rank))

395

396 def quotient_module(self, submodule):

397 """

398 Return a quotient module.

399

400 Examples

401 ========

402

403 >>> from sympy.abc import x

404 >>> from sympy import QQ

405 >>> M = QQ.old_poly_ring(x).free_module(2)

406 >>> M.quotient_module(M.submodule([1, x], [x, 2]))

407 QQ[x]**2/<[1, x], [x, 2]>

408

409 Or more conicisely, using the overloaded division operator:

410

411 >>> QQ.old_poly_ring(x).free_module(2) / [[1, x], [x, 2]]

412 QQ[x]**2/<[1, x], [x, 2]>

413 """

414 return QuotientModule(self.ring, self, submodule)

415

416 def multiply_ideal(self, other):

417 """

418 Multiply ``self`` by the ideal ``other``.

419

420 Examples

421 ========

422

423 >>> from sympy.abc import x

424 >>> from sympy import QQ

425 >>> I = QQ.old_poly_ring(x).ideal(x)

426 >>> F = QQ.old_poly_ring(x).free_module(2)

427 >>> F.multiply_ideal(I)

428 <[x, 0], [0, x]>

429 """

430 return self.submodule(*self.basis()).multiply_ideal(other)

431

432 def identity_hom(self):

433 """

434 Return the identity homomorphism on ``self``.

435

436 Examples

437 ========

438

439 >>> from sympy.abc import x

440 >>> from sympy import QQ

441 >>> QQ.old_poly_ring(x).free_module(2).identity_hom()

442 Matrix([

443 [1, 0], : QQ[x]**2 -> QQ[x]**2

444 [0, 1]])

445 """

446 from sympy.polys.agca.homomorphisms import homomorphism

447 return homomorphism(self, self, self.basis())

448

449

450class FreeModulePolyRing(FreeModule):

451 """

452 Free module over a generalized polynomial ring.

453

454 Do not instantiate this, use the constructor method of the ring instead:

455

456 Examples

457 ========

458

459 >>> from sympy.abc import x

460 >>> from sympy import QQ

461 >>> F = QQ.old_poly_ring(x).free_module(3)

462 >>> F

463 QQ[x]**3

464 >>> F.contains([x, 1, 0])

465 True

466 >>> F.contains([1/x, 0, 1])

467 False

468 """

469

470 def __init__(self, ring, rank):

471 from sympy.polys.domains.old_polynomialring import PolynomialRingBase

472 FreeModule.__init__(self, ring, rank)

473 if not isinstance(ring, PolynomialRingBase):

474 raise NotImplementedError('This implementation only works over '

475 + 'polynomial rings, got %s' % ring)

476 if not isinstance(ring.dom, Field):

477 raise NotImplementedError('Ground domain must be a field, '

478 + 'got %s' % ring.dom)

479

480 def submodule(self, *gens, **opts):

481 """

482 Generate a submodule.

483

484 Examples

485 ========

486

487 >>> from sympy.abc import x, y

488 >>> from sympy import QQ

489 >>> M = QQ.old_poly_ring(x, y).free_module(2).submodule([x, x + y])

490 >>> M

491 <[x, x + y]>

492 >>> M.contains([2*x, 2*x + 2*y])

493 True

494 >>> M.contains([x, y])

495 False

496 """

497 return SubModulePolyRing(gens, self, **opts)

498

499

500class FreeModuleQuotientRing(FreeModule):

501 """

502 Free module over a quotient ring.

503

504 Do not instantiate this, use the constructor method of the ring instead:

505

506 Examples

507 ========

508

509 >>> from sympy.abc import x

510 >>> from sympy import QQ

511 >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(3)

512 >>> F

513 (QQ[x]/<x**2 + 1>)**3

514

515 Attributes

516

517 - quot - the quotient module `R^n / IR^n`, where `R/I` is our ring

518 """

519

520 def __init__(self, ring, rank):

521 from sympy.polys.domains.quotientring import QuotientRing

522 FreeModule.__init__(self, ring, rank)

523 if not isinstance(ring, QuotientRing):

524 raise NotImplementedError('This implementation only works over '

525 + 'quotient rings, got %s' % ring)

526 F = self.ring.ring.free_module(self.rank)

527 self.quot = F / (self.ring.base_ideal*F)

528

529 def __repr__(self):

530 return "(" + repr(self.ring) + ")" + "**" + repr(self.rank)

531

532 def submodule(self, *gens, **opts):

533 """

534 Generate a submodule.

535

536 Examples

537 ========

538

539 >>> from sympy.abc import x, y

540 >>> from sympy import QQ

541 >>> M = (QQ.old_poly_ring(x, y)/[x**2 - y**2]).free_module(2).submodule([x, x + y])

542 >>> M

543 <[x + <x**2 - y**2>, x + y + <x**2 - y**2>]>

544 >>> M.contains([y**2, x**2 + x*y])

545 True

546 >>> M.contains([x, y])

547 False

548 """

549 return SubModuleQuotientRing(gens, self, **opts)

550

551 def lift(self, elem):

552 """

553 Lift the element ``elem`` of self to the module self.quot.

554

555 Note that self.quot is the same set as self, just as an R-module

556 and not as an R/I-module, so this makes sense.

557

558 Examples

559 ========

560

561 >>> from sympy.abc import x

562 >>> from sympy import QQ

563 >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(2)

564 >>> e = F.convert([1, 0])

565 >>> e

566 [1 + <x**2 + 1>, 0 + <x**2 + 1>]

567 >>> L = F.quot

568 >>> l = F.lift(e)

569 >>> l

570 [1, 0] + <[x**2 + 1, 0], [0, x**2 + 1]>

571 >>> L.contains(l)

572 True

573 """

574 return self.quot.convert([x.data for x in elem])

575

576 def unlift(self, elem):

577 """

578 Push down an element of self.quot to self.

579

580 This undoes ``lift``.

581

582 Examples

583 ========

584

585 >>> from sympy.abc import x

586 >>> from sympy import QQ

587 >>> F = (QQ.old_poly_ring(x)/[x**2 + 1]).free_module(2)

588 >>> e = F.convert([1, 0])

589 >>> l = F.lift(e)

590 >>> e == l

591 False

592 >>> e == F.unlift(l)

593 True

594 """

595 return self.convert(elem.data)

596

597##########################################################################

598## Submodules and subquotients ###########################################

599##########################################################################

600

601

602class SubModule(Module):

603 """

604 Base class for submodules.

605

606 Attributes:

607

608 - container - containing module

609 - gens - generators (subset of containing module)

610 - rank - rank of containing module

611

612 Non-implemented methods:

613

614 - _contains

615 - _syzygies

616 - _in_terms_of_generators

617 - _intersect

618 - _module_quotient

619

620 Methods that likely need change in subclasses:

621

622 - reduce_element

623 """

624

625 def __init__(self, gens, container):

626 Module.__init__(self, container.ring)

627 self.gens = tuple(container.convert(x) for x in gens)

628 self.container = container

629 self.rank = container.rank

630 self.ring = container.ring

631 self.dtype = container.dtype

632

633 def __repr__(self):

634 return "<" + ", ".join(repr(x) for x in self.gens) + ">"

635

636 def _contains(self, other):

637 """Implementation of containment.

638 Other is guaranteed to be FreeModuleElement."""

639 raise NotImplementedError

640

641 def _syzygies(self):

642 """Implementation of syzygy computation wrt self generators."""

643 raise NotImplementedError

644

645 def _in_terms_of_generators(self, e):

646 """Implementation of expression in terms of generators."""

647 raise NotImplementedError

648

649 def convert(self, elem, M=None):

650 """

651 Convert ``elem`` into the internal represantition.

652

653 Mostly called implicitly.

654

655 Examples

656 ========

657

658 >>> from sympy.abc import x

659 >>> from sympy import QQ

660 >>> M = QQ.old_poly_ring(x).free_module(2).submodule([1, x])

661 >>> M.convert([2, 2*x])

662 [2, 2*x]

663 """

664 if isinstance(elem, self.container.dtype) and elem.module is self:

665 return elem

666 r = copy(self.container.convert(elem, M))

667 r.module = self

668 if not self._contains(r):

669 raise CoercionFailed

670 return r

671

672 def _intersect(self, other):

673 """Implementation of intersection.

674 Other is guaranteed to be a submodule of same free module."""

675 raise NotImplementedError

676

677 def _module_quotient(self, other):

678 """Implementation of quotient.

679 Other is guaranteed to be a submodule of same free module."""

680 raise NotImplementedError

681

682 def intersect(self, other, **options):

683 """

684 Returns the intersection of ``self`` with submodule ``other``.

685

686 Examples

687 ========

688

689 >>> from sympy.abc import x, y

690 >>> from sympy import QQ

691 >>> F = QQ.old_poly_ring(x, y).free_module(2)

692 >>> F.submodule([x, x]).intersect(F.submodule([y, y]))

693 <[x*y, x*y]>

694

695 Some implementation allow further options to be passed. Currently, to

696 only one implemented is ``relations=True``, in which case the function

697 will return a triple ``(res, rela, relb)``, where ``res`` is the

698 intersection module, and ``rela`` and ``relb`` are lists of coefficient

699 vectors, expressing the generators of ``res`` in terms of the

700 generators of ``self`` (``rela``) and ``other`` (``relb``).

701

702 >>> F.submodule([x, x]).intersect(F.submodule([y, y]), relations=True)

703 (<[x*y, x*y]>, [(y,)], [(x,)])

704

705 The above result says: the intersection module is generated by the

706 single element `(-xy, -xy) = -y (x, x) = -x (y, y)`, where

707 `(x, x)` and `(y, y)` respectively are the unique generators of

708 the two modules being intersected.

709 """

710 if not isinstance(other, SubModule):

711 raise TypeError('%s is not a SubModule' % other)

712 if other.container != self.container:

713 raise ValueError(

714 '%s is contained in a different free module' % other)

715 return self._intersect(other, **options)

716

717 def module_quotient(self, other, **options):

718 r"""

719 Returns the module quotient of ``self`` by submodule ``other``.

720

721 That is, if ``self`` is the module `M` and ``other`` is `N`, then

722 return the ideal `\{f \in R | fN \subset M\}`.

723

724 Examples

725 ========

726

727 >>> from sympy import QQ

728 >>> from sympy.abc import x, y

729 >>> F = QQ.old_poly_ring(x, y).free_module(2)

730 >>> S = F.submodule([x*y, x*y])

731 >>> T = F.submodule([x, x])

732 >>> S.module_quotient(T)

733 <y>

734

735 Some implementations allow further options to be passed. Currently, the

736 only one implemented is ``relations=True``, which may only be passed

737 if ``other`` is principal. In this case the function

738 will return a pair ``(res, rel)`` where ``res`` is the ideal, and

739 ``rel`` is a list of coefficient vectors, expressing the generators of

740 the ideal, multiplied by the generator of ``other`` in terms of

741 generators of ``self``.

742

743 >>> S.module_quotient(T, relations=True)

744 (<y>, [[1]])

745

746 This means that the quotient ideal is generated by the single element

747 `y`, and that `y (x, x) = 1 (xy, xy)`, `(x, x)` and `(xy, xy)` being

748 the generators of `T` and `S`, respectively.

749 """

750 if not isinstance(other, SubModule):

751 raise TypeError('%s is not a SubModule' % other)

752 if other.container != self.container:

753 raise ValueError(

754 '%s is contained in a different free module' % other)

755 return self._module_quotient(other, **options)

756

757 def union(self, other):

758 """

759 Returns the module generated by the union of ``self`` and ``other``.

760

761 Examples

762 ========

763

764 >>> from sympy.abc import x

765 >>> from sympy import QQ

766 >>> F = QQ.old_poly_ring(x).free_module(1)

767 >>> M = F.submodule([x**2 + x]) # <x(x+1)>

768 >>> N = F.submodule([x**2 - 1]) # <(x-1)(x+1)>

769 >>> M.union(N) == F.submodule([x+1])

770 True

771 """

772 if not isinstance(other, SubModule):

773 raise TypeError('%s is not a SubModule' % other)

774 if other.container != self.container:

775 raise ValueError(

776 '%s is contained in a different free module' % other)

777 return self.__class__(self.gens + other.gens, self.container)

778

779 def is_zero(self):

780 """

781 Return True if ``self`` is a zero module.

782

783 Examples

784 ========

785

786 >>> from sympy.abc import x

787 >>> from sympy import QQ

788 >>> F = QQ.old_poly_ring(x).free_module(2)

789 >>> F.submodule([x, 1]).is_zero()

790 False

791 >>> F.submodule([0, 0]).is_zero()

792 True

793 """

794 return all(x == 0 for x in self.gens)

795

796 def submodule(self, *gens):

797 """

798 Generate a submodule.

799

800 Examples

801 ========

802

803 >>> from sympy.abc import x

804 >>> from sympy import QQ

805 >>> M = QQ.old_poly_ring(x).free_module(2).submodule([x, 1])

806 >>> M.submodule([x**2, x])

807 <[x**2, x]>

808 """

809 if not self.subset(gens):

810 raise ValueError('%s not a subset of %s' % (gens, self))

811 return self.__class__(gens, self.container)

812

813 def is_full_module(self):

814 """

815 Return True if ``self`` is the entire free module.

816

817 Examples

818 ========

819

820 >>> from sympy.abc import x

821 >>> from sympy import QQ

822 >>> F = QQ.old_poly_ring(x).free_module(2)

823 >>> F.submodule([x, 1]).is_full_module()

824 False

825 >>> F.submodule([1, 1], [1, 2]).is_full_module()

826 True

827 """

828 return all(self.contains(x) for x in self.container.basis())

829

830 def is_submodule(self, other):

831 """

832 Returns True if ``other`` is a submodule of ``self``.

833

834 >>> from sympy.abc import x

835 >>> from sympy import QQ

836 >>> F = QQ.old_poly_ring(x).free_module(2)

837 >>> M = F.submodule([2, x])

838 >>> N = M.submodule([2*x, x**2])

839 >>> M.is_submodule(M)

840 True

841 >>> M.is_submodule(N)

842 True

843 >>> N.is_submodule(M)

844 False

845 """

846 if isinstance(other, SubModule):

847 return self.container == other.container and \

848 all(self.contains(x) for x in other.gens)

849 if isinstance(other, (FreeModule, QuotientModule)):

850 return self.container == other and self.is_full_module()

851 return False

852

853 def syzygy_module(self, **opts):

854 r"""

855 Compute the syzygy module of the generators of ``self``.

856

857 Suppose `M` is generated by `f_1, \ldots, f_n` over the ring

858 `R`. Consider the homomorphism `\phi: R^n \to M`, given by

859 sending `(r_1, \ldots, r_n) \to r_1 f_1 + \cdots + r_n f_n`.

860 The syzygy module is defined to be the kernel of `\phi`.

861

862 Examples

863 ========

864

865 The syzygy module is zero iff the generators generate freely a free

866 submodule:

867

868 >>> from sympy.abc import x, y

869 >>> from sympy import QQ

870 >>> QQ.old_poly_ring(x).free_module(2).submodule([1, 0], [1, 1]).syzygy_module().is_zero()

871 True

872

873 A slightly more interesting example:

874

875 >>> M = QQ.old_poly_ring(x, y).free_module(2).submodule([x, 2*x], [y, 2*y])

876 >>> S = QQ.old_poly_ring(x, y).free_module(2).submodule([y, -x])

877 >>> M.syzygy_module() == S

878 True

879 """

880 F = self.ring.free_module(len(self.gens))

881 # NOTE we filter out zero syzygies. This is for convenience of the

882 # _syzygies function and not meant to replace any real "generating set

883 # reduction" algorithm

884 return F.submodule(*[x for x in self._syzygies() if F.convert(x) != 0],

885 **opts)

886

887 def in_terms_of_generators(self, e):

888 """

889 Express element ``e`` of ``self`` in terms of the generators.

890

891 Examples

892 ========

893

894 >>> from sympy.abc import x

895 >>> from sympy import QQ

896 >>> F = QQ.old_poly_ring(x).free_module(2)

897 >>> M = F.submodule([1, 0], [1, 1])

898 >>> M.in_terms_of_generators([x, x**2])

899 [-x**2 + x, x**2]

900 """

901 try:

902 e = self.convert(e)

903 except CoercionFailed:

904 raise ValueError('%s is not an element of %s' % (e, self))

905 return self._in_terms_of_generators(e)

906

907 def reduce_element(self, x):

908 """

909 Reduce the element ``x`` of our ring modulo the ideal ``self``.

910

911 Here "reduce" has no specific meaning, it could return a unique normal

912 form, simplify the expression a bit, or just do nothing.

913 """

914 return x

915

916 def quotient_module(self, other, **opts):

917 """

918 Return a quotient module.

919

920 This is the same as taking a submodule of a quotient of the containing

921 module.

922

923 Examples

924 ========

925

926 >>> from sympy.abc import x

927 >>> from sympy import QQ

928 >>> F = QQ.old_poly_ring(x).free_module(2)

929 >>> S1 = F.submodule([x, 1])

930 >>> S2 = F.submodule([x**2, x])

931 >>> S1.quotient_module(S2)

932 <[x, 1] + <[x**2, x]>>

933

934 Or more coincisely, using the overloaded division operator:

935

936 >>> F.submodule([x, 1]) / [(x**2, x)]

937 <[x, 1] + <[x**2, x]>>

938 """

939 if not self.is_submodule(other):

940 raise ValueError('%s not a submodule of %s' % (other, self))

941 return SubQuotientModule(self.gens,

942 self.container.quotient_module(other), **opts)

943

944 def __add__(self, oth):

945 return self.container.quotient_module(self).convert(oth)

946

947 __radd__ = __add__

948

949 def multiply_ideal(self, I):

950 """

951 Multiply ``self`` by the ideal ``I``.

952

953 Examples

954 ========

955

956 >>> from sympy.abc import x

957 >>> from sympy import QQ

958 >>> I = QQ.old_poly_ring(x).ideal(x**2)

959 >>> M = QQ.old_poly_ring(x).free_module(2).submodule([1, 1])

960 >>> I*M

961 <[x**2, x**2]>

962 """

963 return self.submodule(*[x*g for [x] in I._module.gens for g in self.gens])

964

965 def inclusion_hom(self):

966 """

967 Return a homomorphism representing the inclusion map of ``self``.

968

969 That is, the natural map from ``self`` to ``self.container``.

970

971 Examples

972 ========

973

974 >>> from sympy.abc import x

975 >>> from sympy import QQ

976 >>> QQ.old_poly_ring(x).free_module(2).submodule([x, x]).inclusion_hom()

977 Matrix([

978 [1, 0], : <[x, x]> -> QQ[x]**2

979 [0, 1]])

980 """

981 return self.container.identity_hom().restrict_domain(self)

982

983 def identity_hom(self):

984 """

985 Return the identity homomorphism on ``self``.

986

987 Examples

988 ========

989

990 >>> from sympy.abc import x

991 >>> from sympy import QQ

992 >>> QQ.old_poly_ring(x).free_module(2).submodule([x, x]).identity_hom()

993 Matrix([

994 [1, 0], : <[x, x]> -> <[x, x]>

995 [0, 1]])

996 """

997 return self.container.identity_hom().restrict_domain(

998 self).restrict_codomain(self)

999

1000

1001class SubQuotientModule(SubModule):

1002 """

1003 Submodule of a quotient module.

1004

1005 Equivalently, quotient module of a submodule.

1006

1007 Do not instantiate this, instead use the submodule or quotient_module

1008 constructing methods:

1009

1010 >>> from sympy.abc import x

1011 >>> from sympy import QQ

1012 >>> F = QQ.old_poly_ring(x).free_module(2)

1013 >>> S = F.submodule([1, 0], [1, x])

1014 >>> Q = F/[(1, 0)]

1015 >>> S/[(1, 0)] == Q.submodule([5, x])

1016 True

1017

1018 Attributes:

1019

1020 - base - base module we are quotient of

1021 - killed_module - submodule used to form the quotient

1022 """

1023 def __init__(self, gens, container, **opts):

1024 SubModule.__init__(self, gens, container)

1025 self.killed_module = self.container.killed_module

1026 # XXX it is important for some code below that the generators of base

1027 # are in this particular order!

1028 self.base = self.container.base.submodule(

1029 *[x.data for x in self.gens], **opts).union(self.killed_module)

1030

1031 def _contains(self, elem):

1032 return self.base.contains(elem.data)

1033

1034 def _syzygies(self):

1035 # let N = self.killed_module be generated by e_1, ..., e_r

1036 # let F = self.base be generated by f_1, ..., f_s and e_1, ..., e_r

1037 # Then self = F/N.

1038 # Let phi: R**s --> self be the evident surjection.

1039 # Similarly psi: R**(s + r) --> F.

1040 # We need to find generators for ker(phi). Let chi: R**s --> F be the

1041 # evident lift of phi. For X in R**s, phi(X) = 0 iff chi(X) is

1042 # contained in N, iff there exists Y in R**r such that

1043 # psi(X, Y) = 0.

1044 # Hence if alpha: R**(s + r) --> R**s is the projection map, then

1045 # ker(phi) = alpha ker(psi).

1046 return [X[:len(self.gens)] for X in self.base._syzygies()]

1047

1048 def _in_terms_of_generators(self, e):

1049 return self.base._in_terms_of_generators(e.data)[:len(self.gens)]

1050

1051 def is_full_module(self):

1052 """

1053 Return True if ``self`` is the entire free module.

1054

1055 Examples

1056 ========

1057

1058 >>> from sympy.abc import x

1059 >>> from sympy import QQ

1060 >>> F = QQ.old_poly_ring(x).free_module(2)

1061 >>> F.submodule([x, 1]).is_full_module()

1062 False

1063 >>> F.submodule([1, 1], [1, 2]).is_full_module()

1064 True

1065 """

1066 return self.base.is_full_module()

1067

1068 def quotient_hom(self):

1069 """

1070 Return the quotient homomorphism to self.

1071

1072 That is, return the natural map from ``self.base`` to ``self``.

1073

1074 Examples

1075 ========

1076

1077 >>> from sympy.abc import x

1078 >>> from sympy import QQ

1079 >>> M = (QQ.old_poly_ring(x).free_module(2) / [(1, x)]).submodule([1, 0])

1080 >>> M.quotient_hom()

1081 Matrix([

1082 [1, 0], : <[1, 0], [1, x]> -> <[1, 0] + <[1, x]>, [1, x] + <[1, x]>>

1083 [0, 1]])

1084 """

1085 return self.base.identity_hom().quotient_codomain(self.killed_module)

1086

1087

1088_subs0 = lambda x: x[0]

1089_subs1 = lambda x: x[1:]

1090

1091

1092class ModuleOrder(ProductOrder):

1093 """A product monomial order with a zeroth term as module index."""

1094

1095 def __init__(self, o1, o2, TOP):

1096 if TOP:

1097 ProductOrder.__init__(self, (o2, _subs1), (o1, _subs0))

1098 else:

1099 ProductOrder.__init__(self, (o1, _subs0), (o2, _subs1))

1100

1101

1102class SubModulePolyRing(SubModule):

1103 """

1104 Submodule of a free module over a generalized polynomial ring.

1105

1106 Do not instantiate this, use the constructor method of FreeModule instead:

1107

1108 >>> from sympy.abc import x, y

1109 >>> from sympy import QQ

1110 >>> F = QQ.old_poly_ring(x, y).free_module(2)

1111 >>> F.submodule([x, y], [1, 0])

1112 <[x, y], [1, 0]>

1113

1114 Attributes:

1115

1116 - order - monomial order used

1117 """

1118

1119 #self._gb - cached groebner basis

1120 #self._gbe - cached groebner basis relations

1121

1122 def __init__(self, gens, container, order="lex", TOP=True):

1123 SubModule.__init__(self, gens, container)

1124 if not isinstance(container, FreeModulePolyRing):

1125 raise NotImplementedError('This implementation is for submodules of '

1126 + 'FreeModulePolyRing, got %s' % container)

1127 self.order = ModuleOrder(monomial_key(order), self.ring.order, TOP)

1128 self._gb = None

1129 self._gbe = None

1130

1131 def __eq__(self, other):

1132 if isinstance(other, SubModulePolyRing) and self.order != other.order:

1133 return False

1134 return SubModule.__eq__(self, other)

1135

1136 def _groebner(self, extended=False):

1137 """Returns a standard basis in sdm form."""

1138 from sympy.polys.distributedmodules import sdm_groebner, sdm_nf_mora

1139 if self._gbe is None and extended:

1140 gb, gbe = sdm_groebner(

1141 [self.ring._vector_to_sdm(x, self.order) for x in self.gens],

1142 sdm_nf_mora, self.order, self.ring.dom, extended=True)

1143 self._gb, self._gbe = tuple(gb), tuple(gbe)

1144 if self._gb is None:

1145 self._gb = tuple(sdm_groebner(

1146 [self.ring._vector_to_sdm(x, self.order) for x in self.gens],

1147 sdm_nf_mora, self.order, self.ring.dom))

1148 if extended:

1149 return self._gb, self._gbe

1150 else:

1151 return self._gb

1152

1153 def _groebner_vec(self, extended=False):

1154 """Returns a standard basis in element form."""

1155 if not extended:

1156 return [FreeModuleElement(self,

1157 tuple(self.ring._sdm_to_vector(x, self.rank)))

1158 for x in self._groebner()]

1159 gb, gbe = self._groebner(extended=True)

1160 return ([self.convert(self.ring._sdm_to_vector(x, self.rank))

1161 for x in gb],

1162 [self.ring._sdm_to_vector(x, len(self.gens)) for x in gbe])

1163

1164 def _contains(self, x):

1165 from sympy.polys.distributedmodules import sdm_zero, sdm_nf_mora

1166 return sdm_nf_mora(self.ring._vector_to_sdm(x, self.order),

1167 self._groebner(), self.order, self.ring.dom) == \

1168 sdm_zero()

1169

1170 def _syzygies(self):

1171 """Compute syzygies. See [SCA, algorithm 2.5.4]."""

1172 # NOTE if self.gens is a standard basis, this can be done more

1173 # efficiently using Schreyer's theorem

1174

1175 # First bullet point

1176 k = len(self.gens)

1177 r = self.rank

1178 zero = self.ring.convert(0)

1179 one = self.ring.convert(1)

1180 Rkr = self.ring.free_module(r + k)

1181 newgens = []

1182 for j, f in enumerate(self.gens):

1183 m = [0]*(r + k)

1184 for i, v in enumerate(f):

1185 m[i] = f[i]

1186 for i in range(k):

1187 m[r + i] = one if j == i else zero

1188 m = FreeModuleElement(Rkr, tuple(m))

1189 newgens.append(m)

1190 # Note: we need *descending* order on module index, and TOP=False to

1191 # get an elimination order

1192 F = Rkr.submodule(*newgens, order='ilex', TOP=False)

1193

1194 # Second bullet point: standard basis of F

1195 G = F._groebner_vec()

1196

1197 # Third bullet point: G0 = G intersect the new k components

1198 G0 = [x[r:] for x in G if all(y == zero for y in x[:r])]

1199

1200 # Fourth and fifth bullet points: we are done

1201 return G0

1202

1203 def _in_terms_of_generators(self, e):

1204 """Expression in terms of generators. See [SCA, 2.8.1]."""

1205 # NOTE: if gens is a standard basis, this can be done more efficiently

1206 M = self.ring.free_module(self.rank).submodule(*((e,) + self.gens))

1207 S = M.syzygy_module(

1208 order="ilex", TOP=False) # We want decreasing order!

1209 G = S._groebner_vec()

1210 # This list cannot not be empty since e is an element

1211 e = [x for x in G if self.ring.is_unit(x[0])][0]

1212 return [-x/e[0] for x in e[1:]]

1213

1214 def reduce_element(self, x, NF=None):

1215 """

1216 Reduce the element ``x`` of our container modulo ``self``.

1217

1218 This applies the normal form ``NF`` to ``x``. If ``NF`` is passed

1219 as none, the default Mora normal form is used (which is not unique!).

1220 """

1221 from sympy.polys.distributedmodules import sdm_nf_mora

1222 if NF is None:

1223 NF = sdm_nf_mora

1224 return self.container.convert(self.ring._sdm_to_vector(NF(

1225 self.ring._vector_to_sdm(x, self.order), self._groebner(),

1226 self.order, self.ring.dom),

1227 self.rank))

1228

1229 def _intersect(self, other, relations=False):

1230 # See: [SCA, section 2.8.2]

1231 fi = self.gens

1232 hi = other.gens

1233 r = self.rank

1234 ci = [[0]*(2*r) for _ in range(r)]

1235 for k in range(r):

1236 ci[k][k] = 1

1237 ci[k][r + k] = 1

1238 di = [list(f) + [0]*r for f in fi]

1239 ei = [[0]*r + list(h) for h in hi]

1240 syz = self.ring.free_module(2*r).submodule(*(ci + di + ei))._syzygies()

1241 nonzero = [x for x in syz if any(y != self.ring.zero for y in x[:r])]

1242 res = self.container.submodule(*([-y for y in x[:r]] for x in nonzero))

1243 reln1 = [x[r:r + len(fi)] for x in nonzero]

1244 reln2 = [x[r + len(fi):] for x in nonzero]

1245 if relations:

1246 return res, reln1, reln2

1247 return res

1248

1249 def _module_quotient(self, other, relations=False):

1250 # See: [SCA, section 2.8.4]

1251 if relations and len(other.gens) != 1:

1252 raise NotImplementedError

1253 if len(other.gens) == 0:

1254 return self.ring.ideal(1)

1255 elif len(other.gens) == 1:

1256 # We do some trickery. Let f be the (vector!) generating ``other``

1257 # and f1, .., fn be the (vectors) generating self.

1258 # Consider the submodule of R^{r+1} generated by (f, 1) and

1259 # {(fi, 0) | i}. Then the intersection with the last module

1260 # component yields the quotient.

1261 g1 = list(other.gens[0]) + [1]

1262 gi = [list(x) + [0] for x in self.gens]

1263 # NOTE: We *need* to use an elimination order

1264 M = self.ring.free_module(self.rank + 1).submodule(*([g1] + gi),

1265 order='ilex', TOP=False)

1266 if not relations:

1267 return self.ring.ideal(*[x[-1] for x in M._groebner_vec() if

1268 all(y == self.ring.zero for y in x[:-1])])

1269 else:

1270 G, R = M._groebner_vec(extended=True)

1271 indices = [i for i, x in enumerate(G) if

1272 all(y == self.ring.zero for y in x[:-1])]

1273 return (self.ring.ideal(*[G[i][-1] for i in indices]),

1274 [[-x for x in R[i][1:]] for i in indices])

1275 # For more generators, we use I : <h1, .., hn> = intersection of

1276 # {I : <hi> | i}

1277 # TODO this can be done more efficiently

1278 return reduce(lambda x, y: x.intersect(y),

1279 (self._module_quotient(self.container.submodule(x)) for x in other.gens))

1280

1281

1282class SubModuleQuotientRing(SubModule):

1283 """

1284 Class for submodules of free modules over quotient rings.

1285

1286 Do not instantiate this. Instead use the submodule methods.

1287

1288 >>> from sympy.abc import x, y

1289 >>> from sympy import QQ

1290 >>> M = (QQ.old_poly_ring(x, y)/[x**2 - y**2]).free_module(2).submodule([x, x + y])

1291 >>> M

1292 <[x + <x**2 - y**2>, x + y + <x**2 - y**2>]>

1293 >>> M.contains([y**2, x**2 + x*y])

1294 True

1295 >>> M.contains([x, y])

1296 False

1297

1298 Attributes:

1299

1300 - quot - the subquotient of `R^n/IR^n` generated by lifts of our generators

1301 """

1302

1303 def __init__(self, gens, container):

1304 SubModule.__init__(self, gens, container)

1305 self.quot = self.container.quot.submodule(

1306 *[self.container.lift(x) for x in self.gens])

1307

1308 def _contains(self, elem):

1309 return self.quot._contains(self.container.lift(elem))

1310

1311 def _syzygies(self):

1312 return [tuple(self.ring.convert(y, self.quot.ring) for y in x)

1313 for x in self.quot._syzygies()]

1314

1315 def _in_terms_of_generators(self, elem):

1316 return [self.ring.convert(x, self.quot.ring) for x in

1317 self.quot._in_terms_of_generators(self.container.lift(elem))]

1318

1319##########################################################################

1320## Quotient Modules ######################################################

1321##########################################################################

1322

1323

1324class QuotientModuleElement(ModuleElement):

1325 """Element of a quotient module."""

1326

1327 def eq(self, d1, d2):

1328 """Equality comparison."""

1329 return self.module.killed_module.contains(d1 - d2)

1330

1331 def __repr__(self):

1332 return repr(self.data) + " + " + repr(self.module.killed_module)

1333

1334

1335class QuotientModule(Module):

1336 """

1337 Class for quotient modules.

1338

1339 Do not instantiate this directly. For subquotients, see the

1340 SubQuotientModule class.

1341

1342 Attributes:

1343

1344 - base - the base module we are a quotient of

1345 - killed_module - the submodule used to form the quotient

1346 - rank of the base

1347 """

1348

1349 dtype = QuotientModuleElement

1350

1351 def __init__(self, ring, base, submodule):

1352 Module.__init__(self, ring)

1353 if not base.is_submodule(submodule):

1354 raise ValueError('%s is not a submodule of %s' % (submodule, base))

1355 self.base = base

1356 self.killed_module = submodule

1357 self.rank = base.rank

1358

1359 def __repr__(self):

1360 return repr(self.base) + "/" + repr(self.killed_module)

1361

1362 def is_zero(self):

1363 """

1364 Return True if ``self`` is a zero module.

1365

1366 This happens if and only if the base module is the same as the

1367 submodule being killed.

1368

1369 Examples

1370 ========

1371

1372 >>> from sympy.abc import x

1373 >>> from sympy import QQ

1374 >>> F = QQ.old_poly_ring(x).free_module(2)

1375 >>> (F/[(1, 0)]).is_zero()

1376 False

1377 >>> (F/[(1, 0), (0, 1)]).is_zero()

1378 True

1379 """

1380 return self.base == self.killed_module

1381

1382 def is_submodule(self, other):

1383 """

1384 Return True if ``other`` is a submodule of ``self``.

1385

1386 Examples

1387 ========

1388

1389 >>> from sympy.abc import x

1390 >>> from sympy import QQ

1391 >>> Q = QQ.old_poly_ring(x).free_module(2) / [(x, x)]

1392 >>> S = Q.submodule([1, 0])

1393 >>> Q.is_submodule(S)

1394 True

1395 >>> S.is_submodule(Q)

1396 False

1397 """

1398 if isinstance(other, QuotientModule):

1399 return self.killed_module == other.killed_module and \

1400 self.base.is_submodule(other.base)

1401 if isinstance(other, SubQuotientModule):

1402 return other.container == self

1403 return False

1404

1405 def submodule(self, *gens, **opts):

1406 """

1407 Generate a submodule.

1408

1409 This is the same as taking a quotient of a submodule of the base

1410 module.

1411

1412 Examples

1413 ========

1414

1415 >>> from sympy.abc import x

1416 >>> from sympy import QQ

1417 >>> Q = QQ.old_poly_ring(x).free_module(2) / [(x, x)]

1418 >>> Q.submodule([x, 0])

1419 <[x, 0] + <[x, x]>>

1420 """

1421 return SubQuotientModule(gens, self, **opts)

1422

1423 def convert(self, elem, M=None):

1424 """

1425 Convert ``elem`` into the internal representation.

1426

1427 This method is called implicitly whenever computations involve elements

1428 not in the internal representation.

1429

1430 Examples

1431 ========

1432

1433 >>> from sympy.abc import x

1434 >>> from sympy import QQ

1435 >>> F = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)]

1436 >>> F.convert([1, 0])

1437 [1, 0] + <[1, 2], [1, x]>

1438 """

1439 if isinstance(elem, QuotientModuleElement):

1440 if elem.module is self:

1441 return elem

1442 if self.killed_module.is_submodule(elem.module.killed_module):

1443 return QuotientModuleElement(self, self.base.convert(elem.data))

1444 raise CoercionFailed

1445 return QuotientModuleElement(self, self.base.convert(elem))

1446

1447 def identity_hom(self):

1448 """

1449 Return the identity homomorphism on ``self``.

1450

1451 Examples

1452 ========

1453

1454 >>> from sympy.abc import x

1455 >>> from sympy import QQ

1456 >>> M = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)]

1457 >>> M.identity_hom()

1458 Matrix([

1459 [1, 0], : QQ[x]**2/<[1, 2], [1, x]> -> QQ[x]**2/<[1, 2], [1, x]>

1460 [0, 1]])

1461 """

1462 return self.base.identity_hom().quotient_codomain(

1463 self.killed_module).quotient_domain(self.killed_module)

1464

1465 def quotient_hom(self):

1466 """

1467 Return the quotient homomorphism to ``self``.

1468

1469 That is, return a homomorphism representing the natural map from

1470 ``self.base`` to ``self``.

1471

1472 Examples

1473 ========

1474

1475 >>> from sympy.abc import x

1476 >>> from sympy import QQ

1477 >>> M = QQ.old_poly_ring(x).free_module(2) / [(1, 2), (1, x)]

1478 >>> M.quotient_hom()

1479 Matrix([

1480 [1, 0], : QQ[x]**2 -> QQ[x]**2/<[1, 2], [1, x]>

1481 [0, 1]])

1482 """

1483 return self.base.identity_hom().quotient_codomain(

1484 self.killed_module)