Static DPN Balance Equation system

Question

Hi,

in the MBES exam we are required to check whether DPN can be balanced.
For this we construct the incidence matrix J and check whether there exists x!=0 with Jx=0. So we check whether the kernel is nontrivial. Is there a trick to do this, as the Matrix is special, or are we supposed to do Gaussian Elimination in order to find a Basis for the kernel?

Also it is not clear to me how we can construct a schedule . Is there an algorithm to do this, or should we have a sharp look at the DPN?

For example in the following exam https://es.cs.uni-kl.de/teaching/mbes/exams/2018.04.03.mbes/2018.04.03.mbes.solutions.pdf .

Thank you !

Answer 1

There is indeed a trick to solve the linear equation system in linear time: Note that each row has two non-zero coefficients and we know that the rank is 1. Hence, we pick at first one coefficient which is our lambda, and determine the remaining ones as multiples of that one. We start with the other nonzero value of the same row, and continue with the others. It is in fact Gaussian elimination but applied in that special order.

For the schedule, you may simply apply ASAP scheduling, i.e., fire each node at the first time when it is ready until all firings required by the rate vector are consumed.

Comments

I think you mean rank is n-1. Thank you

---

Right! It is n-1