- From: ak.miller at auckland.ac.nz (Andrew Miller)
- Subject: [cellml-discussion] Identifying smaller subsystems of simultaneous equations in differential-algebraic models
- Date: Tue, 22 Apr 2008 16:35:13 +1200
Andrew Miller wrote:
>
Randall Britten wrote:
>
>> 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).
>
>>
>
> Hi Andrew
>
>
>
> If possible, please outline the algorithm that you have found, even though
>
> it is not efficient.
>
>
The most trivial algorithm is of course a simple depth first exhaustive
>
search. I believe this is what Justin already started implementing.
>
>
Firstly, I'll define the exact problem that I'm trying to solve in
>
formal language.
>
>
========
>
There are several ways to formulate the problem, but matrix notation
>
seems the cleanest.
>
>
Let A be an n*n matrix, where n is the number of equations in the model
>
(which haven't already been used), and is also the number of unknown
>
variables (which must be equal for the problem to be correctly constrained).
>
>
Let A_ij = 1 if the ith equation involves the jth unknown, and 0 otherwise.
>
>
The objective is to find the smallest possible non-empty set E such that
>
|E| = |V|, where V = {j where exists i in E such that A_ij = 1 }
>
=======
>
>
Algorithm findSmallestSystem(A, n):
>
for setSize from 1 through to n inclusive:
>
result <- findSystemOfSize(A, n, setSize, {}, 1)
>
if result is not failure:
>
return result
>
end
>
end
>
Not reached because there is always a system of size n.
>
end
>
>
Algorithm findSystemOfSize(A, n, addMembers, existingMembers,
>
lowestConsidered):
>
if (addMembers != 0):
>
result <- findSystemOfSize(A, n, addMembers - 1, existingMembers \
>
{i}, lowestConsidered + 1)
Of course, we don't have i here, I meant lowestConsidered
>
if result is not failure:
>
return result
>
end
>
result <- findSystemOfSize(A, n, addMembers, existingMembers,
>
lowestConsidered + 1)
>
if result is not failure:
>
return result
>
end
>
return failure because this branch is impossible.
>
end
>
>
V <- {}
>
for j from 1 through to n inclusive:
>
for i from 1 through to n inclusive:
>
if A_ij = 1:
>
V <- V union {j}
>
next iteration of the outer loop
>
end
>
end
>
end
>
>
if |V| = |existingMembers|:
>
return existingMembers
>
else
>
return failure
>
end
>
end
>
>
I am measuring the time complexity of this by the number of times we
>
check if A_ij = 1. In the worst case, which is that the only possible
>
system is the system of size n, we fail for systems of size 1 through to
>
n-1, and run to the end of the nth step before failing. This takes n^2
>
* (choose(n, 1) + choose(n, 2) + ... + choose(n, n)) = n^2 * (2^n - 1)
>
steps.
>
>
We can optimise certain cases. For example, if we can isolate disjoint
>
sets of variables and equations using a disjoint sets algorithm, we can
>
do better on this case (this won't improve the worst case, because there
>
is no guarantee of this being possible).
>
>
We can also adapt the above algorithm to be branch-and-bound by noting
>
that even before we get to the end of a branch, if |V| > |E|, then it is
>
never going to shrink as a result of adding more equations so we can
>
close off that branch.
>
>
Another possibility might be to implement a beam search based on some
>
kind of graph connectivity heuristic. However, it is not clear if this
>
would actually improve real world problems.
>
>
Also, it is worth noting that the above algorithm builds up the equation
>
set. We can also attack the problem from the other end (i.e. a divisive
>
algorithm) by starting from the set of all equations, which means we
>
know that |V| = |E|, and removing single equations or pairs of equations
>
and so on from |E| to see if this causes |V| to shrink by the
>
corresponding amount.
>
>
What I suspect will be the best improvement for average world models
I meant real world models.
>
would combine the disjoint sets separator with alternating between
>
divisive (shrink until we fail) and build-up (grow until we succeed)
>
algorithm attempts. This might work for real world problems if we limit
>
the number of equations we try to add or remove before just returning
>
the best divisive algorithm result even though it may be suboptimal.
>
However, whether this is actually useful is something we would need to
>
try with a number of models to find out; we may find that we still need
>
the metadata as a fallback approach for models where the heuristic is
>
not useful.
>
>
Best regards,
>
Andrew
>
>
> Regards,
>
> Randall
>
>
>
> _______________________________________________
>
> cellml-discussion mailing list
>
> cellml-discussion at cellml.org
>
> http://www.cellml.org/mailman/listinfo/cellml-discussion
>
>
_______________________________________________
>
cellml-discussion mailing list
>
cellml-discussion at cellml.org
>
http://www.cellml.org/mailman/listinfo/cellml-discussion
Archive powered by MHonArc 2.6.18.