Operating with potentials of discrete variables

A potential is a function that maps each configuration of a set of variables onto a real number. In the context of probabilistic graphical models, every family of probability distributions and every utility function is a potential, and the process of inference gives rise to new potentials. In principle, potentials defined on discrete variables might be represented as multidimensional arrays, but in practice they are implemented as linear arrays. In this paper we prove that in case of large potentials, the cost of retrieving their elements is significantly higher than the cost of multiplying, maximizing, or summing them. For this reason, we present an alternative algorithm that sequentially retrieves the elements of a potential implemented as a linear array without having to multiply the coordinates of each configuration by the offsets. We analyze theoretically and empirically the computational savings of this algorithm when applied to potential operations, such as marginalization, addition, multiplication, division, and conditioning. We also discuss the savings that can be obtained by multiplying several potentials at the same time, and by integrating the multiplication and marginalization of potentials.