Точное усреднение в сети за 2N сложений обратной подстановкой: анализ и численный тест на 53 узлах

Исследователь Ricardo Merched опубликовал в журнале Applied Network Science математическую работу о консенсусе по среднему: как N агентов кооперативной сети находят точное арифметическое среднее разрозненных локальных данных без центрального процессора. По данным статьи, на неориентированном связном графе точное среднее можно вычислить рекурсиями прямой и обратной подстановки при полной сложности всего от 2N сложений springer.comApplied Network Sciencespringer.comОткрыть источник ↗. Для неориентированных графов существующие схемы требуют O(KN²) умножений, где K — число различных собственных значений матрицы Лапласа графа.

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

Обратная подстановка вместо обращения матрицы

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

Треугольный множитель можно задать с постоянными элементами 1 и −1 под главной диагональю, поэтому при вычислении умножения не нужны. Сеть получает точное среднее за 2N шагов обмена, всего с 2N сложениями. Треугольные подстановки обратно устойчивы, поэтому, как сообщает работа, результат не зависит от алгебраической связности графа и обусловленности его матрицы Лапласа springer.comApplied Network Sciencespringer.comОткрыть источник ↗.

В работе также дана альтернативная точная форма — матричный графовый фильтр с конечной импульсной характеристикой. Строго нижнетреугольная часть переупорядоченного множителя нильпотентна, поэтому ряд Неймана конечен. В графе из 53 узлов оператор обратился в нуль за 23 итерации, а вся операция заняла 47 матричных проходов со сложностью порядка N² сложений.

Почему метод собственных шагов численно неустойчив

Конечновременной метод собственных шагов (eigenstep) использует переменные шаги, равные обратным величинам различных ненулевых собственных значений матрицы комбинирования; в теории это гасит моды расхождения за K итераций. Статья показывает, что ненормированные рекурсии численно неустойчивы на больших или плохо обусловленных матрицах: шаги намного превышают пороги устойчивости и умножают ошибки округления при вычислениях с конечной точностью.

Для старших мод автор выводит оценку усиления ошибки первого порядка: число обусловленности спектра минус единица в степени, пропорциональной размерности сети. В тесте на неориентированной сети из 53 узлов с ветвью-путём машинная ошибка округления около 2,22×10⁻¹⁶ выросла до порядка 10⁴², и сеть не достигла консенсуса springer.comApplied Network Sciencespringer.comОткрыть источник ↗.

Работа также обобщает метод собственных шагов на ориентированные графы с несимметричными матрицами комбинирования. Теорема 1 утверждает, что переменные собственные шаги сходятся ровно за K шагов для диагонализируемых несимметричных матриц.