Chronological Thread 

< Chronological >      < Thread >

---

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] Identifying smaller subsystems of simultaneous equations in differential-algebraic models, Andrew Miller, 04/16/2008
  • [cellml-discussion] Identifying smaller subsystems of simultaneous equations in differential-algebraic models, Randall Britten, 04/22/2008
    • [cellml-discussion] Identifying smaller subsystems of simultaneous equations in differential-algebraic models, Andrew Miller, 04/22/2008
      • [cellml-discussion] Identifying smaller subsystems of simultaneous equations in differential-algebraic models, Andrew Miller, 04/22/2008

---

Archive powered by MHonArc 2.6.18.