# Finding S-invariant

Hi,

I have a question regarding S-invariants in the MBES exam. Is finding s-invariant only trial and error or does it have a sure shot way? Could you please explain it? I am unable to figure it out.

For example, I believe that value (1,1,2,2,-1) is also an answer to the question from this exam. Is that right?

https://es.cs.uni-kl.de/teaching/mbes/exams/2021.04.06.mbes/2021.04.06.mbes.solutions.pdf

My understanding from the below statement is the matrix multiplication (Transpose of IM * · s vector = 0)should be zero and I think that solving in the way I am doing is time-consuming.

"for every cycle of k nodes, there is an S-invariant that is nonzero only for the buffers of the cycle and the buffer’s weights in the S-invariant are such that whenever one node fires, the inner product of the state vectors before and after firing with the S-invariant are the same "

And how do we determine the number of s-invariants for the DPN?

edited

+1 vote

To determine the S-invariants, you have to solve a linear equation system, i.e., transpose(M)*x=0 where M is the incidence matrix. The matrix of the mentioned exercise is

```     2  0  0 −1  0
-5  3  1  0  0
0 −6  0  5  4
0  0 −1  0 −2 ```

Every solution to the linear equation system is an s-invariant. You may proceed as follows using the Gaussian algorithm:

```    10  0  0 −5  0
-10  6  2  0  0
0 −6  0  5  4
0  0 −1  0 −2

10  0  0 −5  0
0  6  2 −5  0
0 −6  0  5  4
0  0 −1  0 −2

10  0  0 −5  0
0  6  2 −5  0
0  0  2  0  4
0  0 −1  0 −2

10  0  0 −5  0
0  6  2 −5  0
0  0  2  0  4
0  0 −2  0 −4

10  0  0 −5  0
0  6  2 −5  0
0  0  2  0  4
0  0  0  0  0

2  0  0 −1  0
0  6  0 −5 -4
0  0  2  0  4
0  0  0  0  0
```

From here you can get two solution vectors:

x1 = (3,5,0,6,0)    x2 = (0,2,-6,0,3)

Now, any linear combination of these two vectors is an S-invariant. Hence, there are infinitely many s-invariants, and all of them can be obtained, e.g., as a linear combination of the above two ones (or the ones mentioned in the example solution). If you compute x1-x2 = (3,3,6,6,-3), you find your vector multiplied by 3, so yes, your vector is also an s-invariant.

I don't see a simpler way than solving the linear equation system, albeit the cycles in the dataflow graph correspond with the s-invariants.
by (165k points)
selected by
S-invariants