LEC-29 (Материалы к лекциям), страница 2

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



Для ленточных методов также используются методы с внешней памятью и так называемые ленточные методы с минимальной памятью.

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

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

12.4.1.1. Алгоритм Розена

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

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

1. Пометить 1,2,...,n список вершин (VL), в котором имеется n ячеек. Определить максимальную ширину ленты в матрице В и две вершины, которые приводят к ней. Если максимум имеет место для нескольких пар вершин, то выбрать любую из них. Если max_i_i=_P , то Р и Р- Р составляют пару вершин.

Положим _i = i - q_i , q_{i } i , где i и q_i индексы элемента , являющегося крайней левой единицей i- ой строки матрицы .

Если вершина с большим номером может быть переставлена с вершиной с меньшим номером для уменьшения ширины ленты (для некоторого i<P (номер вершины) имеет место _i +( Р- i )<_Р, где max_i=_P ), то перейти к шагу 7.

2. Если вершина с меньшим номером может быть переставлена с вершиной с большим номером для уменьшения ширины ленты, то перейти к шагу 7.

3. Если вершина с большим номером может быть переставлена с вершиной с меньшим номером, так, что сохраняется ширина ленты, то перейти к шагу 6.

4. Если вершина с меньшим номером может быть переставлена с вершиной с большим номером так, что сохраняется ширина ленты, то перейти к шагу 6.

5. Дальнейшие перестановки невозможны, и теперь матрица В имеет ленточную структуру.

6. Если на 3-ем и 4-ом шагах произведено максимальное число непрерывных перестановок или снова выбраны для перестановки две вершины, ранее переставленные друг с другом, то перейти к шагу 5.

7. Произвести указанную перестановку вершин, а именно переставить соответствующие элементы в списке вершин VL и строки и столбцы матрицы В, и вернуться к шагу 1.

12.4.1.2 Алгоритм Катхилла и Макки (1969г.)

Для каждой вершины i графа , соответствующего матрице В, вычислить степень _i, равную общему числу недиагональных единиц i-ой строки матрицы В. Затем выбрать какую-либо вершину i, для которой _i1 =min_i и пометить эту вершину первой. Схему Катхилла-Макки можно рассматривать как метод уменьшения ширины ленты матрицы посредством локальной минимизации чисел _i.

В основе метода следующее замечание.

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

Рассмотрим пример 1 (матрицу и соответствующий ей граф на рис. а):

1. Выбираем вершину 1* и обозначаем её как 1 (Рис. b).

2. Присвоить вершинам, смежным с вершиной 1, новые номера, начиная с 2; в порядке возрастания их степеней (если степени некоторых смежных вершин совпадают, то выбирать любую из них). Эти вершины относят к первому уровню. Для нашего случая вершина 2*, 4*, 9* присвоены номера соответственно 2, 3, 4 (Рис. b).

3. Повторить эту процедуру последовательно для каждой из вершин первого уровня - это значит сперва для вершины 2, затем - 3 и т.д. Для исследуемого гграфа еще неперенумерованной вершиной, смежной с вершиной 2 является вершина 3* - она становится вершиной 5. Смежными с вершиной 3 (которая сначала имела номер 4*) являются вершины 6*, 5* и 10*. В соответствии со степенью этим вершинам присваивают номер 6, 7 и 8 (Рис. c). Заметим, что вершины 5, 6, 7 и 8 связаны с вершиной 1 путем двойной длины и относятся ко второму уровню

4. Повторить процедуру для вершин каждого следующего уровня, пока все n вершин графа  не будут перенумерованы. Если  состоит из двух или более несвязных подграфов, то процедура заканчивается, как только все вершины в подграфе перенумерованы. В этом случае необходимо выбрать начальную вершину в каждом из несвязных подграфов и повторить шаги 2, 3, 4 для каждого из них.

5. Наконец, переставить строки и столбцы матрицы В (или А) в соответствии с новыми номерами вершин. Была ширина ленты 17, стала - 11 (Рис. d).

На базе этого метода создана программа BANDIT , эффективно используемая в комплексе NASTRAN.

П
ример 2. Применим алгоритм Катхилла-Макки к нижеприведённой матрице, полуширина которой равна 10.

Результаты переупорядочения при выборе в качестве начального узла 1 будут следующими:

П
олуширина стала равной 4.

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

Полуширина опять стала равной 4.

12.4.1.3 Алгоритм Эйкиуза и Утку (1968г)

Минимизируем среднюю ширину ленты:

 _i , где _i =1- q_i , q_i i , i и q_i индексы элемента а_{i qi} .

1. Переставить две последовательные строки (и соответствующие столбцы) матрицы А, если:

а)  - уменьшается;

б)  - остается без изменения, но строка с меньшим числом единиц внутри ленты расположится в результате перестановки дальше от центральной строки матрицы А. Регистрировать все перестановки в списке перестановок строк RI. (Первоначально список RI содержит целые 1, 2, 3, ... ,n, и всякий раз, когда осуществляется перестановка строк, переставляются и элементы списка RI).

2. Делать перестановки, производя сравнения строк полными циклами

(полный цикл состоит из n-1 шагов). На каждом шаге сравниваются две последовательные строки и производится перестановка, если условия на шаге 1 удовлетворяются. Шаги выполняются в такой последовательности: (1,2), (n,n-1), (2,3), (n-1,n-2).... и так до центральной строки).

3. Остановиться, если не сделано ни одной перестановки или не происходит уменьшения  в течение эмпирически установленного числа циклов, равного 3+n/100.

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

Достоинство ленточных методов - в их относительной простоте. Однако у них есть и некоторые потенциально серьезные слабости.

Прежде всего, если _i(А) - ширина ленты сильно меняется при изменении i, то диагональная схема хранения будет неэффективна. Кроме того, существуют некоторые очень разреженные задачи, которые могут быть решены весьма эффективно; однако их нельзя упорядочить так, чтобы они имели малую ширину ленты. Таким образом, существуют задачи, для которых ленточные методы просто непригодны.

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