Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Homework 06 - Multivariate Polynomial Division Algorithm

Task

Implement the algorithm of multivariate polynomial division for more than one divisor (the examples and pseudo-algorithm of polynomial division can be found in lab slides from week 8 or lecture slides from week 9 and 10. )

Allowed libraries: sympy

Forbidden methods: sympy.polys.polytools.reduced

Create a function poly_div(f, divs, mo) for dividing the polynomial f by the list of polynomials divs using the specified monomial ordering mo.

Input/Output specifications for poly_div:

  1. f : Poly object
  2. divs : list of Poly objects
  3. mo : String. It can take the following values (according to SymPy documentation):
    1. “lex” - lexicographic order
    2. “grlex” - graded lexicographic order
    3. “grevlex” - graded reversed lexicographic order
  4. Return value : dictionary with 2 keys “q” and “r”, whose values are the list of quotient polynomials (list of Poly objects) and the remainder of the division (Poly object), respectively. That is,

$$ f = \sum_{i}q[i]\cdot divs[i] + r, \quad \mathrm{LT}(r) \text{ is not divisible by any of } \mathrm{LT}(divs[i]) \;\text{ or }\; r = 0. $$

For the explanation of how to work with Poly objects see Sympy documentation.

Upload

Upload a zip archive hw07.zip (via the course ware) containing the following files:

  1. hw07.py - python script containing the implemented function poly_div
courses/pkr/labs/hw06.txt · Last modified: 2022/11/06 17:29 by korotvik