Ley distributiva generalizada

La ley distributiva generalizada (GDL) es una generalización de la propiedad distributiva que da lugar a un algoritmo general de paso de mensajes . ^{[ 1 ]} Es una síntesis del trabajo de numerosos autores en las comunidades de teoría de la información , comunicaciones digitales , procesamiento de señales , estadística e inteligencia artificial . La ley y el algoritmo fueron presentados en un semitutorial de Srinivas M. Aji y Robert J. McEliece con el mismo título. ^{[ 1 ]}

"La ley distributiva en matemáticas es la ley que relaciona las operaciones de multiplicación y suma, expresada simbólicamente,${\displaystyle a*(b+c)=a*b+a*c}$; es decir, el factor monomio${\displaystyle a}$se distribuye, o se aplica por separado, a cada término del factor binomial${\displaystyle b+c}$, dando como resultado el producto${\displaystyle a*b+a*c}$" – Britannica. ^{[ 2 ]}

Como se puede observar en la definición, la aplicación de la ley distributiva a una expresión aritmética reduce el número de operaciones en ella. En el ejemplo anterior, el número total de operaciones se redujo de tres (dos multiplicaciones y una suma en${\displaystyle a*b+a*c}$) a dos (una multiplicación y una suma en${\displaystyle a*(b+c)}$La generalización de la ley distributiva conduce a una gran familia de algoritmos rápidos . Esto incluye la FFT y el algoritmo de Viterbi .

Esto se explica de forma más formal en el siguiente ejemplo:

${\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _ {c,d,e\in A}f(a,\,c,\,b)\,g(a,\,d,\,e)}$dónde${\displaystyle f(\cdot )}$y${\displaystyle g(\cdot )}$son funciones de valor real,${\displaystyle a,b,c,d,e\in A}$y${\displaystyle |A|=q}$(decir)

Aquí estamos "marginalizando" las variables independientes (${\displaystyle c}$,${\displaystyle d}$, y${\displaystyle e}$) para obtener el resultado. Cuando calculamos la complejidad computacional, podemos ver que para cada${\displaystyle q^{2}}$pares de${\displaystyle (a,b)}$, hay${\displaystyle q^{3}}$términos debido al triplete${\displaystyle (c,d,e)}$que necesita participar en la evaluación de${\displaystyle \alpha (a,\,b)}$donde cada paso tiene una suma y una multiplicación. Por lo tanto, el número total de cálculos necesarios es${\displaystyle 2\cdot q^{2}\cdot q^{3}=2q^{5}}$Por lo tanto, la complejidad asintótica de la función anterior es${\displaystyle O(n^{5})}$.

Si aplicamos la ley distributiva al lado derecho de la ecuación, obtenemos lo siguiente:

${\displaystyle \alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)\cdot \sum _{d,\,e\in A}g(a,\,d,\,e)}$

Esto implica que${\displaystyle \alpha (a,\,b)}$puede describirse como un producto${\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)}$dónde${\displaystyle \alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)}$y${\displaystyle \alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)}$

Ahora, cuando calculamos la complejidad computacional, podemos ver que hay${\displaystyle q^{3}}$adiciones en${\displaystyle \alpha _{1}(a,\,b)}$y${\displaystyle \alpha _{2}(a)}$cada uno y hay${\displaystyle q^{2}}$multiplicaciones cuando estamos usando el producto${\displaystyle \alpha _{1}(a,\,b)\cdot \alpha _{2}(a)}$evaluar${\displaystyle \alpha (a,\,b)}$Por lo tanto, el número total de cálculos necesarios es${\displaystyle q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}}$. Por lo tanto, la complejidad asintótica del cálculo${\displaystyle \alpha (a,b)}$se reduce a${\displaystyle O(n^{3})}$de${\displaystyle O(n^{5})}$Esto demuestra, mediante un ejemplo, que la aplicación de la ley distributiva reduce la complejidad computacional, lo cual es una de las buenas características de un "algoritmo rápido".

Algunos de los problemas que se resolvieron utilizando la ley distributiva se pueden agrupar de la siguiente manera:

1. Algoritmos de decodificación: Gallager utilizó un algoritmo similar a GDL para decodificar códigos de paridad de baja densidad. Basándose en el trabajo de Gallager, Tanner introdujo el grafo de Tanner y lo expresó mediante el método de paso de mensajes. El grafo de Tanner también ayudó a explicar el algoritmo de Viterbi . Forney observó que la decodificación de máxima verosimilitud de códigos convolucionales de Viterbi también utilizaba algoritmos de generalidad similar a GDL.
2. Algoritmo de avance-retroceso : El algoritmo de avance-retroceso ayudó como algoritmo para rastrear los estados en la cadena de Markov . Y este también fue utilizado por el algoritmo de generalidad GDL.
3. Inteligencia artificial : La noción de árboles de unión se ha utilizado para resolver muchos problemas en IA. Asimismo, el concepto de eliminación de cubos ha utilizado muchos de estos conceptos.

La marginalización de una función producto (MPF, por sus siglas en inglés) es un problema computacional general que, como caso particular, incluye muchos problemas clásicos, como el cálculo de la transformada discreta de Hadamard , la decodificación de máxima verosimilitud de un código lineal sobre un canal sin memoria y la multiplicación de cadenas de matrices . La potencia del GDL reside en que se aplica a situaciones en las que se generalizan las sumas y las multiplicaciones.

Un semianillo conmutativo es un buen marco para explicar este comportamiento. Se define sobre un conjunto${\displaystyle K}$con operadores "${\displaystyle +}$" y "${\displaystyle .}$" dónde${\displaystyle (K,\,+)}$y${\displaystyle (K,\,.)}$son monoides conmutativos y se cumple la ley distributiva.

Dejar${\displaystyle p_{1},\ldots ,p_{n}}$sean variables tales que${\displaystyle p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}}$dónde${\displaystyle A}$es un conjunto finito y${\displaystyle |A_{i}|=q_{i}}$. Aquí${\displaystyle i=1,\ldots ,n}$. Si${\displaystyle S=\{i_{1},\ldots ,i_{r}\}}$y${\displaystyle S\,\subset \{1,\ldots ,n\}}$, dejar ${\displaystyle A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}}$,${\displaystyle p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})}$, ${\displaystyle q_{S}=|A_{S}|}$, ${\displaystyle \mathbf {A} =A_{1}\times \cdots \times A_{n}}$, y ${\displaystyle \mathbf {p} =\{p_{1},\ldots ,p_{n}\}}$

Dejar${\displaystyle S=\{S_{j}\}_{j=1}^{M}}$dónde${\displaystyle S_{j}\subset \{1,...\,,n\}}$. Supongamos que una función se define como${\displaystyle \alpha _{i}:A_{S_{i}}\rightarrow R}$, dónde${\displaystyle R}$es un semianillo conmutativo . Además,${\displaystyle p_{S_{i}}}$se denominan los dominios locales y${\displaystyle \alpha _{i}}$como los núcleos locales .

Ahora el kernel global${\displaystyle \beta$ :\mathbf {A} \rightarrow R} se define como:${\displaystyle \beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})}$

Definición del problema MPF : Para uno o más índices${\displaystyle i=1,...\,,M}$, calcular una tabla de los valores de${\displaystyle S_{i}}$- marginación del núcleo global${\displaystyle \beta }$, que es la función${\displaystyle \beta _{i}:A_{S_{i}}\rightarrow R}$definido como${\displaystyle \beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)}$

Aquí${\displaystyle S_{i}^{c}}$es el complemento de${\displaystyle S_{i}}$con respecto a${\displaystyle \mathbf {\{} 1,...\,,n\}}$y el${\displaystyle \beta _{i}(p_{S_{i}})}$se llama el${\displaystyle i^{th}}$función objetivo , o la función objetivo en${\displaystyle S_{i}}$. Se puede observar que el cálculo de la${\displaystyle i^{th}}$La función objetivo de la manera obvia necesita${\displaystyle Mq_{1}q_{2}q_{3}\cdots q_{n}}$operaciones. Esto se debe a que hay${\displaystyle q_{1}q_{2}\cdots q_{n}}$adiciones y${\displaystyle (M-1)q_{1}q_{2}...q_{n}}$multiplicaciones necesarias en el cálculo de la${\displaystyle i^{\text{th}}}$función objetivo. El algoritmo GDL, que se explica en la siguiente sección, puede reducir esta complejidad computacional.

El siguiente es un ejemplo del problema MPF.

Dejar${\displaystyle p_{1},\,p_{2},\,p_{3},\,p_{4},}$y${\displaystyle p_{5}}$sean variables tales que${\displaystyle p_{1}\in A_{1},p_{2}\in A_{2},p_{3}\in A_{3},p_{4}\in A_{4},}$y${\displaystyle p_{5}\in A_{5}}$. Aquí${\displaystyle M=4}$y${\displaystyle S=\{\{1,2,5\},\{2,4\},\{1,4\},\{2\}\}}$Las funciones dadas que utilizan estas variables son:${\displaystyle f(p_{1},p_{2},p_{5})}$y${\displaystyle g(p_{2},p_{4})}$y necesitamos calcular${\displaystyle \alpha (p_{1},\,p_{4})}$y${\displaystyle \beta (p_{2})}$definido como:

${\displaystyle \alpha (p_{1},\,p_{4})=\displaystyle \sum \limits _{p_{2}\in A_{2},\,p_{3}\in A_{3},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}$

${\displaystyle \beta (p_{2})=\sum \limits _{p_{1}\in A_{1},\,p_{3}\in A_{3},\,p_{4}\in A_{4},\,p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}$

Aquí, los dominios locales y los núcleos locales se definen de la siguiente manera:

dónde${\displaystyle \alpha (p_{1},p_{4})}$es el${\displaystyle 3^{rd}}$función objetivo y${\displaystyle \beta (p_{2})}$es el${\displaystyle 4^{th}}$función objetivo.

Consideremos otro ejemplo donde${\displaystyle p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4}\in \{0,1\}}$y${\displaystyle f(r_{1},r_{2},r_{3},r_{4})}$es una función de valor real. Ahora, consideraremos el problema MPF donde el semianillo conmutativo se define como el conjunto de números reales con suma y multiplicación ordinarias y los dominios locales y los núcleos locales se definen de la siguiente manera:

Ahora bien, dado que el núcleo global se define como el producto de los núcleos locales, es

${\displaystyle F(p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4})=f(p_{1},p_{2},p_{3},p_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}}$

y la función objetivo en el dominio local${\displaystyle p_{1},p_{2},p_{3},p_{4}}$es

${\displaystyle F(p_{1},p_{2},p_{3},p_{4})=\displaystyle \sum \limits _{r_{1},r_{2},r_{3},r_{4}}f(r_{1},r_{2},r_{3},r_{4})\cdot (-1)^{p_{1}r_{1}+p_{2}r_{2}+p_{3}r_{3}+p_{4}r_{4}}.}$

Esta es la transformada de Hadamard de la función${\displaystyle f(\cdot )}$Por lo tanto, podemos ver que el cálculo de la transformada de Hadamard es un caso especial del problema MPF. Se pueden mostrar más ejemplos para demostrar que el problema MPF constituye casos especiales de muchos problemas clásicos, como se explicó anteriormente, cuyos detalles se pueden encontrar en ^{[ 1 ].}

Si se puede encontrar una relación entre los elementos de un conjunto dado${\displaystyle S}$, entonces se puede resolver el problema MPF basándose en la noción de propagación de creencias , que es un uso especial de la técnica de "paso de mensajes". La relación requerida es que el conjunto dado de dominios locales se puede organizar en un árbol de unión . En otras palabras, creamos un árbol de teoría de grafos con los elementos de${\displaystyle S}$como los vértices del árbol${\displaystyle T}$, de tal manera que para cualesquiera dos vértices arbitrarios digamos${\displaystyle v_{i}}$y${\displaystyle v_{j}}$dónde${\displaystyle i\neq j}$y existe una arista entre estos dos vértices, entonces la intersección de las etiquetas correspondientes, a saber:${\displaystyle S_{i}\cap S_{j}}$, es un subconjunto de la etiqueta en cada vértice en el camino único desde${\displaystyle v_{i}}$a${\displaystyle v_{j}}$.

Por ejemplo,

Ejemplo 1: Consideremos los siguientes nueve dominios locales:

1. ${\displaystyle \{p_{2}\}}$
2. ${\displaystyle \{p_{3},p_{2}\}}$
3. ${\displaystyle \{p_{2},p_{1}\}}$
4. ${\displaystyle \{p_{3},p_{4}\}}$
5. ${\displaystyle \{p_{3}\}}$
6. ${\displaystyle \{p_{1},p_{4}\}}$
7. ${\displaystyle \{p_{1}\}}$
8. ${\displaystyle \{p_{4}\}}$
9. ${\displaystyle \{p_{2},p_{4}\}}$

Para el conjunto de dominios locales dado anteriormente, se pueden organizar en un árbol de unión como se muestra a continuación:

De manera similar, si se da otro conjunto como el siguiente

Ejemplo 2: Consideremos los siguientes cuatro dominios locales:

1. ${\displaystyle \{p_{1},p_{2}\}}$
2. ${\displaystyle \{p_{2},p_{3}\}}$
3. ${\displaystyle \{p_{3},p_{4}\}}$
4. ${\displaystyle \{p_{1},p_{4}\}}$

Entonces, construir el árbol solo con estos dominios locales no es posible, ya que este conjunto de valores no tiene dominios comunes que puedan ubicarse entre dos valores cualesquiera del conjunto anterior. Sin embargo, si se agregan los dos dominios ficticios como se muestra a continuación, organizar el conjunto actualizado en un árbol de unión sería posible y, además, sencillo.

5.${\displaystyle \{p_{1},p_{2}}$,${\displaystyle p_{4}\}}$ 6.${\displaystyle \{p_{2},p_{3}}$,${\displaystyle p_{4}\}}$

De manera similar, para este conjunto de dominios, el árbol de unión se ve como se muestra a continuación:

Hay dos casos especiales de los que vamos a hablar aquí, a saber, el problema de un solo vértice, en el que la función objetivo se calcula en un solo vértice.${\displaystyle v_{0}}$ y el segundo es el Problema de Todos los Vértices, donde el objetivo es calcular la función objetivo en todos los vértices.

Comencemos con el problema de un solo vértice ; GDL comenzará dirigiendo cada arista hacia el vértice objetivo.${\displaystyle v_{0}}$Aquí, los mensajes se envían únicamente en la dirección hacia el vértice de destino. Tenga en cuenta que todos los mensajes dirigidos se envían solo una vez. Los mensajes se inician desde los nodos hoja (donde el grado es 1) y se dirigen hacia el vértice de destino.${\displaystyle v_{0}}$El mensaje viaja desde las hojas a sus padres y luego de allí a los padres de estos y así sucesivamente hasta que llega al vértice objetivo.${\displaystyle v_{0}}$. El vértice objetivo${\displaystyle v_{0}}$Calculará su estado solo cuando reciba todos los mensajes de todos sus vecinos. Una vez que tengamos el estado, habremos obtenido la respuesta y, por lo tanto, el algoritmo finalizará.

Por ejemplo, consideremos un árbol de unión construido a partir del conjunto de dominios locales dados anteriormente, es decir, el conjunto del ejemplo 1. Ahora, la tabla de programación para estos dominios es (donde el vértice objetivo es${\displaystyle p_{2}}$).

${\displaystyle {\text{Round Message or State Computation}}}$${\displaystyle 1.\mu _{8,4}(p_{4})=\alpha _{8}(p_{4})}$${\displaystyle 2.\mu _{8,4}(p_{4})=\Sigma _{p_{2}}\alpha _{9}(p_{2},p_{4})}$${\displaystyle 3.\mu _{5,2}(p_{3})=\alpha _{5}(p_{3})}$${\displaystyle 4.\mu _{6,3}(p_{1})=\Sigma _{p_{4}}\alpha _{6}(p_{1},p_{4})}$${\displaystyle 5.\mu _{7,3}(p_{1})=\alpha _{7}(p_{1})}$${\displaystyle 6.\mu _{4,2}(p_{3})=\Sigma _{p_{4}}\alpha _{4}(p_{3},p_{4}).\mu _{8,4}(p_{4}).\mu _{9,4}(p_{4})}$${\displaystyle 7.\mu _{3,1}(p_{2})=\Sigma _{p_{1}}\alpha _{3}(p_{2},p_{1}).\mu _{6,3}(p_{1}).\mu _{7,3}(p_{1})}$${\displaystyle 8.\mu _{2,1}(p_{2})=\Sigma _{p_{3}}\alpha _{2}(p_{3},p_{2}).\mu _{4,2}(p_{3}).\mu _{5,2}(p_{3})}$${\displaystyle 9.\sigma _{1}(p_{2})=\alpha _{1}(p_{2}).\mu _{2,1}(p_{2}).\mu _{3,1}(p_{2})}$

Por lo tanto, la complejidad para GDL de un solo vértice se puede mostrar como

${\displaystyle \Sigma _{v}d(v)|A_{S_{(v)}}|}$ operaciones aritméticas Donde (Nota: La explicación de la ecuación anterior se explica más adelante en el artículo) ${\displaystyle S(v)}$es la etiqueta de${\displaystyle v}$. ${\displaystyle d(v)}$es el grado de${\displaystyle v}$(es decir, número de vértices adyacentes a v).

Para resolver el problema de todos los vértices , podemos programar GDL de varias maneras. Una de ellas es la implementación paralela, donde en cada ronda se actualiza cada estado y se calcula y transmite cada mensaje simultáneamente. En este tipo de implementación, los estados y los mensajes se estabilizan tras un número de rondas que, como máximo, es igual al diámetro del árbol. En este punto, todos los estados de los vértices coincidirán con la función objetivo deseada.

Otra forma de programar GDL para este problema es la implementación en serie, que es similar al problema de un solo vértice, excepto que no detenemos el algoritmo hasta que todos los vértices de un conjunto requerido hayan recibido todos los mensajes de todos sus vecinos y hayan calculado su estado. Por lo tanto, el número de operaciones aritméticas que requiere esta implementación es como máximo${\displaystyle \Sigma _{v\in V}d(v)|A_{S_{(v)}}|}$operaciones aritméticas.

La clave para construir un árbol de unión reside en el grafo del dominio local.${\displaystyle G_{LD}}$, que es un grafo completo ponderado con${\displaystyle M}$vértices${\displaystyle v_{1},v_{2},v_{3},\ldots ,v_{M}}$es decir, uno para cada dominio local, con el peso de la arista. ${\displaystyle e_{i,j}:v_{i}\leftrightarrow v_{j}}$definido por ${\displaystyle \omega _{i,j}=|S_{i}\cap S_{j}|}$. si${\displaystyle x_{k}\in S_{i}\cap S_{j}}$, entonces decimos${\displaystyle x_{k}}$está contenido en${\displaystyle e_{i,j}}$. Denotado por${\displaystyle \omega _{max}}$(el peso de un árbol de expansión de peso máximo de${\displaystyle G_{LD}}$), que se define por

${\displaystyle \omega ^{*}=\Sigma _{i=1}^{M}|S_{i}|-n}$

donde n es el número de elementos en ese conjunto. Para mayor claridad y detalles, consulte estos enlaces: ^{[ 3 ] [ 4 ]}

Dejar${\displaystyle 'T'}$ser un árbol de unión con conjunto de vértices${\displaystyle 'V'}$y conjunto de bordes${\displaystyle 'E'}$En este algoritmo, los mensajes se envían en ambas direcciones en cualquier arista, por lo que podemos decir/considerar el conjunto de aristas E como un conjunto de pares ordenados de vértices. Por ejemplo, de la Figura 1${\displaystyle 'E'}$se puede definir de la siguiente manera

${\displaystyle E=\{(1,2),(2,1),(1,3),(3,1),(4,2),(2,4),(5,2),(2,5),(6,3),(3,6),(7,3),(3,7),(8,4),(4,8),(9,4),(4,9)\}}$

NOTA:${\displaystyle E}$Lo anterior te muestra todas las direcciones posibles que puede seguir un mensaje en el árbol.

El cronograma para el GDL se define como una secuencia finita de subconjuntos de${\displaystyle E}$. Que generalmente se representa por ${\displaystyle {\mathcal {E}}=}${${\displaystyle E_{1},E_{2},E_{3},\ldots ,E_{N}}$}, Dónde${\displaystyle E_{N}}$es el conjunto de mensajes actualizados durante el${\displaystyle N^{th}}$ronda de ejecución del algoritmo.

Habiendo definido/visto algunas notaciones, veremos lo que dice el teorema, cuando se nos da un cronograma.${\displaystyle {\mathcal {E}}=\{E_{1},E_{2},E_{3},\ldots ,E_{N}\}}$, el enrejado de mensajes correspondiente como un grafo dirigido finito con conjunto de vértices de ${\displaystyle V\times \{0,1,2,3,\ldots ,N\}}$, en el que un elemento típico se denota por${\displaystyle v_{i}(t)}$para ${\displaystyle t\in \{0,1,2,3,\ldots ,N\}}$, Luego, después de completar el paso del mensaje, estado en el vértice${\displaystyle v_{j}}$será el${\displaystyle j^{\text{th}}}$objetivo definido en

${\displaystyle \sigma (p_{S_{i}})=\alpha _{i}(p_{S_{i}})\prod _{v_{k}\operatorname {adj} v_{i}}\mu _{k,j}(p_{S_{k}\cap S_{i}})}$

y si existe un camino desde${\displaystyle v_{i}(0)}$a${\displaystyle v_{j}(N)}$

Aquí intentamos explicar la complejidad de resolver el problema MPF en términos del número de operaciones matemáticas necesarias para el cálculo. Es decir, comparamos el número de operaciones necesarias al calcularlo utilizando el método normal (aquí por método normal nos referimos a métodos que no utilizan paso de mensajes ni árboles de unión; en resumen, métodos que no utilizan los conceptos de GDL) y el número de operaciones utilizando la ley distributiva generalizada.

Ejemplo: Consideremos el caso más simple en el que necesitamos calcular la siguiente expresión.${\displaystyle ab+ac}$.

Para evaluar esta expresión de forma ingenua se requieren dos multiplicaciones y una suma. La expresión, cuando se expresa utilizando la ley distributiva, se puede escribir como${\displaystyle a(b+c)}$Una optimización sencilla que reduce el número de operaciones a una suma y una multiplicación.

De forma similar al ejemplo explicado anteriormente, expresaremos las ecuaciones en diferentes formas para realizar la menor cantidad de operaciones posible aplicando el GDL.

Como se explicó en las secciones anteriores, resolvemos el problema utilizando el concepto de árboles de unión. La optimización obtenida mediante el uso de estos árboles es comparable a la obtenida al resolver un problema de semigrupos en árboles. Por ejemplo, para encontrar el mínimo de un grupo de números, podemos observar que si tenemos un árbol y todos los elementos están en la base del árbol, podemos comparar el mínimo de dos elementos en paralelo y el mínimo resultante se escribirá en el nodo padre. Cuando este proceso se propaga hacia arriba en el árbol, el mínimo del grupo de elementos se encontrará en la raíz.

A continuación se muestra la complejidad para resolver el árbol de unión mediante paso de mensajes.

Reescribimos la fórmula utilizada anteriormente de la siguiente forma. Esta es la ecuación para un mensaje que se enviará del vértice v al vértice w.

${\displaystyle \mu _{v,w}(p_{v\cap w})=\sum _{p_{v\setminus w}\in A_{S(v)\setminus S(w)}}\alpha _{v}(p_{v})\prod _{uadjv_{u\neq v}}\mu _{u,v}(p_{u\cap v})}$ ----ecuación del mensaje

De manera similar, reescribimos la ecuación para calcular el estado del vértice v de la siguiente manera:

${\displaystyle \sigma _{v}(p_{v})=\alpha _{v}(p_{v})\prod _{u\operatorname {adj} v}\mu _{v,w}(p_{v\cap w})}$

Primero analizaremos el problema de un solo vértice y asumiremos que el vértice objetivo es${\displaystyle v_{0}}$y por lo tanto tenemos una ventaja de${\displaystyle v}$a${\displaystyle v_{0}}$Supongamos que tenemos una arista${\displaystyle (v,w)}$Calculamos el mensaje usando la ecuación del mensaje. Para calcular${\displaystyle p_{u\cap v}}$requiere

${\displaystyle q_{v\setminus w}-1}$

adiciones y

${\displaystyle q_{v\setminus w}(d(v)-1)}$

multiplicaciones.

(Nosotros representamos a la${\displaystyle |A_{S(v)\ S(w)}|}$como${\displaystyle q_{v\setminus w}}$.)

Pero habrá muchas posibilidades para${\displaystyle x_{v\cap w}}$por eso ${\displaystyle q_{v\cap w}{\stackrel {\mathrm {def} }{=}}|A_{S(v)\cap S(w)}|}$posibilidades para${\displaystyle p_{v\cap w}}$Por lo tanto, todo el mensaje necesitará

${\displaystyle (q_{v\cap w})(q_{v\setminus w}-1)=q_{v}-q_{v\cap w}}$

adiciones y

${\displaystyle (q_{v\cap w})q_{v\setminus w}.(d(v)-1)=(d(v)-1)q_{v}}$

multiplicaciones

El número total de operaciones aritméticas necesarias para enviar un mensaje hacia${\displaystyle v_{0}}$a lo largo de los bordes del árbol estará

${\displaystyle \sum _{v\neq v0}(q_{v}-q_{v\cap w})}$

adiciones y

${\displaystyle \sum _{v\neq v0}(d(v)-1)q_{v}}$

multiplicaciones.

Una vez que se han transmitido todos los mensajes, el algoritmo finaliza con el cálculo del estado en${\displaystyle v_{0}}$El cálculo del estado requiere${\displaystyle d(v_{0})q_{0}}$más multiplicaciones.

Por lo tanto, el número de cálculos necesarios para calcular el estado se indica a continuación.

${\displaystyle \sum _{v\neq v_{0}}(q_{v}-q_{v\cap w})}$

adiciones y

${\displaystyle \sum _{v\neq v_{0}}(d(v)-1)q_{v}+d(v_{0})q_{v_{0}}}$

multiplicaciones

Por lo tanto, el gran total del número de cálculos es

${\displaystyle \chi (T)=\sum _{v\in V}d(v)q_{v}-\sum _{e\in E}q_{e}}$----${\displaystyle (1)}$

dónde${\displaystyle e=(v,w)}$es una arista y su tamaño está definido por${\displaystyle q_{v\cap w}}$

La fórmula anterior nos da el límite superior.

Si definimos la complejidad del borde${\displaystyle e=(v,w)}$como

${\displaystyle \chi (e)=q_{v}+q_{w}-q_{v\cap w}}$

Por lo tanto,${\displaystyle (1)}$se puede escribir como

${\displaystyle \chi (T)=\sum _{e\in E}\chi (e)}$

Ahora calculamos la complejidad de las aristas para el problema definido en la Figura 1 de la siguiente manera:

${\displaystyle \chi (1,2)=q_{2}+q_{2}q_{3}-q_{2}}$

${\displaystyle \chi (2,4)=q_{3}q_{4}+q_{2}q_{3}-q_{3}}$

${\displaystyle \chi (2,5)=q_{3}+q_{2}q_{3}-q_{3}}$

${\displaystyle \chi (4,8)=q_{4}+q_{3}q_{4}-q_{4}}$

${\displaystyle \chi (4,9)=q_{2}q_{4}+q_{3}q_{4}-q_{4}}$

${\displaystyle \chi (1,3)=q_{2}+q_{2}q_{1}-q_{2}}$

${\displaystyle \chi (3,7)=q_{1}+q_{1}q_{2}-q_{1}}$

${\displaystyle \chi (3,6)=q_{1}q_{4}+q_{1}q_{2}-q_{1}}$

La complejidad total será${\displaystyle 3q_{2}q_{3}+3q_{3}q_{4}+3q_{1}q_{2}+q_{2}q_{4}+q_{1}q_{4}-q_{1}-q_{3}-q_{4}}$lo cual es considerablemente bajo en comparación con el método directo. (Aquí, por método directo nos referimos a los métodos que no utilizan el paso de mensajes. El tiempo empleado con el método directo será equivalente al tiempo necesario para calcular el mensaje en cada nodo y el estado de cada uno de ellos).

Ahora consideramos el problema de todos los vértices, donde el mensaje deberá enviarse en ambas direcciones y el estado deberá calcularse en ambos vértices. Esto tomaría${\displaystyle O(\sum _{v}d(v)d(v)q_{v})}$pero mediante el preprocesamiento podemos reducir el número de multiplicaciones a${\displaystyle 3(d-2)}$. Aquí${\displaystyle d}$es el grado del vértice. Ejemplo: Si hay un conjunto${\displaystyle (a_{1},\ldots ,a_{d})}$con${\displaystyle d}$números. Es posible calcular todos los productos d de${\displaystyle d-1}$del${\displaystyle a_{i}}$con como máximo${\displaystyle 3(d-2)}$multiplicaciones en lugar de lo obvio${\displaystyle d(d-2)}$Lo hacemos precalculando las cantidades.${\displaystyle b_{1}=a_{1},b_{2}=b_{1}\cdot a_{2}=a_{1}\cdot a_{2},b_{d-1}=b_{d-2}\cdot a_{d-1}=a_{1}a_{2}\cdots a_{d-1}}$y${\displaystyle c_{d}=a_{d},c_{d-1}=a_{d-1}c_{d}=a_{d-1}\cdot a_{d},\ldots ,c_{2}=a_{2}\cdot c_{3}=a_{2}a_{3}\cdots a_{d}}$esto toma${\displaystyle 2(d-2)}$multiplicaciones. Entonces si${\displaystyle m_{j}}$denota el producto de todos${\displaystyle a_{i}}$excepto${\displaystyle a_{j}}$tenemos${\displaystyle m_{1}=c_{2},m_{2}=b_{1}\cdot c_{3}}$y así sucesivamente necesitará otro${\displaystyle d-2}$multiplicaciones que dan como resultado el total${\displaystyle 3(d-2)}$.

No hay mucho que podamos hacer en lo que respecta a la construcción del árbol de unión, excepto que podemos tener muchos árboles de expansión de peso máximo y debemos elegir el árbol de expansión con el menor${\displaystyle \chi (T)}$y a veces esto puede significar agregar un dominio local para reducir la complejidad del árbol de unión.

Podría parecer que GDL solo es correcto cuando los dominios locales pueden expresarse como un árbol de unión. Sin embargo, incluso en casos con ciclos y varias iteraciones, los mensajes serán aproximadamente iguales a la función objetivo. Los experimentos realizados con el algoritmo de Gallager-Tanner-Wiberg para códigos de verificación de paridad de baja densidad respaldaron esta afirmación.