# Polynomial Simplification

The com.singularsys.extensions.polynomials package provides a more advanced simplification, expansion and comparison algorithms which works completely for polynomials and can handle some other expressions. It is not a substitute for a full Computer Algebra System.

The capabilities of the package are exposed by the XJep package, which make setting up easier.

The system works by converting expressions into a new representation based on polynomials (implemented using an interface PNodeI and classes like Monomial and Polynomial). Every polynomial expression has one canonical representation hence `x^2+3 x+2`, `2+3 x+x^2` and `x^2+5 x+2-2 x` are all converted to the same representation: `2+3 x+x^2`. Converting this representation back to a Jep expression effectively simplify the expression.

The main PolynomialCreator class contains most of the API. The `PNodeI createPoly(Node node)` method is used to convert Jep expressions to the PNodeI format and `Node toNode(PNodeI poly)` converts back to a simplified Jep expression. These two methods are combined in the `Node simplify(Node node)` method which simplifies an expression.

```Jep jep = new Jep();
PolynomialCreator pc = new PolynomialCreator(jep);
Node node=jep.parse("x^3 + x*x*x +x^2 -2 x^2 + 3 x - x - x - x + 1 + 0.5");
jep.println(node);
Node simp=pc.simplify(node);
jep.println(simp);
assertEquals("1.5-x^2.0+2.0*x^3.0",jep.toString(simp));
```

This simplification does not expand brackets which can be done with `Node expand(Node node)` methods.

```Node node2 = jep.parse("(x+3)*(x+2)");
Node expand=pc.expand(node2);
jep.println(expand);
assertEquals("6.0+5.0*x+x^2.0",jep.toString(expand));
```

### Comparison

The system imposes a total ordering on expression this allows two Jep expressions to be compared. The `equals(Node node1,Node node2)` methods compares the two expressions without expanding hence they must be symbolically equal apart from reordering of terms. `expandEquals(Node node1,Node node2)` expands the expressions first hence `x^2-1` and `(x+1)*(x-1)` would be equals.

```Node node3 = jep.parse("x^2-1");
Node node4 = jep.parse("-1+x^2");
Node node5 = jep.parse("(x+1)*(x-1)");
boolean eq = pc.equals(node3, node4);
assertTrue(eq);
boolean eq2 = pc.equals(node3, node5);
assertFalse(eq2);
boolean eq3 = pc.expandEquals(node3, node5);
assertTrue(eq3);
```

The `int compare(Node node1,Node node2)` methods using a total ordering. The ordering is complex but two algebraically different expressions are will give non zero results. Some of the rules for this ordering include: all polynomials of degree n in `x` are considered less than polynomials of degree n+1. Polynomials in x are considered less than polynomials in x and y which are less than polynomials in y.

```Node node6 = jep.parse("2 x - 1");
Node node7 = jep.parse("x^2 + 1");
int cmp = pc.compare(node6, node7);
assertEquals(-1,cmp);
```

### Extracting polynomial coefficients

The PolynomialCreator can also extract the coefficients of polynomials. The `toDoubleArray(PnodeI pnode,String s)` will find the coefficients of a PNodei representing a polynomial in a single variable.

```Node node8 = jep.parse("x^2-3x+4");
PNodeI pnode8 = pc.createPoly(node8);
double[] coeffs=pc.toDoubleArray(pnode8,"x");
// coeffs is [4.0,-3.0,1.0] -- the coefficients of x^0, x^1 and x^2
```

There are similar methods for polynomials in two and three variables.

```Node node9 = jep.parse("x^2+2 x y+3 x+4 y");
PNodeI pnode9 = pc.createPoly(node9);
double[][] coeffs8 = pc.toDoubleArray(pnode9, "x", "y");
// [[0.0, 4.0], [3.0, 2.0], [1.0, 0.0]]
// coeffs of [][x^0 y^0, x^0 y^1],[x^1 y^0, x^1 y^1],[x^2 y^0, x^2 y^1]]
```

Coefficients which are symbolic can be extracted using `toCoefficientArray(PNodeI poly,String var)` each entry is a type implementing `PNodeI`, `PConstant` for constants, `PVariable` for a simple variable and `Monomial` or `Polynomial` for more complex expressions. The value can be extracted from a `PConstant` and the name from a `PVariable` other types can be converted to a Jep `Node`.

```Node node10 = jep.parse("2 a x^2+ b x+3");
PNodeI pnode10 = pc.createPoly(node10);
PNodeI[] coeffs10 =  pc.toCoefficientArray(pnode10, "x");
System.out.println(Arrays.deepToString(coeffs10));
double constant = (double) ((PConstant) coeffs10).getValue();
String name = ((PVariable) coeffs10).getName();
Node res10 = coeffs10.toNode();
```

Coefficients of multivarient polynomials can be extracted with `toPNodeArray(PNodeI pnode, String... vars)` whose result needs to be cast to the appropriate array type.

```Node node11 = jep.parse("x^3+2 x y+3 x+4 y");
PNodeI pnode11 = pc.createPoly(node11);
PNodeI[][] coeffs11 = (PNodeI[][]) pc.toPNodeArray(pnode11, "x","y");
```

### The PNodeI type

The interface PNodeI represents a node in the tree. There are a number of classes which implement it.

• PConstant a constant number `2`
• PVariable a variable `x`
• Monomial a monomial like `2 x^2 y`
• Polynomial a polynomial is a sum of monomials `x^2+y^2`
• POperator an operator like `<=` which is not represents by a polynomial
• PFunction a function

The interface provides a number of methods for working with this internal structure including `Node toNode()`, `boolean equals(Object pnode)`, `int compareTo(PNodeI pnode)` and methods to perform basic operation on polynomials like addition and subtract. Some of the implementing types allow the names of variables or values of constants to be interrogated.

### Symbolic Operators

The Expand and Compare functions can be used in Jep expressions to perform symbolic expansion/comparison on expression using the preprocess mechanism in XJep.

### Use with other Fields

The package can be used with other fields. The `PolynomialCreator(Jep j,FieldI f)` constructor allows a specific field to be used. Note it assumed that the field has a commutative multiplication operation.

It can also be used as a component. The TreeUtils must also be specified.

```TreeUtils tu = new TreeUtils();
PolynomialCreator pc = new PolynomialCreator();
Jep jep = new Jep(pc,tu);
```

Or as a component with a field.

```NumberFactory nf = new BigDecNumberFactory(MathContext.DECIMAL128);
FieldI field = new BigDecimalField(MathContext.DECIMAL128);
FieldTreeUtils tu = new FieldTreeUtils(field);
FieldOperatorTable ot = new FieldOperatorTable(field);
PolynomialCreator pc = new PolynomialCreator(field);
Jep jep = new Jep(nf,ot,tu,pc);
```