[Math] Represent loop nests as multiple summations

algorithmsnotationsequences-and-series

This may be trivial but I would appreciate if someone could point me in the right direction here.. I am trying to express the number of instances in a loop nest in a general form. As a mathematical expression I would think this would be a multiple summation.

Example, loop nest:

for k in f_1(N):
   for j in f_2(k):
      for i in f_3(k,j):
         do something

Where $f_n(x)$ is a function that generates a set of indices for loop $n$ given input $x$. I would say that each loop nest function can take as input any of the outer indices (or not — it could be completely static/independent).. not quite sure if I've expressed that right.

From that I have: $\sum_{k}^{f_{1}(N)}\sum_{j}^{f_{2}(k)}|f_{3}(k,j)|$

Assuming this is correct, which it may not be!, how would one make this more generic to handle any number of loops say in the form with loop $l=1,…,N$?

Best Answer

The usual way to write this as a multiple sum would be

$$\sum_{k\in f_1(N)}\sum_{j\in f_2(k)}|f_3(k,j)|\;.$$

I don't think there's any generalization beyond that, since we don't know anything about the $f_i$.

Related Question