Последовательная композиция кланов линейных систем

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Системні дослідження та інформаційні технології
Datum:	2006
1. Verfasser:	Зайцев, Д.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2006
Schlagworte:	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/42182
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Последовательная композиция кланов линейных систем / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 121–137. — Бібліогр.: 8 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-42182
record_format	dspace
spelling	Зайцев, Д.А. 2013-03-11T12:53:00Z 2013-03-11T12:53:00Z 2006 Последовательная композиция кланов линейных систем / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 121–137. — Бібліогр.: 8 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42182 512.8+519.74 Предложена организация последовательного процесса композиции кланов линейных систем для реализации дополнительных ускорений вычислений при их решении. Получено ускорение вычислений путем решения последовательности систем композиции кланов существенно меньшей размерности. Использован граф декомпозиции системы на кланы. Выполнен сравнительный анализ последовательной композиции подграфов и реберной (парной) композиции. Задача построения последовательности систем наименьшей размерности названа оптимальным коллапсом взвешенного графа. Приведены оценки верхней и нижней границ ширины коллапса, которая соответствует размерности систем. Построен и статистически обоснован эвристический алгоритм оптимального коллапса. Запропоновано організацію послідовного процесу композиції кланів лінійних систем для реалізації додаткових прискорень обчислювань при їх розв’язанні. Прискорення обчислень отримано шляхом розв’язання послідовності систем композиції кланів суттєво меншої розмірності. Використано граф декомпозиції системи на клани. Виконано порівняльний аналіз послідовної композиції підграфів та реберної (парної) композиції. Задачу побудови послідовності систем найменшої розмірності названо колапсом зваженого графа. Отримано оцінки верхньої та нижньої границь ширини колапсу, яка відповідає розмірності систем. Побудовано та статистично обґрунтовано евристичний алгоритм оптимального колапсу. To obtain an additional computational speedup in the course of solution of linear systems, it is proposed to organize a sequential process of composition of their clans. Computational speedup was obtained through the solution of a sequence of clan composition systems with essentially lower dimensions using the graph of system decomposition into clans. A comparative analysis of sequential composition for subgraphs and edge (paired 3) composition was performed. The problem of construction of systems sequence with the lowest dimension was named by a collapse of weighted graph. The upper and lower limits of the collapse width which corresponds to the dimension of systems were estimated. A heuristic algorithm of optimal collapse was constructed and statistically grounded. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Последовательная композиция кланов линейных систем Послідовна композиція кланів лінійних систем Sequential composition of clans in linear systems Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Последовательная композиция кланов линейных систем
spellingShingle	Последовательная композиция кланов линейных систем Зайцев, Д.А. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
title_short	Последовательная композиция кланов линейных систем
title_full	Последовательная композиция кланов линейных систем
title_fullStr	Последовательная композиция кланов линейных систем
title_full_unstemmed	Последовательная композиция кланов линейных систем
title_sort	последовательная композиция кланов линейных систем
author	Зайцев, Д.А.
author_facet	Зайцев, Д.А.
topic	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
topic_facet	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
publishDate	2006
language	Russian
container_title	Системні дослідження та інформаційні технології
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format	Article
title_alt	Послідовна композиція кланів лінійних систем Sequential composition of clans in linear systems
description	Предложена организация последовательного процесса композиции кланов линейных систем для реализации дополнительных ускорений вычислений при их решении. Получено ускорение вычислений путем решения последовательности систем композиции кланов существенно меньшей размерности. Использован граф декомпозиции системы на кланы. Выполнен сравнительный анализ последовательной композиции подграфов и реберной (парной) композиции. Задача построения последовательности систем наименьшей размерности названа оптимальным коллапсом взвешенного графа. Приведены оценки верхней и нижней границ ширины коллапса, которая соответствует размерности систем. Построен и статистически обоснован эвристический алгоритм оптимального коллапса. Запропоновано організацію послідовного процесу композиції кланів лінійних систем для реалізації додаткових прискорень обчислювань при їх розв’язанні. Прискорення обчислень отримано шляхом розв’язання послідовності систем композиції кланів суттєво меншої розмірності. Використано граф декомпозиції системи на клани. Виконано порівняльний аналіз послідовної композиції підграфів та реберної (парної) композиції. Задачу побудови послідовності систем найменшої розмірності названо колапсом зваженого графа. Отримано оцінки верхньої та нижньої границь ширини колапсу, яка відповідає розмірності систем. Побудовано та статистично обґрунтовано евристичний алгоритм оптимального колапсу. To obtain an additional computational speedup in the course of solution of linear systems, it is proposed to organize a sequential process of composition of their clans. Computational speedup was obtained through the solution of a sequence of clan composition systems with essentially lower dimensions using the graph of system decomposition into clans. A comparative analysis of sequential composition for subgraphs and edge (paired 3) composition was performed. The problem of construction of systems sequence with the lowest dimension was named by a collapse of weighted graph. The upper and lower limits of the collapse width which corresponds to the dimension of systems were estimated. A heuristic algorithm of optimal collapse was constructed and statistically grounded.
issn	1681–6048
url	https://nasplib.isofts.kiev.ua/handle/123456789/42182
citation_txt	Последовательная композиция кланов линейных систем / Д.А. Зайцев // Систем. дослідж. та інформ. технології. — 2006. — № 2. — С. 121–137. — Бібліогр.: 8 назв. — рос.
work_keys_str_mv	AT zaicevda posledovatelʹnaâkompoziciâklanovlineinyhsistem AT zaicevda poslídovnakompozicíâklanívlíníinihsistem AT zaicevda sequentialcompositionofclansinlinearsystems
first_indexed	2025-11-24T03:23:40Z
last_indexed	2025-11-24T03:23:40Z
_version_	1850840682908876800
fulltext	© Д.А. Зайцев, 2006 Системні дослідження та інформаційні технології, 2006, № 2 121 УДК 512.8+519.74 ПОСЛЕДОВАТЕЛЬНАЯ КОМПОЗИЦИЯ КЛАНОВ ЛИНЕЙНЫХ СИСТЕМ Д.А. ЗАЙЦЕВ Предложена организация последовательного процесса композиции кланов ли- нейных систем для реализации дополнительных ускорений вычислений при их решении. Получено ускорение вычислений путем решения последовательно- сти систем композиции кланов существенно меньшей размерности. Использо- ван граф декомпозиции системы на кланы. Выполнен сравнительный анализ последовательной композиции подграфов и реберной (парной) композиции. Задача построения последовательности систем наименьшей размерности на- звана оптимальным коллапсом взвешенного графа. Приведены оценки верхней и нижней границ ширины коллапса, которая соответствует размерности сис- тем. Построен и статистически обоснован эвристический алгоритм оптималь- ного коллапса. ВВЕДЕНИЕ Линейные системы уравнений (неравенств) широко используются в различ- ных областях современной науки [1, 2]. Известно множество методов их решения [1, 2]. Серьезная научная проблема — эффективное решение ли- нейных систем большой размерности — особенно актуальна при поиске решений в целой неотрицательной области, так как для таких задач извест- ны лишь экспоненциальные алгоритмы решения [3]. В работе [4] для ускорения процессов решения линейных систем в по- лях, кольцах и моноидах предложено использовать их декомпозицию на подсистемы специального вида, названные кланами. Следует отметить: фак- тические ускорения вычислений получаются только при разложении систе- мы более чем на один клан, что, как правило, имеет место для разреженных систем большой размерности. Существенным для разложения также являет- ся наличие коэффициентов с противоположными знаками в уравнениях сис- темы. В [4] композиция всех кланов системы выполнялась одновременно и сводилась к решению единственной системы композиции. В ряде случаев размерность системы композиции может быть значительной и обусловли- вать общую сложность решения исходной системы. Такая ситуация воз- можна, если количество контактных переменных превышает максимальный размер клана. Цель настоящей работы — формализация задачи последовательной композиции кланов линейных систем и построение эффективных методов ее решения. КОМПОЗИЦИОННОЕ РЕШЕНИЕ ЛИНЕЙНЫХ СИСТЕМ Рассмотрим линейную систему уравнений вида bxA =⋅ , (1) Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 122 где A — матрица коэффициентов размерности nm× ; x — вектор-столбец неизвестных размерности n ; b — вектор-столбец свободных членов раз- мерности m . При 0=b систему называют однородной, а при 0≠b — не- однородной. Как и в работе [4], мы не указываем точно множества значений переменных и коэффициентов. Предполагаем только, что известен метод, позволяющий решить систему (1) и представить ее общее решение в форме yGxx ⋅+′= , (2) где yG ⋅ — общее решение соответствующей однородной системы, а x ′ — минимальное частное решение неоднородной системы (1). Композиционный метод решения системы (1), описанный в работе [4] состоит из следующих этапов: 1. Декомпозиция системы на кланы. 2. Нахождение общего решения для каждого клана. 3. Композиция кланов. Напомним, что кланом названо подмножество уравнений, сформиро- ванное как транзитивное замыкание отношения близости. Два уравнения близки, если они содержат некоторую переменную с одинаковым знаком. Соответствующие переменные названы внутренними переменными клана. В [4] изучена одновременная композиция кланов, т.е. решение одной системы композиции для всех контактных переменных (входящих в кланы с разными знаками). Такой способ композиции целесообразен при решении систем сравнительно небольшой размерности, а также в тех случаях, когда общее число контактных переменных не превосходит размерности наибольшего из кланов. Возможность применения последовательной композиции обсужда- лась в работе [5], где приведены сравнительные оценки сложности одновре- менной и последовательной композиции для вычисления линейных инвари- антов моделей Петри телекоммуникационных протоколов. Показано, что для конкретных моделей протоколов последовательная композиция позво- ляет получить дополнительное ускорение вычислений. Линейную систему вида (1), содержащую m уравнений и n неизвест- ных, будем называть ),( nm -системой. В качестве общей оценки размерно- сти системы, как правило, используют один параметр, равный максимуму количества уравнений и переменных: ),(max nmq = . Если числа т и n от- личаются незначительно, возможно использование одного из них в качестве параметра в оценках сложности. Далее будем предполагать, что сложность системы характеризуется количеством уравнений т . Вычислительная сложность решения систем линейных уравнений су- щественно зависит от области значений переменных и коэффициентов. Так для решения систем в полях известны полиномиальные методы сложности порядка 3q [1]. Для решения систем в кольцах предложены полиномиальные методы порядка 4q [2]. Отметим, что известные методы решения линейных диофантовых систем в целых неотрицательных числах [3] являются экспо- ненциальными. Их временная сложность оценивается q2 . Как показано в работе [6], приведенная оценка является оптимистичной, поскольку слож- Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 123 ность в худшем случае может быть сопоставима с двойной экспонентой. Большинство полученных далее результатов имеют место как для полино- миальных, так и для экспоненциальных методов решения систем. Если раз- личия существенны, то это оговаривается дополнительно. Предположим, что выполнена декомпозиция системы на k кланов. Рассмотрим размерности систем для них. Итак, требуется решить k систем размерности ),( 11 nm , ),( 22 nm ,..., ),( kk nm . Пусть для клана iC получена матрица базисных решений iG , насчитывающая il решений. Для полей и колец имеет место известная оценка количества базисных решений iii rnl −= , где ir — ранг матрицы iA соответствующей системы. Отметим, что при решении систем в целых неотрицательных числах оценка количест- ва базисных решений является нетривиальной задачей. Известны примеры систем [6], содержащих пару уравнений и пять переменных, для которых базис насчитывает 240 решений. Однако такое разрастание базиса на- блюдается только при использовании целочисленных свободных перемен- ных. Базисы для рациональных генераторов либо, что то же самое, при ис- пользовании операции сокращения на общий делитель получаются более компактными. Например, для упомянутой системы он состоит из четырех решений. После нахождения общих решений для кланов необходимо определить систему композиции для контактных переменных. Оценка размерности этой системы ),( ∑ i ilp , поскольку уравнения системы соответствуют контакт- ным переменным, а неизвестными являются свободные переменные базис- ных решений для кланов. Заметим, что nn i i =∑ , pmm i i +=∑ , где p — количество контактных переменных в полученной декомпозиции, 0Xp = , а 0X — множество всех контактных переменных исходной системы. Как отмечено ранее, будем предполагать, считая ∑≈ i ilp , что сложность сис- темы определяется количеством ее уравнений p . Далее считаем характери- стикой размерности системы уравнений клана количество его переменных, а характеристикой размерности композиции кланов — количество используе- мых в ней контактных переменных. Контактные переменные при таком под- счете учитываются дважды для каждого из смежных кланов ii i XXm += , где iX — множество внутренних переменных, iX — множество контакт- ных переменных клана iC . Поэтому, как правило, выполняется неравенство ii mn ≤ . В работе [4] показано, что каждая контактная переменная используется для связи ровно двух кланов. Поэтому для представления декомпозиции удобно применять ориентированный граф, кратность дуг которого соответ- ствует количеству контактных переменных, используемых для связи пары кланов в определенном направлении. В настоящей работе направление свя- Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 124 зей несущественно, поэтому в качестве основного средства представления декомпозиции линейной системы выбран взвешенный неориентированный граф, веса ребер которого равны количеству контактных переменных, ис- пользуемых для связи соответствующих кланов. Численные характеристики вершин определяются парой ),( ii nm . Далее покажем, что в последователь- ной композиции характеристики вершин могут быть опущены. Рассмотрим основные способы организации композиции кланов: 1. Одновременная. 2. Последовательная: а) парная (реберная); б) подграфов. Одновременная композиция изучена в работе [4]. Полученное ускоре- ние вычислений оценивается как pq−2 . Наиболее простой последовательной является парная композиция, при которой пара смежных вершин заменяется одной в результате решения системы, построенной для контактных пере- менных, используемых для связи соседних кланов. Количество контактных переменных равно весу соответствующего ребра. По существу такая опера- ция может быть представлена как слияние (стягивание) смежных вершин графа. Пусть выполняется слияние двух смежных вершин с номерами i и j , представляющими системы уравнений сложности соответственно ),( ii nm и ),( jj nm . Тогда сложность системы, решаемой при парной композиции, равна ),( , jiji llp + , где jip , — количество контактных переменных в ком- позиции кланов iC и jC . При композиции подграфов решается система для выбранного подмножества вершин. Затем подграф, порожденный этими вершинами, заменяется единственной вершиной. Примеры решения систем с помощью одновременной и последовательной композиции описаны в ра- боте [5]. Одновременную композицию целесообразно применять в тех случаях, когда количество контактных переменных не превышает количества внут- ренних переменных максимальной подсети pmi i ≥)(max либо в случаях незначительного превышения. Поскольку обязательным этапом композици- онного метода [4] является решение уравнения для каждого клана, даль- нейшие построения направлены на снижение сложности решения системы для контактных переменных. ПОСЛЕДОВАТЕЛЬНАЯ КОМПОЗИЦИЯ ЛИНЕЙНЫХ СИСТЕМ Для сравнения различных вариантов композиции по отношению к выбран- ному параметру сложности системы введем следующий взвешенный граф, описывающий декомпозицию системы на кланы. Граф декомпозиции — это тройка ),,( WEVG = , где вершины множества }{vV = соответствуют кла- нам Cv ↔ ; ребра VVE ×⊆ соединяют кланы, имеющие общие кон- тактные переменные =∨=∧=∈∃⇔∈ )(())()((: 210 21 xICxOCxIXxEvv Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 125 ))( 12 CxOC =∧= ; функция взвешивания )()(: Ν→Ν→ EVW ∪ сопостав- ляет вершине количество переменных соответствующего клана, а ребру — количество контактных переменных. Кроме того, для каждой вершины вы- полняется неравенство ∑≥ u uvwvw ),()( , поскольку контактные переменные учитываются совместно с внутренними переменными при оценке размера клана. Представим последовательную композицию следующим образом. Пусть задан граф G декомпозиции линейной системы S . Выберем некото- рое подмножество вершин VV ⊆1 , порождающее связный подграф =1H )( 1V= графа G . Заменим его одной вершиной и перейдем к рассмотрению полученного графа 1G . Продолжая процесс, мы преобразуем исходный граф в единственную вершину. Процесс последовательной композиции можно представить следующим образом: k d V d V d V GGGGG k k →→→→= ...210 2 2 1 1 , причем заключительный граф последовательности kG состоит из единст- венной вершины и соответствует завершению процесса композиционного решения. Число id равно сумме весов ребер графа iH и соответствует раз- мерности системы композиции, решаемой на шаге i . Пример коллапса под- графов показан на рис. 1, а на рис. 2 — пример реберного коллапса для по- следовательности подграфов, изображенной на рис. 1. Пусть )(qM сложность решения системы размерности q . Тогда слож- ность последовательной композиции можно оценить как ∑ = = ki idMqY ,1 )()( . Следует отметить, что pd ki i =∑ = ,1 , где p — сумма весов ребер исходного графа (общее количество контактных переменных) ∑= e ewp )( . Таким об- разом, как для полиномиальной, так и для экспоненциальной сложности ре- шения систем последовательная композиция не хуже одновременной. Так как исходный граф декомпозиции системы на кланы сжимается в единственную вершину, по аналогии с процессами, исследуемыми в астро- C4C5 C8 C1 C2 C3C6 C7 7 5 2 7 2 6 2 4 4 3 4 6 3 2 8 C4 C8 C1,3,5,7 C2 C6 7 15 14 4 3 11 C1,2,3,4,5,7,8 C6 14 C1,2,3,4,5,6,7,8H1, 11 H2, 40 H3, 14 H1 H2 H3 d=40 Рис. 1. Пример коллапса подграфов Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 126 физике, процесс последовательной композиции назван коллапсом графа. С точки зрения сложности решения систем нас интересует коллапс, обеспе- чивающий минимальную вычислительную сложность решения исходной системы. Такой коллапс назовем оптимальным. В зависимости от того, рас- сматриваются ли методы полиномиальной либо экспоненциальной сложно- сти, имеются два основных варианта постановки соответствующей оптими- зационной задачи: I. ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ > = → ∑ ∑ .0 , ,min i i i i u i d qd d II. ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ > = → ∑ ∑ .0 , ,min i i i i d d qd u i (3) Как правило, для полиномиальных методов в задаче I рассматриваются 3≥u , а для экспоненциальных методов в задаче II — 2≥u . В соответствии с теорией сложности в оценках экспоненциальных функций слагаемые низ- ших степеней могут быть опущены. Таким образом, для экспоненциальных методов становится актуальным параметр ( )i i dd max= , названный шириной коллапса и равный максимальному из чисел id . Тогда сложность последо- вательной композиции можно оценить как du , а дополнительное ускорение вычислений по сравнению с одновременной композицией как dpu − . Хотя для методов полиномиальной сложности аналогичные упрощения являются довольно грубыми, выражение udk можно рассматривать как оценку верх- ней границы сложности. В ряде случаев в качестве квазиоптимального кол- лапса целесообразно рассматривать коллапс, имеющий минимальную ши- рину. Действительно, при произвольном разбиении числа p на k частей как в задаче I, так и в задаче II, оптимальным является равномерное разбие- ние kpdi /= . Таким образом, снижение максимума последовательности id способствует приближению к равномерному разбиению. C4C5 C8 C1 C2 C3C6 C7 7 5 2 7 2 6 2 4 4 3 4 6 3 2 8 C C4C5 C8 C1 C2 C3,7C6 2 7 5 7 2 4 3 2 8 9 6 C 6 C4C5 C8 C1,3,7 C2 C6 8 7 9 2 4 3 2 8 7 C 6 C4 C8 C1,3,7 C2 C6 14 15 11 4 3 7 C3C7,4 C1C3,5 C1C5,2 15 C4 C8 C1,2,3,5,7 C6 7 14 4 14 C 4 C8 C1,2,3,4,5,7 C6 11 14 C1C8, 11 C C4 C8 C1,3,5,7 C2 C6 7 15 14 4 3 11 C C1 6 14 C1C4,14C1C2,15 C1C8,14 C1,2,3,4,5,7,8 C1C6,14 C12,3,4,5,7,8 d=15 C6 Рис. 2. Пример реберного коллапса Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 127 Сравнительные оценки сложности различных способов организации последовательного коллапса приведены в табл. 1. Композиция подграфов соответствует последовательности на рис. 1. Реберная композиция 1 соот- ветствует последовательности на рис. 2. Реберная композиция 2 соответст- вует оптимальному коллапсу. Реберная композиция 3 соответствует наиху- дшему коллапсу. Графические изображения реберных композиций 2, 3 описаны в работе [5]. Следует отметить, что использование ширины коллап- са позволяет получить простые и достаточно хорошие оценки сложности. Заметим, что ускорения вычислений для наилучшего коллапса по сравне- нию с одновременной композицией имеют порядок 1510 для методов экспо- ненциальной сложности. Т а б л и ц а 1 . Сравнительные оценки сложности композиционного реше- ния систем Сложность решения систем Полином Экспонента Компози- ция Последовательность d 4d ∑ 4 id d2 ∑ id2 Подграфы H1,11–H2,40–H3,14 40 2,56·106 2,61·106 1,1·1012 1,99·1012 Реберная 1 C3C7,4–C1C3,5–C1C5,2– C1C2,15–C1C4,14– C1C8,11–C1C6,14 15 5,06·104 1,43·105 3,28·104 6,76·104 Реберная 2 C2C5,8–C1C2,9–C1C4,8– C1C7,9–C1C8,11– C1C6,9–C1C3,11 11 1,46·104 5,72·104 2,05·103 6,14·103 Реберная 3 C5C6,2–C1C3,2–C1C4,2– C1C8,4–C5C7,4–C1C2,7– C1C4,44 44 3,75·106 3,75·106 1,76·1013 1,76·1013 Одновре- менная C1C2C3C4C5C6C7C8,65 65 1,79·107 1,79·107 3,69·1019 3,69·1019 При выборе способа реализации последовательной композиции следует рассмотреть два основных вопроса: 1. Может ли применение не минимальных кланов ускорить процесс решения. 2. Может ли композиция подграфов быть более эффективной, чем пар- ная композиция. Выбор не минимальных кланов предполагает решение единственной системы уравнений для составного клана без решения промежуточных сис- тем для внутренних минимальных кланов. Композиция подграфов предпо- лагает одновременную композицию всех вершин подграфа. Полученные в результате графы совпадают. Отличие состоит только в сложности решения системы для подграфа, которая в одном случае решается обычными метода- ми (без применения композиции), а в другом — с помощью одновременной композиции. Справедливы следующие оценки сложности: подграф без компо- зиции ∑ ∑ ∈ ∈ −= Hv He ewvwq )()( ; подграф с одновременной композицией ))(),(max(max ∑ ∈∈ = HeHv ewvwq . Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 128 Лемма 1. Для любого графа декомпозиции выполняется неравенство ∑ ∑∑ −≤ )()())(),((maxmax ewvwewvw . (4) Доказательство. Неравенство (4) можно представить в виде эквива- лентной системы неравенств ⎪⎩ ⎪ ⎨ ⎧ −≤ −≤ ∑ ∑∑ ∑ ∑ ).()()( ),()()(max ewvwew ewvwvw Докажем выполнение каждого из неравенств системы. В соответствии с определением графа декомпозиции ∑≥ u uvwvw ),()( . Просуммируем неравенство по всем вершинам графа ∑∑∑ ≥ v uv uvwvw ),()( . Учитывая известное из теории графов [7] равенство ∑∑∑ = ev u ewuvw )(2),( , (5) получаем ∑∑ ≥ ev ewvw )(2)( . И, далее ∑ ∑∑ −≤ )()()( ewvwew . Справедливость второго из неравенств доказана. Докажем справедли- вость первого. Покажем, что неравенство ∑ ∑−≤′ )()()( ewvwvw выполняется для произвольной вершины Vv ∈′ графа G . Имеем ∑∑ −≤ ′≠ )()(0 ewvw vv . Для доказательства неравенства ∑∑ ′≠ ≤ vv vwew )()( будем учитывать тот факт, что вес ребра уже содержится в весе каждой ин- цидентной ему вершины таким образом, что ∑≥ u uvwvw ),()( . Тогда ∑∑∑ ′≠′≠ ≥ vv uvv uvwvw ),()( . Учитывая соотношение (5), получаем Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 129 ∑∑∑∑∑∑ ′≠′′≠′≠ +=+= vvvvvvv u ewewewewuvw )()()()(2),( . Заметим, что индекс суммирования ребер задан множеством инцидент- ных вершин. Принимая во внимание неравенство 0)( ≥∑ ′≠vv ew , получаем ∑∑ ≠ ≤ uv vwew )()( , что и требовалось доказать. Следствие. Использование минимальных кланов в процессе последо- вательной композиции является более эффективным. Таким образом, решение систем уравнений для всех минимальных кла- нов является обязательным этапом. Поэтому в дальнейшем изложении веса вершин графа декомпозиции могут быть опущены. В качестве графа деком- позиции на кланы выберем взвешенный граф ),,( WEVG = , где отображе- ние ΝEW →: задает кратность его ребер. Проанализируем последовательный коллапс графа путем слияния (кол- лапса) подграфов, порожденных указанным множеством вершин. Не огра- ничивая общности, рассмотрим связные подграфы. В качестве основного параметра коллапса примем его ширину d . Задача состоит в построении такой последовательности стягивания подграфов, которая обеспечит мини- мальную ширину коллапса. Возможны два упомянутых ранее способа орга- низации этого процесса: одновременный и последовательный. Последова- тельный коллапс может быть организован как парный (реберный) либо как коллапс произвольных подграфов, порожденных указанным множеством вершин. Лемма 2. Парный (реберный) коллапс не хуже произвольного коллапса подграфов. Доказательство. Во-первых, результат применения реберного коллап- са подграфа совпадает с результатом применения одновременного коллапса по отношению к окружению подграфа. Т.е. в обоих случаях будет получен один и тот же граф. Отличие состоит в ширине коллапса выбранного подграфа. Так как ширина одновременного коллапса известна и равна сумме весов ребер, не- обходимо оценить ширину реберного коллапса подграфа. Покажем, что в результате реберного коллапса не может появиться ребро веса, превышаю- щего сумму весов всех ребер. Выберем произвольное ребро Ee ∈′ . При слиянии вершин веса ребер, инцидентных общей вершине, суммируются и, следовательно, сумма весов ребер полученного графа равна ∑ ′− e ewew )()( . Эта сумма и является верхней границей оценки сложности реберного коллапса полученного графа. Продолжение коллапса не приведет к появле- Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 130 нию ребра большего веса, а ширина реберного коллапса равна максималь- ному весу ребра. Поэтому ∑ ∑ ′≠ +′= e ee ewewew )()()( . Тогда ∑ ∑ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≥ ′≠e ee ewewew )(),(max)( . Таким образом, в дальнейшем будем рассматривать реберный коллапс как более эффективный способ композиции при экспоненциальной сложно- сти решения системы. Следует отметить, что приведенные оценки сложно- сти являются асимптотическими. В частных случаях при небольшой раз- мерности кланов, когда конкретные значения оценок экспоненциальной сложности сопоставимы с полиномиальными сомножителями, коллапс под- графов может иметь меньшую вычислительную сложность. ОЦЕНКИ ШИРИНЫ РЕБЕРНОГО КОЛЛАПСА Пусть задан взвешенный граф ),,( WEVG = . Не ограничивая общности, считаем, что G связный, иначе выполняем коллапс по компонентам. Опре- делим операцию реберного коллапса eG \ для некоторого Ee∈ следующим образом. Пусть 21vve = . Тогда ),,(\ WEVGeG ′′′=′= , где vvvVV ∪)\( 21= ( v — новая вершина, представляющая собой слияние (коллапс) вершин 21,vv ), т.е. ∪∪∪ ))},{},{(\( 221121 EuvVuuvEuvVuuvvvEE ∈∈∈∈=′ },,{ 21 EuvEuvVuvu ∈∨∈′∈∪ ⎪ ⎩ ⎪ ⎨ ⎧ ∉∧∈ ∉∧∈ ∈∧∈+ =′ . , , ),( ),( ),()( )( 12 21 11 2 1 21 EuvEuv EuvEuv EuvEuv uvW uvW uvWuvW vuW Таким образом, при слиянии вершин ребра объединяются ребра, инци- дентные обеим вершинам. Утверждение 1. Операция реберного коллапса сохраняет связность графа. Утверждение 2. Верно следующее равенство для суммы весов ребер: )()()( ewGSGS +′= . В соответствии с терминологией [7], граф, в котором kV = , а pE = , будем называть ),( pk -графом либо k -графом. Так как при выполнении операции реберного коллапса объединяется пара смежных вершин графа, то реберный коллапс всего графа состоит в последовательном выполнении Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 131 )1( −k операций реберного коллапса. Процесс последовательного реберного коллапса взвешенного k -графа — это последовательность )1( −k операций реберного коллапса k kk eGGeGGeGGGG \\\ 21 2 12 1 010 −− =→⋅⋅⋅→=→=→= . Заметим, что полученный в результате граф 1−kG состоит из единст- венной вершины. Это вполне соответствует названию процесса, сжимающе- го исходный граф в вершину. В качестве основного параметра коллапса будем рассматривать его ширину, равную максимальному весу стягиваемо- го ребра. Ширина коллапса — это максимальный вес ребра в процессе кол- лапса )(max)( ewd e σ σ ∈ = . Выбор различных последовательностей ребер keee ...21 в общем случае приводит к различным значениям ширины коллапса. Оптимальным процес- сом коллапса будем называть последовательность ребер, обеспечивающую минимизацию общей сложности решения систем (4). Квазиоптимальным процессом коллапса будем называть коллапс, имеющий наименьшую шири- ну. Отметим, что минимальная ширина коллапса является свойством задан- ного графа. Введем рекуррентное определение минимальной ширины кол- лапса. Обозначим )(Gd ширину реберного коллапса графа G . Тогда ⎪⎩ ⎪ ⎨ ⎧ = = )),\(),(max(),( ),,(min)( eGdeweGd eGdGd e где функция двух аргументов ),( eGd определяет минимальную ширину ре- берного коллапса графа G при условии, что первоначально будет выполнен коллапс ребра e . Реберный коллапс представляет собой комбинаторную задачу, для ре- шения которой применим универсальный метод полного перебора всех воз- можных последовательностей ребер. Пример дерева полного перебора ре- берного коллапса графа показан на рис. 3. Заметим, что минимальная ширина коллапса составляет 14, максимальная 23, а сумма весов ребер (ши- рина одновременного коллапса) равна 35. Точное число различных последо- вательностей ∏ −= = 2,0 )( ki iEGK . На каждом шаге стягивается пара смежных вершин, а наибольшее количество смежных вершин имеет место в полном графе. Количество ребер полного k -графа равно 2 )1( −kk . Тогда =)(ˆ GK 1 2 1 ,2 2 )!( 2 )!1(! 2 )1( −− = ⋅ = − = − = ∏ kk ki k kkkii . Например, 9106,2)10(ˆ ⋅=K , а =)20(K̂ 29107,5 ⋅= , 284104,1)100(ˆ ⋅=K . Таким образом, необходим поиск эффектив- ных методов решения задачи оптимального (квазиоптимального) реберного коллапса. Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 132 Теорема 1. Ширина коллапса ациклического графа равна максималь- ному весу ребра. Доказательство. Операция реберного коллапса ациклического графа приводит к получению нового ациклического графа, содержащего количест- во ребер меньшее на единицу, чем исходный граф. Кроме того, эта операция не изменяет веса оставшихся ребер. Таким образом, ширина коллапса не зависит от порядка выбора ребер и равна максимальному весу ребра. Любая простая цепь может быть заменена ребром минимального веса при ширине ее коллапса, равного максимальному весу ребра. Это соответст- вует выбору на шаге коллапса ребра максимального веса. Не ограничивая общности, можно рассматривать компактные графы, не содержащие про- стых цепей и висячих вершин. Утверждение 3. Если граф имеет точки сочленения, то ширина коллап- са равна максимальной ширине среди его двусвязных компонентов (блоков). Теорема 2. Ширина коллапса простого цикла равна )((max 21,, ew eee , ))()((min 21 ewew + . Доказательство. Простой цикл преобразуется в цикл меньшей размер- ности до тех пор, пока не будет получен треугольник. При коллапсе тре- угольника будет получен граф, состоящий из одного ребра, вес которого равен сумме весов ребер, отличных от стягиваемого. Таким образом, шири- на коллапса определяется, с одной стороны, максимальным весом ребра пе- ред стягиванием треугольника, а с другой — весом последнего ребра. Сле- довательно, нижней границей ширины является как вес максимального ребра, так и суммарный вес пары ребер. Теорема 3. Оптимальный коллапс простого цикла соответствует выбо- ру на шаге коллапса ребра максимального веса. Доказательство. Коллапс простого цикла продолжается без изменения весов ребер до тех пор, пока не будет получен треугольник. Выбор макси- мального ребра гарантирует, что при получении треугольника останется три AD B C 8 11 7 D C 15 8 7 AB A D 9 5 13 CD A B 9 14 5 BC A B D C7 8 5 9 ADC B 19 ADB 19 15 AD BC 18 CD 23 AB C 15 ABD D ABC 22 A BCD 14 AD 18 BC D 22 ABC ACD B19 CD AB 23 BCD A 14 d=19 d=15 d=18 d=23 d=15 d=22 d=14 d=18 d=22 d=19 d=23 d=14 AD,9 AB,5 BC,8 CD,7 ADC,7 BC,8 ADB,11 CD,7 ABD,15 ABC,8 BCD,13 AD,9 ABC,5 ACD,9 AB,5 BCD,14 6 BD C 14 15 A BDC 14 A ABD C15 d=15 d=15 BDC,15 ABD,14 BD,6 15 18 23 15 22 15 15 14 18 22 19 23 14 Рис. 3. Пример дерева полного перебора реберного коллапса Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 133 ребра минимального веса. Кроме того, при коллапсе треугольника выбор ребра максимального веса обеспечит минимальный суммарный вес ос- тавшихся ребер. Действительно, имеет место соотношение +)((min 1 , 21 ew ee )(min)(min))( 212 121 eeew eee ≠ +=+ . Графы, образованные в результате стягивания ребер, называют мино- рами исходного графа [7]. Рассмотрим решетку миноров, полученных в ре- зультате коллапса, которую назовем частичной решеткой коллапса. Она состоит из )1( −k уровней. На i -м уровне точками представлены ребра те- кущего графа iG . Линии соответствуют отношению частичного порядка << ребер текущего и предыдущего уровней таким образом, что iiiiiii eeeeeee 21 1 31 1 3 1 31 +=∨=⇔<< +++ . Частичная решетка является наглядным представлением процесса кол- лапса. В соответствии с определением операции коллапса на каждом шаге стягивается одно ребро. Если концы этого ребра не имеют общих смежных вершин (не формируют треугольников вместе с другими ребрами), то на следующем уровне присутствуют все ребра за исключением стягиваемого. Если ребро образует один либо несколько треугольников, то каждая пара ребер треугольника заменяется одним ребром. Рекуррентное соотношение для числа ребер tpp ii −−= − 11 , где t — количество треугольников, опре- деляемых стягиваемым ребром. Решетка иллюстрирует взаимосвязи ребер. Таким образом, каждое ребро на шаге коллапса представляет собой либо ребро исходного графа, либо сумму некоторых ребер. Решетки двух различ- ных последовательностей коллапса (рис. 3), изображены на рис. 4. Стяги- ваемые ребра помечены диагональным крестом. Утверждение 4. Каждое ребро на шаге коллапса является суммой не- которых ребер исходного графа. Таком образом, ширина коллапса равна весу ребра, полученного на не- котором шаге. Такое ребро будем называть критическим ребром коллапса. Критическое ребро либо просто стягивается в процессе коллапса, либо оста- ется его последним ребром. Верхние и нижние оценки ширины коллапса могут быть использованы при поиске оптимального коллапса с помощью метода ветвей и границ [8]. В соответствии с определением ширины реберного коллапса AB BC BD CD e1 e5e2 e3 e4 5 6 7 14 DA e6e7 8 13 9 AB BC BD CD e1 e5e2 e3 e4 5 6 7 23 DA e7e6 8 14 9 a б Рис. 4. Примеры частичных решеток коллапса: а — BC, BCD, ABCD; б — CD, AB, ABCC Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 134 ∑≤≤ ee ewGdew )()()(max . Построим более точные верхние оценки ширины коллапса. В лемме 2 была представлена оценка ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ≤ ∑ ′≠ee ewewGd )(),(max)( . Действительно, по крайней мере, одно ребро будет аннулировано и ширина коллапса оставшегося графа не превысит сумму его ребер. Продол- жая описанный процесс не более )1( −k раз, можно прийти к следующей оценке. Пусть )(maxmax eww Ge∈ = — максимальный вес ребра исходного графа, а )(minmin eww Ge∈ = — минимальный. На первом шаге не может появиться реб- ро большего веса, чем max2 w , на третьем maxmaxmax 422 www =+ и так да- лее. Получим рекуррентное соотношение ⎪⎩ ⎪ ⎨ ⎧ −== = − .2,1,2 , max 1 max maxmax 0 kiww ww ii Тогда max2max 2 2)( wwGd k k − − =≤ . С другой стороны, после первого шага сумма весов ребер оставшейся части графа не превысит ∑ − min)( wew , после второго ∑ − min2)( wew . Продолжая оценки до завершения коллапса, получаем ( )∑ −−≤ − minmax2 )2()(,2max)( wkewwGd k . Хотя оценка является довольно грубой, она дополняет ранее получен- ные. Для более точных оценок рассмотрим процесс добавления ребер, со- единяющих пару несмежных вершин. Изучим влияние этой операции на ширину коллапса. Теорема 4. Добавление ребра, соединяющего пару несмежных вер- шин графа, увеличивает ширину коллапса не более чем на вес добавленного ребра. Доказательство. Пусть ширина коллапса графа G равна )(Gd и дос- тигается с помощью последовательности σ . Рассмотрим граф eG + и вы- полним его коллапс с помощью той же последовательности σ . Пусть 21vve = . При выполнении операции коллапса пометим символом 1v все верши- ны, стягиваемые с вершиной 1v , и символом 2v все вершины, стягиваемые с 2v . Во-первых, вершины 21,vv несмежные в исходном графе. Во-вторых, граф связный. Следовательно, на некотором шаге коллапса получаем вер- шину u , смежную как с 1v , так и с 2v . Стягивание этой вершины в графе G Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 135 с одной из вершин 21,vv приводит к образованию ребра 21vve =′ . В даль- нейшем это ребро может участвовать в образовании критического ребра ли- бо будет просто аннулировано. Рассмотрим выполнение рассмотренной операции в графе eG + . Пе- ред получением треугольника, образованного ребром e и некоторой верши- ной u , процесс не отличается от ранее рассмотренного. При стягивании вершины u с одной из вершин 21,vv вместо ребра веса )(ew ′ будет полу- чено ребро веса )()( ewew +′ . Далее это ребро либо войдет в критическое ребро коллапса, либо будет просто аннулировано. В первом случае ширина коллапса увеличится на величину )(ew , во втором случае не изменится. Для получения более точных верхних оценок рассмотрим процесс до- бавления недостающих ребер к некоторому остову R графа G . Поскольку ширина коллапса ациклического графа в соответствии с теоремой 1 равна максимальному весу ребра, то может быть дана следующая оценка ширины коллапса. Теорема 5. Ширина коллапса не превышает сумму веса максимального ребра остова и весов оставшихся ребер ∑ ∉∈ +≤ ReRe ewewGd )()(max)( , где R — остов графа G . Для улучшения оценки можно выбирать остов, содержащий ребра мак- симального веса, таким образом, чтобы минимизировать сумму, и в качестве хорошего приближения рассматривать стандартную задачу выбора остова максимального веса [7]. Заметим, что количество оставшихся ребер равно цикломатическому числу графа 1)( +−= kpGν . Тогда оценка представля- ется как maxmax )2()1)(()( wkpwGGd +−=+≤ ν . ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ОПТИМАЛЬНОГО КОЛЛАПСА Оптимальный коллапс для полиномиальной и экспоненциальной оценок сложности, а также квазиоптимальный коллапс минимальной ширины — это задачи, для решения которых в предыдущем разделе предложено при- менить универсальный метод полного перебора, имеющий экспоненци- альную сложность по отношению к размеру графа. Однако являются ли указанные задачи NP-полными? Построим и статистически обоснуем эври- стические алгоритмы решения задач оптимального коллапса, основанные на одношаговых стратегиях выбора стягиваемого ребра. Применение таких ал- горитмов целесообразно также потому, что отсутствуют точные оценки ко- личества базисных решений подсистем композиции. В соответствии с результатами, полученными для простой цепи и про- стого цикла, можно предложить выбор ребра максимального веса на шаге коллапса: первое либо случайное ребро максимального веса в случае, если имеется несколько таких ребер. Алгоритм состоит в простой реализации операции коллапса в соответствии с определением, дополненной правилом Д.А. Зайцев ISSN 1681–6048 System Research & Information Technologies, 2006, № 2 136 выбора ребра максимального веса. Сложность такого алгоритма оценивается как 2kp . Действительно, необходимо выполнить 1−k шагов и на каждом шаге следует обработать не более p ребер, для которых при коллапсе тре- угольников обрабатывается не более p смежных ребер. Следует отметить, что описанный «жадный» алгоритм не всегда гарантирует оптимальный коллапс, хотя и обеспечивает достаточно хорошее приближение. Так для графа, изображенного на рис. 3, «жадный» алгоритм дает ширину 15, в то время как оптимальная ширина равна 14. Примеры коллапса графа (см. рис. 1) с использованием выбора максимального, минимального и слу- чайного ребра приведены в работе [5]. Для сравнения различных правил выбора ребра на шаге коллапса гене- рировались случайные графы и выполнялся их реберный коллапс. Сравни- вался выбор максимального, минимального и случайного ребра на шаге. Полученные результаты приведены в табл. 2. Для построения табл. 2 использованы случайные равномерно распреде- ленные веса ребер в диапазоне от 4 до 20. Использование других диапазонов приводит к другим абсолютным величинам, но сохраняет процентные соот- ношения. Оценивалась ширина коллапса, а также сложность последователь- ной композиции для полиномиальных и экспоненциальных методов реше- ния систем. Можно сделать вывод, что худшим является выбор ребра минимально- го веса. Он приближается к случайному выбору ребра с ростом количества вершин. Лучшим выбором на шаге является выбор ребра максимального веса, который обеспечивает существенно меньшую ширину коллапса. Т а б л и ц а 2 . Сравнение коллапсов случайных графов Ширина последовательного коллапса Максимальное ребро Случайное ребро Минимальное ребро Количе- ство вершин графа Плот- ность графа, % Ширина одновре- менного коллапса Ширина % Ширина % Ширина % 20 442 35 7,9 191 44,6 231 52,3 40 869 66 7,6 367 42,2 533 61,3 60 1372 102 7,4 651 47,4 829 60,4 20 80 1825 160 8,8 876 48,0 990 54,2 20 1836 73 4,0 632 34,4 1002 54,6 40 3699 139 3,8 1664 45,0 2133 57,7 60 5539 214 3,9 2665 48,1 2948 53,2 40 80 7354 314 4,3 3608 49,0 3908 53,1 20 11602 160 1,4 4827 41,6 5829 50,2 40 22973 316 1,4 7617 33,2 12341 53,7 60 34334 501 1,5 13282 38,7 17559 51,1 100 80 45582 754 1,7 17144 37,6 23008 50,5 20 46073 288 0,63 19673 42,7 23781 51,6 40 91715 612 0,67 42260 46,0 91715 50,5 60 137684 997 0,72 67609 49,1 68957 50,0 200 80 183652 1486 0,81 91015 49,6 91669 49,9 Последовательная композиция кланов линейных систем Системні дослідження та інформаційні технології, 2006, № 2 137 ЗАКЛЮЧЕНИЕ В настоящей работе предложен новый метод решения линейных систем с помощью последовательной композиции их кланов. Применение метода це- лесообразно в случае, если количество контактных переменных превы- шает максимальный размер клана. По сравнению с ранее изученной одновременной композицией кланов последовательная композиция позволяет получить дополнительные ускоре- ния вычислений путем решения последовательности систем существенно меньшей размерности. Задача формализована в терминах теории графов и названа оптимальным коллапсом взвешенного графа. Получены оценки верхней и нижней границ ширины коллапса. Построен и статистически обоснован эвристический алгоритм оптимального коллапса полиномиаль- ной сложности. ЛИТЕРАТУРА 1. Годунов С.К. Решение систем линейных уравнений. — М.: Наука, 1980. — 177 с. 2. Схрейвер А. Теория линейного и целочисленного программирования. В 2-х т. — М.: Мир, 1991. — 726 c. 3. Крывый С.Л. О некоторых методах решения и критериях совместимости сис- тем линейных диофантовых уравнений в области натуральных чисел // Ки- бернетика и системный анализ. — 1999, № 4. — С. 12–36. 4. Зайцев Д.А. Решение линейных систем с помощью декомпозиции // Системні дослідження та інформаційні технології. — 2005. — № 2. — С. 131–143. 5. Zaitsev D.A. Functional Petri Nets, Universite Paris-Dauphine, Cahier du Lamsade 224, Avril 2005. — 62 p. (www.lamsade.dauphine.fr/cahiers.html). 6. Зайцев Д.А. К вопросу о вычислительной сложности метода Тудика // Искусст- венный интеллект. — 2004. — № 1. — С. 29–37. 7. Татт У. Теория графов. — М.: Мир, 1988. — 424 с. 8. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — Киев, Наук. думка, 1988. — 472 с. Поступила 1.09.2005

Последовательная композиция кланов линейных систем

Institution

Ähnliche Einträge