Разряженные матрицы. Р. Тьюарсон, страница 14

Эти методы обеспечивают отсутствие нулей в ленте, если матрица допускает такое преобразование, или приводят к матрице со значением шах; рь достаточно близким к минимуму р. Первый метод Этот метод особенно полезен для задач, в которых исходная нумерация пространственной системы вершин помеченного графа определяет ширину ленты соответствующей матрицы (например, структурные системы конечных элементов, модели тепловых цепей с сосредоточенными параметрами, электрические цепи, системы трубопроводов, конечно-разностные урав- 92 - Гл. д. 11ополнительные методы минимизации памяти пения энергетических систем).

На рис. 3.8.1 приведен простой пример, иллюстрирующий уменьшение шири. ны ленты матрицы путем перенумерования вершин соответствующего ей графа. После изменения номеров вершин графа 1е, который соответствует матрице В, получается граф Й, которому соответствует матрица В, В матрицах В и Я единицы обозначены знаками умножения, нули — точками. Заметим, что ширина ленты в матрице В равна 9, в то время как в матрице В она д х х ° ° х х хх ° ° ° ххх ° ° ° ххх х ° ° х х х хх х х х ° х ° х ° х ° х ° х х ° ° ° х х Ряс.

3.8.1. Перенуыерацяя вершин яля уменьшения ширины ленты. равна всего 5. Метод перенумерования вершин графа с целью уменьшения ширины ленты в соответствующей матрице может быть в алгоритмической форме описан следующим образом (Розен (!968)).

1. Поместить 1, 2, ..., и в список вершин (зт1.), в котором имеется п ячеек. Определить максимальную ширину ленты в матрице В и две вершины, которые приводят к ней. Если максимум имеет место для нескольких пар вершин, то выбрать любую нз них (если шахт 1)е = рр, то р и р — ()р составляют пару вершин). Если вершина с ббльшим номером может быть переставлена с вершиной с меньшим номером для уменьшения ширины ленты (для некоторого 1 «р имеет место р;+ (р — т) ( ~р), то перейти к шагу 7. 2.

Если вершина с меньшим номером может быть переставлена с вершиной с ббльшим номером для уменьшения ширины ленты, то перейти н шагу 7, 8.8. Ленточная форма 3 Если вершина с ббльшнм номером может быть переставлена с вершиной с меньшим номером так, что сохраняется ширина ленты, то перейти к шагу 6, 4, Если вершина с меньшим номером может быть переставлена с вершиной с ббльшим номером так, что сохраняется ширина ленты, то перейти к шагу 6. (Замечание. Целью шагов 3 и 4 является изменить расположение вершин без увеличения ширины ленты так, чтобы могли быть выполнены дополнительные успешные церестановки на первом и втором шагах.) 5, ДаАьнейшие перестановки невозможны, и теперь матрица В имеет ленточную форму и ечтхв будет 1-и столбцом матрицы перестановок Р Ц = 1, 2,...

„,, и), где Ч).(1) — целое число 1'-й ячейки списка вершин чг1. Тогда А = РАР'. Останов. 6. Если на 3-м и 4-м шагах произведено максимальное число непрерывных перестановок или снова выбраны для перестановки две вершины, ранее пере- ставленные друг с другом, то перейти к шагу 5. 7.

Произвести указанную перестановку вершин, а именно переставить соответствующие элементы в списке вершин Ч1 и строки и столбцы матрицы В, и вернуться к шагу 1. Второй метод Другая схема изменения номеров вершин, приводящая, к уменьшению ширины ленты соответствующей матрицы, описывается следующим алгоритмом (Катхилл и Мак-Ки (1969)). !. Для каждой вершины 1 графа й, соответствующего матрице В, вычислить ее степень рь равную общему числу недиагональных единиц бй строки матрицы В.

Затем выбрать какую-либо вершину 1ь для которой р, =ш)п, р„и пометить эту вершину первой. На рис. 3.8.2 вершина 1' помечена 1. 2. Присвоить вершинам, смежным с вершиной 1, новые номера, начиная с 2ч в порядке возрастания их :тепеяей (еслн степени некоторых смежных вершин 94 Гя. Д Допоянитеяьные методы минимизации памяти совпадают, то выбирать любую из них). Эти вершины относят к первому уровню.

На рис. 3,8.2 вершинаи 2*, 4* и 9е присвоены номера соответственно 2, 3 и 4, 3, Повторить эту процедуру последовательно длх каждой из вершин первого уровня — это значит спер. ва для вершины 2, затем для вершины 3 и т. д. Не рис. 3.8,2 'еще неперенумерованной вершиной, смежЛ 1 3 7 Рис. 3.8.2. Пример схемы перенуиерации вершин ной с вершиной 2, является вершина 3' — она стано.

антея вершиной 6. Смежными с вершиной 3 (которая сначала имела номер 4") являются вершины 6*, 5* и 10*. Вершина 6* имеет меньшую степень, чем вершина 6', степень которой в свою очередь меньше степени вершины 1О"; поэтому присвоим этим вершинаи соответственно номера 6, 7 и 8. Заметим, что вершины 5, 6, 7 и 8 связаны с вершиной 1 путем длины 2 и от.

носятся ко второму уровню. 4. Повторить вышеизложенную процедуру для 'вершин каждого следующего уровня, пока все и вершин графа 14 не будут перенумерованы. Если й состоит из двух или более несвязных подграфов, то процедура заканчивается, как только все вершины в подграфе перенумерованы. В этом случае необходимо выбрать начальную вершину в каждом из несвязных 3.0. Леитопяая форма подграфов и повторить шаги 2, 3, 4 для каждого из них. б Наконец, переставить строки и столбцы матрицы В (или А) в соответствии с новыми номерами вершин для получения В (или Л). Матрицы В н В представлены на рис.

3.8.3. Они соответствуют исход- В ' 2'3'4' бх б' 7* 0* 5'10' ному графу и перенумерованному .графу, представленным на рис. 3.8.2. Заметим, что ширина ленты в матрице В равна !7, а в агатрице  — 11. Описанная схема перенумерации не приводит, вообще говоря, к минимальной ширине ленты. Однако можно построить другую последовательность номеров вершин, если в качестве исходной выбрать другую вершину й на шаге 1, такую, для которой 1 Рппп 1 Ь 1 поп+ я Рылах' « . . +— где рпип и р „соответственно минимальное н максимальное значения рь и если на любом из последующих шагов выбирать другой порядок номеров вершин данного уровня, когда степени вершин совпадают.

для преобразования матрицы В к матрице В 3" 4' 5* б' 1О' В 12345б70510 1 2 3 4 5 б 7 0 0 10 Рис. З.З.З. Матрица и и ее преобразованная форма В. 96 Гм 8. Дополнительные методы минимизации иемлти выбирается такая последовательность номеров вершин, которая приводит к меньшей ширине ленты. Разумеется, имеет смысл построить только небольшое число таких последовательностей, так как в противном случае процесс отнял бы неоправданно много времени.

Третий метод Итеративный метод, минимизирующий среднюю ширину ленты Р= — „~Рт, где р! определяется формулой (3.8.2), основан на перестановках строк (столбцов), как н первый метод, и может быть представлен в виде следующего алгоритма (Эйкиуз и Утку (1968)). 1. Переставить две последовательные строки (и соответствующие столбцы) матрицы В, если а) уменьшается, б) р остается без изменения, но строка с меньшим числом единиц внутри лентв! расположится в результате перестановки дальше от центральной строки матрицы В.

Регистрировать все перестановки в списке перестановок строк К1. (Первоначально список К! содержит целые 1, 2... и, и всякий раз, когда осуществляется перестановка строк, перестав. ляются и элементы списка !х1.) 2. Делать перестановки, производя сравнения строк полными циклами. (Полный цикл состоит из и — 1 шагов. На каждом шаге сравниваются две последовательные строки и производится перестановка, если условия на шаге 1 удовлетворяются, Шаги выполняются в такой последовательности: (1,2), (и, п — 1), (2, 3), (л — 1„ л — 2)... и так до центральной строки.) 3. Остановиться, если не сделано ни одной перестановки или не происходит уменьшения р в течение эмпирически установленного числа циклов, равного с 88.

Ленточная форма 97 8+ и/100. Вектор енин является 1-м столбцом матрицы перестановок Р (1 = 1, 2, ..., и), где ьт1(1) — содержимое 1'-й ячейки списка перестановок бтрок ьт1. Четвертый метод уменьшении ширины ленты Назовем обычное скалярное произведение (не будево) двух строк данной матрицы В длиною их иерагиьеяия. Пусть ть обозначает сумму длин пересечения ь.й строки со всеми строками матрицы В.

Если мы предположим, что матрица В имеет ленточную форму Рис. 3.8.4. Пересечение строк ленточной матрицы. с шььрььььой ленты 2р+ 1, то число единиц в заштрихованных областях на рис. 3.8.4 представляет собой значения тч для трех групп значений ь. Первая заштрихованная площадь, соответствующая ь, (1 = ( ьь < ~)+ 1), увеличивается вместе с ьь.

Это же относится и к заштрихованной плошади, соответствующей ь,. Заштрихованная площадь, соответствующая ьз, остается той же при увеличении ьз от 2р+ 1 до и — 21). Кроме того, все площади, соответствующие 1ь меньше площадей, соответствующих ь,, которые в свою очередь меньше площадей, соответствующих 1з. Поэтому если молчаливо допустить, что неднагональные единицы внутри ленты распределены случайным образом, то значения всех тн будут, вообще говоря, увеличиваться с увеличением ь от 1 до 2р+! и затем оставаться теми же до значения ь, равного и — -2р, Исходя из симметрии матрицы В, легко заключить, 4 р. Тьюьрсоа 98 Гл.