Patent ID: 8890862

Claim:
A method to be carried out by a processing device for efficiently performing a message passing algorithm encoded in software executable by said processing device and stored in a memory of said computer device, the method causing the processing device to preform steps comprising: for each node i in the message passing algorithm, iteratively: for each node j linked to node i: combine incoming messages to form an intermediate vector I, determining an output message vector M by: considering an auxiliary seed vector S; a pairwise function r=d(x,y), where r, x, y are real numbers; and an index distance Δ≧2^floor(log 2(N)), N being the length of message vector M and the seed vector S, initializing S as S(m)=m for each element m of vector S, for each index p of the vector I and while Δ>0,computing in parallel, by: considering the set of all indices within distance Δ from given index p, augmented by index p, for every index k belonging to this set, computing its distance from p using the function: d(p,k)+I(S(k)) in order to determine the minimum distance, computing S(p)=S(n), n being the index corresponding to this minimum distance, and computing Δ=floor(Δ/2), determining the message vector M by computing M(m)=I(S(m))+d(m,S(m)) for each element m of vector M, communicating the vector M to node i.