Friday, August 29, 2008


A Matrex project consists in a network of matrices and functions (let's forget about charts, presentations and timers).
They are connected together by the relations:
  • The matrix Mi is input parameter of the function Fj
  • The matrix Mi is output (result) of the function Fj
When a matrix changes its content, it fires the functions of which is input, which recalculate their output matrices, which in turn fires the functions of which are input and so on.

One peculiar property of this network is that it does not have loops. In mathematics it is representable as a simple graph.
This means that a matrix cannot be, directly or through other functions and matrices, input and output of the same function.

This is a good property, because it guarantees that, if the calculation of each single function terminates in a finite time, the calculation of the whole project terminates in a finite time.
In other words, the calculation of the project cannot contain an infinite loop.

In the upcoming version 1.3 I made an exception to this property, to solve the following problem:
I added a new solver function template to Matrex, that finds the minima of functions.
To use a solver, you need to pass to it the function you want to minimize.
In a programming language, you pass the function to mimimize to the solver function as a callback function (or a closure).

But how I did this in Matrex?
In Matrex, a programming language's function is equivalent to a network of functions and matrices, which, seen as a black box, has input and output matrices:

This block of functions and matrices can be equivalent to a callback function, with a trick:
  • the output of the callback block and the input of the caller must have one matrix in common
  • the output of the caller and the input of the callback block must have one matrix in common
The output matrix of the caller that is input matrix of the callback block is called callback matrix.

Here is a picture showing the concept:

In this way the caller, by
changing the content of one of its input matrices recalculates the callback block.
When the callback block executes, it updates the content of its output matrices. But one of those is a input matrix of the caller, therefore the caller is recalculated.

Caller and callback block execute each other until the caller decides to stop and does not change the content of the output matrix that it has in common with the callback block.

But when does the caller decide to stop? This depends by the caller code.

The solver I added In Matrex is Nelder Mead (sys.mathstat.optimization.neldermead), an implementation of the direct search algorithm, a simplex optimization algorithm (it uses the Apache Commons Math library).
At each step of the solving process the solver needs to call a function to calculate the cost of the current solution. The cost calculation function is our callback function.
The following picture shows the solver, the cost calculation function and their input and output matrices:

x is the callback matrix of the solver. It is both output matrix of the solver and input matrix of the cost calculation function.
When the content of x is changed, the cost calculation function is fired and it calculates the cost matrix, which is input of the solver.
The solver is executed and produces a new content for the x matrix, therefore firing the cost calculation function, until the cost is good enough to stop. At this point it stops changing the content of x and writes the final solution in the result matrix.

What I learned writing the Nelder Mead solver template is that one has to write the caller code carefully m
aking always sure that the mutual execution of caller and callback function stops at a certain point, in a way or the other. For example a solver must stop after a certain number of iterations, even if it does not converge.

Adding callbacks in Matrex required some changes in the code:
  • The callback matrix is special: adding a function that has a callback output matrix requires that this matrix is already in the project (it is the input matrix for the callback block).
  • Functions that have callback output matrices are not calculated when the project is loaded.
    Calculating them only once would leave them incomplete (for a solver this means to calculate only one step).
    Calculate them until they stop would be a risk. Better to leave to the user the responsability to calculate them.
Because of the complexity of this new feature, I introduce it in Matrex as experimental.

No comments: