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]");
dimV.visit(node);
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]");
dimV.visit(node2);
MrpCommandList com2 = mrpe.compile(node2);
MrpRes res2 = mrpe.evaluate(com2);
double dres = res2.doubleValue();
System.out.println(dres);
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]");
dimV.visit(node3);
MrpCommandList com3 = mrpe.compile(node3);
MrpRes res3 = mrpe.evaluate(com3);
double[] vres = res3.toArrayVec();
System.out.println(Arrays.toString(vres));
or it can be converted to a
Double[] array
Double[] doubleVec = res3.toDoubleVec();
System.out.println(Arrays.toString(doubleVec));
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]]");
dimV.visit(node4);
MrpCommandList com4 = mrpe.compile(node4);
MrpRes res4 = mrpe.evaluate(com4);
double[][] mres = res4.toArrayMat();
System.out.println(Arrays.deepToString(mres));
or to a
Double[][] array
Double[][] doubleMat = res4.toDoubleMat();
System.out.println(Arrays.toString(doubleMat));
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();
System.out.println(Arrays.toString(flatArray));
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);
System.out.println(vec1);
For matrices
MatrixI mat4 = mrpe.convertToMatrix(res4);
System.out.println(mat4);
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());
res3.copyToVec(vec3);
// or
VectorI vec4 = res3.copyToVec(mfact.zeroVec(res3.getDimensions()));
// For matrices
MatrixI mat4b = mfact.zeroMat(res4.getDimensions());
res4.copyToMat(mat4b);
// or
MatrixI mat4c = res4.copyToMat(mfact.zeroMat(res4.getDimensions()));
| Result Type | method | Final result |
|---|
| scaler | res.doubleValue() | double |
| scaler | res.toFlatternedArray() | double[1] |
| vector | res.toArrayVec() | double[] |
| vector | res.toDoubleVec() | Double[] |
| vector | res.toFlatternedArray() | double[] |
| vector | mrpe.convertToVector(res) | VectorI |
| vector | mrpe.convertResult(res) | VectorI |
| vector | res.copyToVec(mfact.zeroVec(res.getDimentions())) | VectorI |
| matrix | res.toArrayMat() | double[][] |
| matrix | res.toDoubleMat() | Double[][] |
| matrix | res.toFlatternedArray() | double[] |
| matrix | mrpe.convertToMatrix(res) | MatrixI |
| matrix | mrpe.convertResult(res) | MatrixI |
| matrix | res.copyToMat(mfact.zeroMat(res.getDimentions())) | MatrixI |
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)");
dimV.visit(node5);
MrpCommandList com5 = mrpe.compile(node5);
MrpVarRef uRef = mrpe.getVarRef(uVar); // Look up by variable
MrpVarRef lenRef = mrpe.getVarRef("len"); // look up by name
mrpe.evaluate(com5);
MrpRes lenVal = mrpe.getVarValue(lenRef); // get the value of the variable
System.out.println(lenVal.doubleValue());
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});
mrpe.evaluate(com5);
lenVal = mrpe.getVarValue(lenRef);
// Set the value of a vector using varargs list of arguments
mrpe.setVarValue(uRef, 1.,4.,8.);
mrpe.evaluate(com5);
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);
mrpe.evaluate(com5);
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);
dimV.visit(n);
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
mrpe.updateToJepVariables();
assertEquals("Jep value of y", 12.0, (Double) yvar.getValue(),1e-9);
// set a variable value using Jep
// will not alter the rpe variable
jep.setVariable("x",3.0);
res = mrpe.evaluate(coms);
assertEquals(s, 12.0, res.doubleValue(),1e-9);
// unless this method is called
mrpe.updateFromJepVariables();
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);
dimV.visit(n2);
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);
System.out.println(res2b);
}
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);
dimV.visit(n3);
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);
}
}
System.out.println(Arrays.deepToString(results));
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);
dimV.visit(node);
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 =
Executors.newSingleThreadExecutor();
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) {
super();
this.mrpe = mrpe;
this.command = command;
this.xref = xref;
this.xlow = xlow;
this.xhigh = xhigh;
this.steps = steps;
}
@Override
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);
dimV.visit(n1);
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.
Serialization
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);
dv.visit(n);
MrpCommandList coms = rpe.compile(n);
MrpVarRef xref = rpe.getVarRef("x");
// Serialize
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
oos.writeObject(rpe);
oos.writeObject(coms);
oos.writeObject(xref);
oos.close();
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();
ois.close();
// 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
