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, Andrew _______________________________________________ cellml-discussion mailing list cellml-discussion@cellml.org http://www.cellml.org/mailman/listinfo/cellml-discussion
