Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

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?

in * Other Teaching Fields by (160 points)
edited by

1 Answer

+1 vote
 
Best answer

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 (170k points)
selected by
S-invariants

Related questions

0 votes
1 answer
asked Mar 19, 2023 in * Other Teaching Fields by lu (460 points)
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Jan 15, 2023 in * TF "Emb. Sys. and Rob." by lu (460 points)
0 votes
1 answer
Imprint | Privacy Policy
...