Hi all,

One issue which has recently been discussed amongst those of us working 
on CellML tools is the best way to handle models which require systems 
of equations to be solved efficiently. For example, if a model has 
equations like:

f1(a, b, c) = 0
f2(a, b, c) = 0
f3(a, c) = 0
f4(b, c, d, e) = 0
f5(b, d) = 0

We could simply solve the entire system in one go in a non-linear 
solver, over all five variables. However, this is not an efficient 
approach generally; we could have thousands of variables in a complex 
model, but only have one place in which we need to solve a system of two 
models. In this case, we could break the solution down to the following 
procedural steps:
Step 1) Solve the following system:
f1(a, b, c) = 0
f2(a, b, c) = 0
f3(a, c) = 0

to get a, b, and c.

Step 2) Solve the following equation:
f4(b, d) = 0
using the value of b obtained in the above step, to get d.

Step 3) Solve the following equation:
f4(b, c, d, e) = 0
using the known values of b, c, and d, to get e.

However, in general, I haven't been able to find an efficient 
(polynomial time) algorithm to compute this break-down (but I also 
haven't yet proved that the problem is NP-complete, so there may be a 
polynomial time solution even if P != NP).

We have several other approaches available to us, even if finding the 
exactly optimal break-down into systems is intractable:
  1) Use a heuristic algorithm which cannot always break down the 
system, but can for simple cases. For example, we could limit the size 
of systems allowed to control the complexity, or we could try some 
divisive algorithm which starts with the system which requires that all 
variables be solved, and tries to isolate individual equations or pairs 
or triples from it to see if this eliminates the need to solve for any 
variables, or perhaps tries both heuristics. We can also efficiently 
identify completely disconnected systems which don't share any common 
variables and solve them individually using a disjoint sets datatype.
  2) Require the model creator to provide us with this information. This 
is perhaps an unclean approach because certain kinds of changes to the 
model may change the types of systems that need to be solved. However, I 
understand it is essentially the status quo for most non-CellML 
modelling work which requires systems of equations to be expressed, so 
might still be a good last resort if we don't find a better solution (or 
even useful as a override for cases where the heuristic algorithm fails 
to find the optimal procedural steps).

I would be very grateful if anyone has feedback or suggestions on how to 
handle this issue.

Best regards,
cellml-discussion mailing list

Reply via email to