Design an algorithm in python3 to solve a mathematics question involving polynomials.

The project is to design an algorithm to solve the following mathematics question involving polynomials, and write an implementation of that algorithm in python3. The algorithm strategy should be explained clearly either in code comments, or in a separate file in plain text or markdown.

## Input: an integer d, a list of polynomials F = [f_0, f_1, ... f_n], and another polynomial A.

The polynomials in F will have the following special properties:

1) The terms will have integer coefficients.

2) The polynomials are homogeneous. (For any individual polynomial in F, all the monomials in that polynomial will have the same degree. However, this does not necessarily mean all the polynomial in F will have the same degree.)

3) The monomials are multilinear. (This means a term may have multiple variables, but will never have a variable to a power higher than 1. For example x*y*z is multilinear, but a*b^2 is not.)

4) The monomials are unique between the polynomials in F.

The polynomial A will have the following properties:

1) It will only use variables already seen in F.

2) The terms will have integer coefficients.

3) The polynomial is homogeneous.

## Output:

Either

- a list of polynomials G = [g_0, g_1, ... g_n] of the same length as F, and another polynomial B.

Such that degree(A*B) <= d, and A*B = sum_i (f_i*g_i).

Some of the polynomials in G may be zero, but B must be a non-zero polynomial.

OR

- None, if there is no solution.

I would like this algorithm to be written in python3, and I suggest using sympy to deal with symbolic polynomials in python.

I'd like this done in 2 weeks, but am willing to extend this if requested.

Note: there are some computer algebra systems that can solve this problem via first calculating a full Groebner basis. If you do not know what that is, that is fine. I am mentioning this because, for the problems I am interested in, calculating a full Groebner basis first would not be feasible. If there is some way to work with a truncated Groebner basis calculated only up to degree d, that however would be acceptable. If you find an existing (freely available) library or computer science publication that largely already solves this problem while respecting the degree d limit, then that is perfectly fine by me -- I just ask that you please site the original inspiration so I can read more about it later. That being said, doing an initial search for existing algorithms may be worthwhile, as I do not know how to do such a search effectively.

Algoritmos Matemáticas Python

Nº del proyecto: #37704859

Sobre el proyecto