Обобщенный распределительный закон

Обобщенный дистрибутивный закон (GDL) — это обобщение распределительного свойства , которое приводит к общему алгоритму передачи сообщений . Это синтез работ многих авторов в области теории информации , цифровых коммуникаций , обработки сигналов , статистики и искусственного интеллекта . Закон и алгоритм были представлены в полуучебнике Шриниваса М. Аджи и Роберта Дж. МакЭлиса с таким же названием.

Введение

«Распределительный закон в математике — это закон, связывающий операции умножения и сложения, выраженный символически: $a*(b+c)=a*b+a*c$; то есть мономиальный множитель $a$ распределяется или применяется отдельно к каждому члену биномиального коэффициента $b+c$, в результате чего получается продукт $a*b+a*c$" - Британника

Как видно из определения, применение распределительного закона к арифметическому выражению уменьшает количество операций в нем. В предыдущем примере общее количество операций уменьшено с трех (два умножения и сложение в $a*b+a*c$) до двух (одно умножение и одно сложение в $a*(b+c)$). Обобщение распределительного закона приводит к появлению большого семейства быстрых алгоритмов . Сюда входят БПФ и алгоритм Витерби .

Более формально это объясняется в примере ниже:

$\alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c,d,e\in A}f(a,\,c,\,b)\,g(a,\,d,\,e)$ где $f(\cdot )$ и $g(\cdot )$ являются вещественнозначными функциями, $a,b,c,d,e\in A$ и $|A|=q$ (сказать)

Здесь мы «маргинализируем» независимые переменные ( $c$, $d$, и $e$), чтобы получить результат. Когда мы вычисляем вычислительную сложность, мы видим, что для каждого $q^{2}$ пары $(a,b)$, есть $q^{3}$ условия из-за тройки $(c,d,e)$ который должен принять участие в оценке $\alpha (a,\,b)$ причем каждый шаг имеет одно сложение и одно умножение. Таким образом, общее количество необходимых вычислений равно $2\cdot q^{2}\cdot q^{3}=2q^{5}$. Следовательно, асимптотическая сложность указанной выше функции равна $O(n^{5})$.

Если мы применим распределительный закон к правой части уравнения, мы получим следующее:

$\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)$

Это означает, что $\alpha (a,\,b)$ можно охарактеризовать как продукт $\alpha _{1}(a,\,b)\cdot \alpha _{2}(a)$ где $\alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)$ и $\alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)$

Теперь, когда мы вычисляем вычислительную сложность, мы видим, что есть $q^{3}$ дополнения в $\alpha _{1}(a,\,b)$ и $\alpha _{2}(a)$ каждый и есть $q^{2}$ умножения, когда мы используем продукт $\alpha _{1}(a,\,b)\cdot \alpha _{2}(a)$ оценивать $\alpha (a,\,b)$. Таким образом, общее количество необходимых вычислений равно $q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}$. Отсюда асимптотическая сложность вычисления $\alpha (a,b)$ сводится к $O(n^{3})$ от $O(n^{5})$. На примере это показывает, что применение распределительного закона снижает сложность вычислений, что является одной из хороших особенностей «быстрого алгоритма».

История

Некоторые из проблем, для решения которых использовался распределительный закон, можно сгруппировать следующим образом.

1. Алгоритмы декодирования
Алгоритм, подобный GDL, использовался Галлагером для декодирования кодов с низкой плотностью проверки на четность. На основе работы Галлагера Таннер представил граф Таннера и выразил работу Галлагера в форме передачи сообщений. Граф кожевников также помог объяснить алгоритм Витерби .

Форни заметил, что декодирование сверточных кодов методом максимального правдоподобия Витерби также использовало алгоритмы общности, подобной GDL.

2. Алгоритм вперед-назад
Алгоритм вперед-назад помог в качестве алгоритма отслеживания состояний в цепи Маркова . И здесь также использовался алгоритм GDL, подобный общности.

3. Искусственный интеллект
Понятие деревьев соединений использовалось для решения многих проблем в области искусственного интеллекта. Также в концепции исключения корзин использовались многие концепции.

Проблема MPF

MPF или маргинализация функции продукта — это общая вычислительная задача, которая в качестве частного случая включает в себя множество классических задач, таких как вычисление дискретного преобразования Адамара , декодирование с линейного кода без памяти максимальным правдоподобием по каналу и умножение цепочки матриц . Сила GDL заключается в том, что он применим к ситуациям, в которых сложение и умножение являются обобщенными.Коммутативное полукольцо является хорошей основой для объяснения такого поведения. Он определен на множестве $K$ с операторами» $+$" и " $.$" где $(K,\,+)$ и $(K,\,.)$ являются коммутативными моноидами и выполняется распределительный закон.

Позволять $p_{1},\ldots ,p_{n}$ быть такими переменными, что $p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}$ где $A$ является конечным множеством и $|A_{i}|=q_{i}$. Здесь $i=1,\ldots ,n$. Если $S=\{i_{1},\ldots ,i_{r}\}$ и $S\,\subset \{1,\ldots ,n\}$, позволять $A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}$, $p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})$, $q_{S}=|A_{S}|$, $\mathbf {A} =A_{1}\times \cdots \times A_{n}$, и $\mathbf {p} =\{p_{1},\ldots ,p_{n}\}$

Позволять $S=\{S_{j}\}_{j=1}^{M}$ где $S_{j}\subset \{1,...\,,n\}$. Предположим, что функция определена как $\alpha _{i}:A_{S_{i}}\rightarrow R$, где $R$ является коммутативным полукольцом . Также, $p_{S_{i}}$ называются локальными доменами и $\alpha _{i}$ как локальные ядра .

Теперь глобальное ядро $\beta :\mathbf {A} \rightarrow R$ определяется как: $\beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})$

Определение проблемы MPF : для одного или нескольких индексов. $i=1,...\,,M$, вычислить таблицу значений $S_{i}$- маргинализация глобального ядра $\beta$, что является функцией $\beta _{i}:A_{S_{i}}\rightarrow R$ определяется как $\beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)$

Здесь $S_{i}^{c}$ является дополнением $S_{i}$ относительно $\mathbf {\{} 1,...\,,n\}$ и $\beta _{i}(p_{S_{i}})$ называется $i^{th}$ целевая функция или целевая функция при $S_{i}$. Можно заметить, что вычисление $i^{th}$ целевая функция очевидным образом требует $Mq_{1}q_{2}q_{3}\cdots q_{n}$ операции. Это потому, что есть $q_{1}q_{2}\cdots q_{n}$ дополнения и $(M-1)q_{1}q_{2}...q_{n}$ умножения, необходимые для вычисления $i^{\text{th}}$ целевая функция. Алгоритм GDL, который объясняется в следующем разделе, может уменьшить эту вычислительную сложность.

Ниже приведен пример проблемы MPF. Позволять $p_{1},\,p_{2},\,p_{3},\,p_{4},$ и $p_{5}$ быть такими переменными, что $p_{1}\in A_{1},p_{2}\in A_{2},p_{3}\in A_{3},p_{4}\in A_{4},$ и $p_{5}\in A_{5}$. Здесь $M=4$ и $S=\{\{1,2,5\},\{2,4\},\{1,4\},\{2\}\}$. Данными функциями, использующими эти переменные, являются $f(p_{1},p_{2},p_{5})$ и $g(p_{3},p_{4})$ и нам нужно посчитать $\alpha (p_{1},\,p_{4})$ и $\beta (p_{2})$ определяется как:

$\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})$

$\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})$

Здесь локальные домены и локальные ядра определяются следующим образом:

локальные домены	локальные ядра
$\{p_{1},p_{2},p_{5}\}$	$(f(p_{1},p_{2},p_{5})$
$\{p_{2},p_{4}\}$	$g(p_{2},p_{4})$
$\{p_{1},p_{4}\}$	$1$
$\{p_{2}\}$	$1$

где $\alpha (p_{1},p_{4})$ это $3^{rd}$ целевая функция и $\beta (p_{2})$ это $4^{th}$ целевая функция.

Рассмотрим еще один пример, где $p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4}\in \{0,1\}$ и $f(r_{1},r_{2},r_{3},r_{4})$ является действительнозначной функцией. Теперь мы рассмотрим задачу MPF, где коммутативное полукольцо определяется как набор действительных чисел с обычным сложением и умножением, а локальные области определения и локальные ядра определяются следующим образом:

локальные домены	локальные ядра
$\{r_{1},r_{2},r_{3},r_{4}\}$	$f(r_{1},r_{2},r_{3},r_{4})$
$\{p_{1},r_{1}\}$	$(-1)^{p_{1}r_{1}}$
$\{p_{2},r_{2}\}$	$(-1)^{p_{2}r_{2}}$
$\{p_{3},r_{3}\}$	$(-1)^{p_{3}r_{3}}$
$\{p_{4},r_{4}\}$	$(-1)^{p_{4}r_{4}}$
$\{p_{1},p_{2},p_{3},p_{4}\}$	$1$

Теперь, поскольку глобальное ядро ​​определяется как произведение локальных ядер, оно

$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}}$

и целевая функция в локальной области $p_{1},p_{2},p_{3},p_{4}$ является

$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}}.$

Это преобразование Адамара функции $f(\cdot )$. Следовательно, мы видим, что вычисление преобразования Адамара является частным случаем проблемы MPF. Можно продемонстрировать больше примеров, чтобы доказать, что проблема MPF образует частные случаи многих классических проблем, как описано выше, подробности которых можно найти по адресу

GDL: алгоритм решения задачи MPF

Если можно найти связь между элементами данного множества $S$, то можно решить проблему MPF, основываясь на понятии распространения убеждений , которое представляет собой специальное использование техники «передачи сообщений». Требуемая связь заключается в том, что данный набор локальных доменов может быть организован в дерево соединений . Другими словами, мы создаем дерево теории графов с элементами $S$ как вершины дерева $T$, такой, что для любых двух произвольных вершин скажем $v_{i}$ и $v_{j}$ где $i\neq j$ и между этими двумя вершинами существует ребро, то пересечение соответствующих меток, а именно $S_{i}\cap S_{j}$, является подмножеством метки на каждой вершине уникального пути из $v_{i}$ к $v_{j}$.

Например,

Пример 1. Рассмотрим следующие девять локальных доменов:

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

Для приведенного выше набора локальных доменов можно организовать их в дерево соединений, как показано ниже:

An example of a junction of tree

Аналогично, если задан другой набор, подобный следующему

Пример 2. Рассмотрим следующие четыре локальных домена:

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

Тогда построение дерева только с этими локальными доменами невозможно, поскольку этот набор значений не имеет общих доменов, которые можно было бы разместить между любыми двумя значениями из вышеуказанного набора. Но, однако, если добавить два фиктивных домена, как показано ниже, то организация обновленного набора в дерево соединений будет возможной и простой.

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

Аналогично для этого набора доменов дерево соединений выглядит, как показано ниже:

Another example of a junction tree

Алгоритм обобщенного распределительного закона (GDL)

Входные данные: набор локальных доменов.
Выходные данные: Для заданного набора доменов вычисляется возможное минимальное количество операций, необходимое для решения задачи.
Итак, если $v_{i}$ и $v_{j}$ соединены ребром в дереве соединений, то сообщение от $v_{i}$ к $v_{j}$ представляет собой набор/таблицу значений, заданных функцией: $\mu _{i,j}$: $A_{S_{i}\cap S_{j}}\rightarrow R$. Начнем со всех функций, т.е. для всех комбинаций $i$ и $j$ в данном дереве, $\mu _{i,j}$ определяется как тождественный $1$ и когда конкретное сообщение обновляется, оно следует уравнению, приведенному ниже.

$\mu _{i,j}(p_{S_{i}\cap S_{j}})$ = $\sum _{p_{S_{i}\setminus S_{j}}\in A_{S_{i}\setminus S_{j}}}\alpha _{i}(p_{S_{i}})\prod _{{v_{k}\operatorname {adj} v_{i}},{k\neq j}}\mu _{k,j}(p_{S_{k}\cap S_{i}})(1)$

где $v_{k}\operatorname {adj} v_{i}$ означает, что $v_{k}$ является смежной вершиной с $v_{i}$ в дереве.

Аналогично каждая вершина имеет состояние, которое определяется как таблица, содержащая значения функции. $\sigma _{i}:A_{S_{i}}\rightarrow R$, Точно так же, как сообщения одинаково инициализируются значением 1, состояние $v_{i}$ определяется как локальное ядро $\alpha (p_{S_{i}})$, но всякий раз, когда $\sigma _{i}$ обновляется, он следует следующему уравнению:

$\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}})(2).$

Основная работа алгоритма

Для заданного набора локальных доменов в качестве входных данных мы выясняем, можем ли мы создать дерево соединений, либо используя набор напрямую, либо добавляя сначала в набор фиктивные домены, а затем создавая дерево соединений, если построение соединения невозможно, то Алгоритм выдает, что нет способа уменьшить количество шагов для вычисления данной задачи уравнения, но как только у нас будет дерево соединений, алгоритму придется планировать сообщения и вычислять состояния, делая это, мы можем знать, где шаги можно сократить, следовательно об этом будет сказано ниже.

Планирование передачи сообщений и вычисления состояния

Здесь мы поговорим о двух особых случаях, а именно о задаче с одной вершиной , в которой целевая функция вычисляется только в одной вершине. $v_{0}$ а второй — задача всех вершин , цель которой — вычислить целевую функцию во всех вершинах.

Начнем с задачи с одной вершиной . GDL начнёт с направления каждого ребра к целевой вершине. $v_{0}$. Здесь сообщения отправляются только в направлении целевой вершины. Обратите внимание, что все направленные сообщения отправляются только один раз. Сообщения запускаются из конечных узлов (где степень равна 1) и идут вверх к целевой вершине. $v_{0}$. Сообщение перемещается от листьев к родителям, а затем оттуда к их родителям и так далее, пока не достигнет целевой вершины. $v_{0}$. Целевая вершина $v_{0}$ будет вычислять свое состояние только тогда, когда получит все сообщения от всех своих соседей. Как только мы получим состояние, мы получим ответ, и, следовательно, алгоритм завершит работу.

Например, давайте рассмотрим дерево соединений, построенное на основе набора локальных областей, приведенных выше, то есть набора из примера 1,
Теперь таблица планирования для этих доменов (где целевая вершина $p_{2}$).

${\text{Round Message or State Computation}}$
$1.\mu _{8,4}(p_{4})=\alpha _{8}(p_{4})$
$2.\mu _{8,4}(p_{4})=\Sigma _{p_{2}}\alpha _{9}(p_{2},p_{4})$
$3.\mu _{5,2}(p_{3})=\alpha _{5}(p_{3})$
$4.\mu _{6,3}(p_{1})=\Sigma _{p_{4}}\alpha _{6}(p_{1},p_{4})$
$5.\mu _{7,3}(p_{1})=\alpha _{7}(p_{1})$
$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})$
$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})$
$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})$
$9.\sigma _{1}(p_{2})=\alpha _{1}(p_{2}).\mu _{2,1}(p_{2}).\mu _{3,1}(p_{2})$

Таким образом, сложность Single Vertex GDL можно показать как

$\Sigma _{v}d(v)|A_{S_{(v)}}|$ арифметические операции
Где (Примечание: объяснение приведенного выше уравнения будет дано далее в статье)
$S(v)$ это этикетка $v$.
$d(v)$ это степень ​ $v$ (т.е. количество вершин, смежных с v).

Чтобы решить проблему всех вершин , мы можем запланировать GDL несколькими способами, некоторые из них представляют собой параллельную реализацию, при которой в каждом раунде каждое состояние обновляется, а каждое сообщение вычисляется и передается одновременно. В этом типе реализации состояния и сообщения стабилизируются после количества раундов, не превышающего диаметра дерева. В этот момент все состояния вершин будут равны искомой целевой функции.

Другой способ запланировать GDL для этой задачи — последовательная реализация, которая аналогична задаче с одной вершиной, за исключением того, что мы не останавливаем алгоритм до тех пор, пока все вершины требуемого набора не получат все сообщения от всех своих соседей и не вычислят свои значения. состояние.
Таким образом, количество арифметических операций, требуемых для этой реализации, не превышает $\Sigma _{v\in V}d(v)|A_{S_{(v)}}|$ арифметические операции.

Построение дерева соединений

Ключ к построению дерева соединений лежит в графе локальной области. $G_{LD}$, который представляет собой взвешенный полный граф с $M$ вершины $v_{1},v_{2},v_{3},\ldots ,v_{M}$ т.е. по одному для каждого локального домена, имеющего вес ребра $e_{i,j}:v_{i}\leftrightarrow v_{j}$ определяется
$\omega _{i,j}=|S_{i}\cap S_{j}|$.
если $x_{k}\in S_{i}\cap S_{j}$, тогда мы говорим $x_{k}$ содержится в $e_{i,j}$. Обозначается $\omega _{max}$ (вес остовного дерева максимального веса $G_{LD}$), который определяется

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

где n — количество элементов в этом наборе. Для большей ясности и подробностей, пожалуйста, обратитесь к ним.

Теорема о расписании

Позволять $'T'$ быть деревом соединений с набором вершин $'V'$ и набор кромок $'E'$. В этом алгоритме сообщения отправляются в обоих направлениях по любому ребру, поэтому мы можем рассматривать набор ребер E как набор упорядоченных пар вершин. Например, из рисунка 1 $'E'$ можно определить следующим образом

$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)\}$

ПРИМЕЧАНИЕ: $E$ выше приведены все возможные направления, по которым сообщение может перемещаться по дереву.

Расписание GDL определяется как конечная последовательность подмножеств $E$. Что обычно представлено ${\mathcal {E}}=${ $E_{1},E_{2},E_{3},\ldots ,E_{N}$}, Где $E_{N}$ набор сообщений, обновляемых в течение $N^{th}$ раунд запуска алгоритма.

Определив/увидев некоторые обозначения, мы увидим, что теорема гласит:Когда нам дают расписание ${\mathcal {E}}=\{E_{1},E_{2},E_{3},\ldots ,E_{N}\}$соответствующая решетка сообщений представляет собой конечный ориентированный граф с множеством вершин $V\times \{0,1,2,3,\ldots ,N\}$, в котором типичный элемент обозначается $v_{i}(t)$ для $t\in \{0,1,2,3,\ldots ,N\}$, Затем после завершения передачи сообщения состояние в вершине $v_{j}$ будет $j^{\text{th}}$ цель, определенная в

$\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}})$

и если есть путь из $v_{i}(0)$ к $v_{j}(N)$

Вычислительная сложность

Здесь мы попытаемся объяснить сложность решения задачи МПФ количеством математических операций, необходимых для расчета. т.е. мы сравниваем количество операций, требуемых при расчете с использованием обычного метода (здесь под нормальным методом мы подразумеваем методы, которые не используют передачу сообщений или деревья соединений в коротких методах, не использующих концепции GDL) и количество операций с использованием обобщенный распределительный закон.

Пример: рассмотрим простейший случай, когда нам нужно вычислить следующее выражение $ab+ac$.

Чтобы вычислить это выражение, наивно требуется два умножения и одно сложение. Выражение, выраженное с использованием распределительного закона, можно записать как $a(b+c)$ простая оптимизация, сокращающая количество операций до одного сложения и одного умножения.

Подобно объясненному выше примеру, мы будем выражать уравнения в разных формах, чтобы выполнить как можно меньше операций, применяя GDL.

Как объяснялось в предыдущих разделах, мы решаем проблему, используя концепцию деревьев соединений. Оптимизация, полученная с использованием этих деревьев, сравнима с оптимизацией, полученной путем решения полугрупповой задачи на деревьях. Например, чтобы найти минимум группы чисел, мы можем заметить, что если у нас есть дерево и все элементы находятся в нижней части дерева, тогда мы можем сравнить минимум двух элементов параллельно, и результирующий минимум будет написано родителю. Когда этот процесс распространяется вверх по дереву, минимум группы элементов будет найден в корне.

Ниже приводится сложность решения дерева соединений с использованием передачи сообщений.

Перепишем использованную ранее формулу к следующему виду. Это уравнение для отправки сообщения из вершины v в вершину w.

$\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})$ ----уравнение сообщения

Аналогично перепишем уравнение для расчета состояния вершины v следующим образом

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

Сначала мы проанализируем задачу с одной вершиной и предположим, что целевая вершина равна $v_{0}$ и, следовательно, у нас есть одно ребро от $v$ к $v_{0}$. Предположим, у нас есть преимущество $(v,w)$ мы вычисляем сообщение, используя уравнение сообщения. Чтобы рассчитать $p_{u\cap v}$ требует

$q_{v\setminus w}-1$

дополнения и

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

умножения.

(Мы представляем $|A_{S(v)\ S(w)}|$ как $q_{v\setminus w}$.)

Но будет много возможностей для $x_{v\cap w}$ следовательно
$q_{v\cap w}{\stackrel {\mathrm {def} }{=}}|A_{S(v)\cap S(w)}|$ возможности для $p_{v\cap w}$.Таким образом, все сообщение будет нуждаться в

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

дополнения и

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

умножения

Общее количество арифметических операций, необходимых для отправки сообщения $v_{0}$по краям дерева будет

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

дополнения и

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

умножения.

Как только все сообщения будут переданы, алгоритм завершается вычислением состояния в точке $v_{0}$ Вычисление состояния требует $d(v_{0})q_{0}$ еще умножения.Таким образом, количество вычислений, необходимых для расчета состояния, указано ниже.

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

дополнения и

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

умножения

Таким образом, общая сумма вычислений равна

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

где $e=(v,w)$ является ребром, и его размер определяется выражением $q_{v\cap w}$

Формула выше дает нам верхнюю границу.

Если мы определим сложность ребра $e=(v,w)$ как

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

Поэтому, $(1)$ можно записать как

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

Теперь мы рассчитаем сложность ребра для задачи, определенной на рисунке 1, следующим образом:

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

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

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

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

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

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

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

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

Общая сложность составит $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}$ что значительно ниже, чем при прямом методе. (Здесь под прямым методом мы подразумеваем методы, которые не используют передачу сообщений. Время, затраченное на использование прямого метода, будет эквивалентно вычислению сообщения на каждом узле и времени на вычисление состояния каждого из узлов.)

Теперь мы рассмотрим задачу всех вершин, где сообщение необходимо будет отправить в обоих направлениях, а состояние должно быть вычислено в обеих вершинах. Это потребует $O(\sum _{v}d(v)d(v)q_{v})$ но с помощью предварительных вычислений мы можем сократить количество умножений до $3(d-2)$. Здесь $d$ — степень вершины. Пример: Если есть набор $(a_{1},\ldots ,a_{d})$ с $d$ цифры. Можно вычислить все d произведений $d-1$ принадлежащий $a_{i}$ с максимум $3(d-2)$ умножения, а не очевидного $d(d-2)$. Мы делаем это путем предварительного вычисления величин $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}$ и $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}$ это занимает $2(d-2)$ умножения. Тогда, если $m_{j}$ обозначает произведение всех $a_{i}$ за исключением $a_{j}$ у нас есть $m_{1}=c_{2},m_{2}=b_{1}\cdot c_{3}$ и так далее понадобится еще один $d-2$ умножения, составляющие сумму $3(d-2)$

Когда дело доходит до построения соединительного дерева, мы мало что можем сделать, за исключением того, что у нас может быть много остовных деревьев с максимальным весом, и нам следует выбрать остовное дерево с наименьшим $\chi (T)$ а иногда это может означать добавление локального домена для снижения сложности дерева соединений.

Может показаться, что GDL корректен только тогда, когда локальные домены можно выразить в виде дерева соединений. Но даже в тех случаях, когда есть циклы и количество итераций, сообщения будут примерно равны целевой функции. Эксперименты с алгоритмом Галлагера-Таннера-Вайберга для кодов с низкой плотностью проверки на четность подтвердили это утверждение.