Fast evaluation of expression with vector and matrices - Jep extensions

The com.singularsys.extensions.fastmatrix package provides a fast evaluation algorithm for evaluating equations using vectors and matrix defined over doubles. It is a more advanced version of the fastreal package which only works for scaler expressions.

The main class MrpEval first compiles a node into a sequence stored in a MrpCommandList. The same class also evaluates the sequence returning results which are a sub-type of MrpRes; these can then be converted to a double, arrays of double, a VectorI objects, or MatrixI objects as appropriate.

The name stands for Matrix Reverse Polish Evaluator and the command sequence uses an efficient reverse-Polish representation. This allows a very simple step by step evaluation. Evaluation using the package is about 10 times faster than a standard Jep implementation and three times faster the the next most efficient implementation. The package depends on the matrix package which in turn depends on the field package.

Setting up

To set up a Jep instance needs to initialised with support for matrices typically using the DoubleMatrixComponents

DoubleMatrixComponents dmc= new DoubleMatrixComponents();
StandardConfigurableParser cp = new StandardConfigurableParser();
Jep jep = new Jep(dmc,cp);
DimensionVisitor dimV = new DimensionVisitor(jep);

The StandardConfigurableParser is needed to allow some syntactical elements like the two dimensional element-of operation mat[1][2]. A DimensionVisitor class is needed to calculate the sizes of results at each step. Other methods of configuring the Jep instance are discussed in Matrix page.

Once those are created the main MrpEval instance can be constructed:

MrpEval mrpe = new MrpEval(jep);
or with an explicitly set MatrixFactory:
MatrixFactory mf = new DoubleMatrixFactory();
MrpEval mrpe = new MrpEval(jep,mf);

Compilation and evaluation

To compile an expression the dimensions of each node must first be calculated by using the DimensionVisitor. Next, the actual compilation takes place, which returns a list of commands MrpCommandList.

Node node = jep.parse("[[1,2],[3,4]] *[1,2]");
MrpCommandList com = mrpe.compile(node);

The evaluate method is then called with the list of commands.

MrpRes res = mrpe.evaluate(com);

Handling the results

The return type, MrpRes, will always need be converted to another, more useful type, and this needs to happen before the evaluate method is called again. A given MrpCommandList will always give the same size of result and the methods used will depend of the type of result, either scalers, vectors or matrices.

If its know the result will be scaler double then the res.doubleValue() can be called.

// Dot product of vectors
Node node2 = jep.parse("[1,2,3].[1,1,1]");
MrpCommandList com2 = mrpe.compile(node2);
MrpRes res2 = mrpe.evaluate(com2);
double dres = res2.doubleValue();

If the result is known to be a vector the result can be converted to an array of doubles using the res.toArrayVec() method

Node node3 = jep.parse("[1,2,3]+[1,1,1]");
MrpCommandList com3 = mrpe.compile(node3);
MrpRes res3 = mrpe.evaluate(com3);
double[] vres = res3.toArrayVec();
or it can be converted to a Double[] array
Double[] doubleVec = res3.toDoubleVec();

If the result is known to be a matrix the result can be converted to a two dimensional array of doubles using the res.toArrayMat() method

// Matrix multiplication
Node node4 = jep.parse("[[1,0],[0,-1]]*[[1,2],[3,4]]");
MrpCommandList com4 = mrpe.compile(node4);
MrpRes res4 = mrpe.evaluate(com4);
double[][] mres = res4.toArrayMat();
or to a Double[][] array
Double[][] doubleMat = res4.toDoubleMat();
The res.toFlatternedArray() method always produces a double[] array, converting matrices to row-major arrays and scalers to one dimensional arrays
double[] flatArray = res4.toFlatternedArray();

The result type can be determined using the res.getDimensions() which returns a Dimensions type. In particular res.getDimensions().order() methods will return 0 for scaler (Double) results, 1 for vectors and 2 for matrices. The size of vectors can be found using res.getDimensions().getFirstDim() and the number of rows and columns of a matrix by using res.getDimensions().getFirstDim() and res.getDimensions().getLastDim() respectively. The dimensions of the result is always fixed and can be found using MrpCommandList.getDimsOfResult() of the list of commands.

Results can also copied into a VectorI or MatrixI types. The The MrpEval class provides a methods provides two convenience methods to do this. For vectors

VectorI vec1 = mrpe.convertToVector(res3);

For matrices

MatrixI mat4 = mrpe.convertToMatrix(res4);
a third method MrpEval.convertResult(MrpRes) which converts the result into an appropriate type, either Double, VectorI or MatrixI and requires a cast. For example
MatrixI mat4a = (MatrixI) mrpe.convertResult(res4);

The results can also be copied VectorI or MatrixI objects created by a matrix factory.

// Gets the factory from the matrix components used above
MatrixFactoryI mfact = dmc.getMatrixFactory();
// For vectors
VectorI vec3 = mfact.zeroVec(res3.getDimensions());
// or 
VectorI vec4 = res3.copyToVec(mfact.zeroVec(res3.getDimensions()));
// For matrices
MatrixI mat4b = mfact.zeroMat(res4.getDimensions());
// or 
MatrixI mat4c = res4.copyToMat(mfact.zeroMat(res4.getDimensions()));
Result TypemethodFinal result
Summary of conversion routines, res is a MrpRes, mrpe is an MreEval, and mfact is a MatrixFactoryI.

Using Variables

The evaluator uses its own set of variables and the MrpVarRef type is used to identify each variable. A reference to the variable can be found with the getVarRef(String) and getVarRef(Variable) methods which look up the reference either by name or variable. Once found the reference can be used to get and set the variables.

// Create a vector valued variable
Variable uVar = jep.addVariable("u", mfact.newVector(1.0,2.0,2.0));
Node node5 = jep.parse("len = sqrt(u.u)");
MrpCommandList com5 = mrpe.compile(node5);
MrpVarRef uRef = mrpe.getVarRef(uVar);     // Look up by variable
MrpVarRef lenRef = mrpe.getVarRef("len");  // look up by name
MrpRes lenVal = mrpe.getVarValue(lenRef);  // get the value of the variable

The values of variables returned by getVarValue(MrpVarRef) is the same as returned by main evaluate method and can be converted in the same way. The value can be set by setVarValue(MrpVarRef,double) setVarValue(MrpVarRef,double...) setVarValue(MrpVarRef,VectorI) setVarValue(MrpVarRef,MatrixI)

// Set value using an array of doubles
mrpe.setVarValue(uRef, new double[]{2,3,6});  
lenVal = mrpe.getVarValue(lenRef);

// Set the value of a vector using varargs list of arguments
mrpe.setVarValue(uRef, 1.,4.,8.);
lenVal = mrpe.getVarValue(lenRef);

// Set value using a VectorI
VectorI vec2 = mfact.newVector(new Object[]{4.0,4.0,7.0});
mrpe.setVarValue(uRef, vec2);
lenVal = mrpe.getVarValue(lenRef);

The variables values used by the evaluator are not synchronized with the values of the normal Jep values. The methods updateFromJepVariables() and updateToJepVariables() can be used to copy the variables values from Jep to the evaluator and vica-versa.

// Create two jep variables
Variable xvar = jep.addVariable("x", 1.0);
Variable yvar = jep.addVariable("y", 0.0);

// calculates a variable based on another others

// On compilation the values of Jep variables are copied to mrpe values
String s = "y=x+10";
Node n = jep.parse(s);
MrpCommandList coms = mrpe.compile(n);
MrpVarRef xref = mrpe.getVarRef("x");
MrpRes xval = mrpe.getVarValue(xref);
assertEquals("Rpe value of x",1d, xval.doubleValue(),1e-9);
MrpVarRef yref = mrpe.getVarRef("y");
MrpRes yval = mrpe.getVarValue(yref);
assertEquals("Rpe value of y",0d, yval.doubleValue(),1e-9);

// evaluation will alter the y value
res = mrpe.evaluate(coms);
assertEquals(s,11.0, res.doubleValue(),1e-9);

// Set the rpe x variable and re-evaluate
mrpe.setVarValue(xref, 2.0);
res = mrpe.evaluate(coms);
assertEquals(s, 12.0, res.doubleValue(),1e-9);

// check the value of the rpe y variable
MrpRes val = mrpe.getVarValue(yref);
assertEquals("Rpe value of y", 12.0, val.doubleValue(),1e-9);

// Altering an rpe variable will not change the corresponding jep variable
assertEquals("Jep value of y", 0.0, yvar.getValue());

// Unless this method is called
assertEquals("Jep value of y", 12.0, (Double) yvar.getValue(),1e-9);

// set a variable value using Jep
// will not alter the rpe variable
res = mrpe.evaluate(coms);
assertEquals(s, 12.0, res.doubleValue(),1e-9);

// unless this method is called
res = mrpe.evaluate(coms);
assertEquals(s, 13.0, res.doubleValue(),1e-9);

Repeated evaluation

The evaluator really comes into its own when the same expression is re-evaluated multiple times with different values for the variables. The general pattern is compile,

String s2 = "3 x^2 + 4 x - 5";
// Parse, and compile 
Node n2 = jep.parse(s2);
MrpCommandList coms2 = mrpe.compile(n2);
// Get the variable reference
MrpVarRef xRef = mrpe.getVarRef("x");
for(double x=1.0;x<10;++x) {
// Set the value
	mrpe.setVarValue(xRef, x);
    // evaluate
    MrpRes res2b = mrpe.evaluate(coms2);

A more extensive example, calculating points on a sphere.

// Vector valued variable need to be specified so dimensions can be calculated
jep.addVariable("p0", mfact.newVector( 1.0, 2.0, 0.0));

// Parse, compile and evaluate an expression
String s3 = "p0+r*[cos(phi) sin(theta), sin(phi) sin(theta), cos(theta)]";
Node n3 = jep.parse(s3);
MrpCommandList coms3 = mrpe.compile(n3);

// references for variables
MrpVarRef thetaRef = mrpe.getVarRef("theta");
MrpVarRef phiRef = mrpe.getVarRef("phi");
MrpVarRef rRef = mrpe.getVarRef("r");
MrpVarRef p0Ref = mrpe.getVarRef("p0");

// Set the value for r
mrpe.setVarValue(rRef, 2.5);

// 3D array to store results
double results[][][] = new double[21][21][3];

for(int i=0;i<21;++i) {
    double theta = 0.0 + Math.PI * i / 20;
    mrpe.setVarValue(thetaRef, theta);
    for(int j=0;j<21;++j) {
        double phi = -Math.PI + 2 * Math.PI *j / 20;
        mrpe.setVarValue(phiRef, phi);
        MrpRes res5 = mrpe.evaluate(coms3);
        System.arraycopy(res5.toArrayVec(), 0,results[i][j], 0, 3);

MrpeEval in multiple threads

Since Jep 4.0/Extensions 2.1 the fastmatrix class MrpeEval has facilities to make it easier to use in multiple threads.

The getLightWeightInstance() returns a new instance which can be safely used for evaluation in multiple threads. This has copies of internal data so the evaluate(MrpCommandList) can be used with an already compiled command list, and set of MrpVarRef variable references.

A typical example which runs a repeated calculation in a separate thread would first compile the commands in the main thread and extract references to variables. A new MrpeEval instance, a list of commands, and set of references would then be passed to a new thread, where they can be evaluated.

public static void main(String args[]) {
    Jep jep = new Jep();
    DimensionVisitor dimV = new DimensionVisitor(jep);
    MrpEval mrpe = new MrpEval(jep, new DoubleMatrixFactory());

    try {
        String expression = "sqrt(1-x^2)";
        Node node = jep.parse(expression);
        MrpCommandList commands = mrpe.compile(node);
        MrpVarRef xref = mrpe.getVarRef("x");
        // Instance to use in thread
        final MrpEval rpe = (MrpEval) mrpe.getLightWeightInstance();

        // Create and run callable
        TrapesiumRule trap = 
            new TrapesiumRule(rpe,commands,xref, -1.0, 1.0, 1000);
        ExecutorService executorService = 
        Future<Double> future = executorService.submit(trap);
        double integral = future.get(); 
         System.out.println("Calculated pi = "+2*integral);
    } catch(Exception e) {

 * Use the TrapesiumRule to approximate the integral 
 * of a command.
static class TrapesiumRule implements Callable<Double> {
    MrpEval mrpe;            // local mrpe instance
    MrpCommandList command;  // command to execute
    MrpVarRef xref;          // reference to variable x
    double xlow,xhigh;       // bounds
    int steps;               // number of steps  
    public TrapesiumRule(MrpEval mrpe, MrpCommandList command, MrpVarRef xref, 
        double xlow, double xhigh, int steps) {
    	this.mrpe = mrpe;
    	this.command = command;
    	this.xref = xref;
    	this.xlow = xlow;
    	this.xhigh = xhigh;
    	this.steps = steps;

    public Double call() throws EvaluationException {
    	// calculate 1/2 h ( y0 + yn + 2 (y1 + ... yn-1) )
    	double h = (xhigh-xlow) / steps;
    	mrpe.setVarValue(xref, xlow);
    	double ylow = mrpe.evaluate(command).doubleValue();
    	mrpe.setVarValue(xref, xhigh);
    	double yhigh = mrpe.evaluate(command).doubleValue();
    	double sum = ylow + yhigh; 
    	for(int i=1;i<steps;++i) {
            double x = xlow + i * h;
            mrpe.setVarValue(xref, x);
            double y = mrpe.evaluate(command).doubleValue();
            sum += 2 * y;
    	return h * sum / 2;

Instances created in this way loose information about Jep variable, so the updateFromJepVariables(), updateToJepVariables(), getVariable(MrpVarRef ref), getVarRef(String name), getVarRef(Variable var), methods do not work. But variable values can be accessed using the getVarValue(MrpVarRef ref), and the various setVarValue(MrpVarRef ref,double), methods.

The instance also loose information about the matrix factory used to convert vector and matrix results. So the methods convertToVector(MrpRes ref), convertToMatrix(MrpRes ref), and convertResult(MrpRes ref), don't work. But you can use the MrpRes.copyToVec(VectorI), MrpRes.copyToMat(MatrixI) and other methods of MrpRes.

A second method getLightWeightInstance(Jep jep) uses the Variable and MatrixFactory information from the new Jep instance.

Jep jep = new Jep(new DoubleMatrixComponents());
DimensionVisitor dimV = new DimensionVisitor(jep);
MrpEval mrpe = new MrpEval(jep, new DoubleMatrixFactory());

// compile in parent instance    	
Variable u = jep.addVariable("u");
dimV.setVariableDimensions(u, Dimensions.TWO);
String s = "[1,2]+u";
Node n1 = jep.parse(s);
MrpCommandList com = mrpe.compile(n1);

// Create an instance using a lightweight jep instance	
ComponentSet cs = new LightWeightComponentSet(jep);
Jep lwj = new Jep(cs);
lwj.setComponent(new DoubleMatrixFactory()); // needed for convertToVector to work	
MrpEval eval = (MrpEval) mrpe.getLightWeightInstance(lwj);

// Get the reference using 
MrpVarRef u1ref = eval.getVarRef("u");
eval.setVarValue(u1ref, 3.0,4.0);
MrpRes res = eval.evaluate(com);
VectorI vec = eval.convertToVector(res); // requires a matrix factory

Implementation notes

The evaluator can be used with more than one expression. They can be compiled and evaluated in any order. There is one caveat if the dimensions of variables are change, for instance if the variable x changes from being a 2D vector to a 3D vector then the reset() method should be called. This clear all internal data are remove the variables.

Supported functions

All functions which take double arguments and return double results are supported, some functions have been optimized for speed these are: sin, cos, tan, sec, cosec, cot, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh, abs, exp, log, ln, sqrt, atan2, if.

Functions which implement com.singularsys.extensions.matrix.functions.MatrixFunctionI are supported. These can take vector of matrix arguments and return vector or matrix results. Example include MatrixDet, MatrixTrace and MatrixTrans which calculate the determinant, trace and transpose of a matrix.

Other functions which return strings or complex numbers will raise exceptions when used.


Both MrpEval and MrpCommandList implements Serializable so serialized versions of expressions can be stored or transmitted.

// set up and compile
DoubleMatrixComponents dmc = new DoubleMatrixComponents();
Jep jep = new Jep(dmc);
DimensionVisitor dv = new DimensionVisitor(jep);
MrpEval rpe = new MrpEval(jep);
String s = "1+2*x/4";
Node n = jep.parse(s);
MrpCommandList coms = rpe.compile(n);
MrpVarRef xref = rpe.getVarRef("x");

// Serialize
ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
ObjectOutputStream oos = new ObjectOutputStream(baos);
byte bytes[] = baos.toByteArray();

// Deserialize
ByteArrayInputStream bais = new ByteArrayInputStream(bytes); 
ObjectInputStream ois = new ObjectInputStream(bais);
MrpEval rpe2 = (MrpEval) ois.readObject();
MrpCommandList coms2 = (MrpCommandList) ois.readObject();
MrpVarRef xref2 = (MrpVarRef )ois.readObject();

// Evaluate
rpe2.setVarValue(xref2, 5.0);
MrpRes res2 = rpe2.evaluate(coms2);
double resval = res2.doubleValue();       

A Jep instance can also be serialised along with the mrpe instance. On deserialization the MreEval.init(Jep jep) methods should be called, to ensure the new instance has a valid jep instance and MatrixFactoryI (which is found from the jep instance).

Example applications