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[0]).getValue(); 
String name = ((PVariable) coeffs10[1]).getName();
Node res10 = coeffs10[2].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.

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);
top

Examples