LEC-31 (Материалы к лекциям)
Описание файла
Файл "LEC-31" внутри архива находится в следующих папках: Материалы к лекциям, Lecturessemestr7. Документ из архива "Материалы к лекциям", который расположен в категории "". Всё это находится в предмете "методы решения задач механики сплошных сред" из 7 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "методы решения задач механики сплошных сред" в общих файлах.
Онлайн просмотр документа "LEC-31"
Текст из документа "LEC-31"
7
В.А. Столярчук. “Моделирование систем”. Конспект лекций. Лекция № 31Лекция № 31
12.4.3. Определение начального узла
Цель состоит в том, чтобы найти пару узлов, удаленных друг от друга на максимальное или почти максимальное расстояние. Значительный практический опыт свидетельствует, что такие узлы хороши в качестве начальных для нескольких алгоритмов упорядочения, в том числе для алгоритма RCM (Reverse Cuthill-McKee)
Расстояние d(x,y) между двумя узлами x и y связного графа G=(X,E) есть просто длина кратчайшего пути, соединяющего эти узлы.
Эксцентриситет узла Х: e(x)=max{d(x,y), где yX}
Диаметр графа G: (G)=max{e(x), xX}
или эквивалентно: (G)=max{d(x,y), x,yX}
Узел xX называется периферийным, если эксцентриситет равен диаметру графа, т.е. если e(x)= (G).
Пример графа:
При этом периферийные узлы X2, X5, X7.
Таким образом, наша цель состоит в описании эвристического эффективного алгоритма для определения узлов с большим эксцентриситетом.
Подчеркнем, что алгоритм не дает гарантии, что будет найден периферийный узел или хотя бы узел, близкий к периферийному. Тем не менее получаемые узлы , как правило, имеют большой эксцентриситет и являются хорошими начальными значениями для использующих их алгоритмов.
Основной конструкцией алгоритма является корневая структура уровней
Алгоритм принадлежит Гиббсу и соавторам (1976г.)
Шаг 1. инициализация: выбрать в Х произвольный узел r.
Шаг 2. построение структуры уровней:
а) построить структуру уровней с корнем в r .
б) определить e(r).
Шаг 3. стягивание последнего уровня: выбрать в последнем уровне узел Х с минимальной степенью.
Шаг 4. построение структуры уровней:
а) построить структуру уровней с корнем в Х.
б) если e(x) > e(r), положить r x и перейти к шагу 3.
Шаг 5 (финиш). Узел Х является псевдопериферийным.
Для построения структуры уровней возьмем в качестве начального узел 10.
Выбираем в последнем уровне узел 5 с минимальной степенью (могли бы взять узел 3) и снова строим структуру уровней..
Строим структуру уровней от узла 3.
Таким образом, судя по эксцентриситету в качестве периферийных могут выступать узлы 3,5 и 8.
Мы уже убедились ранее, что перенумерация, производимая от узла 3 привела к профилю, равному 18. Применим алгоритм RCM, начиная от узла 8.
Новая нумерация | Старая нумерация | Ненумерованные соседи в порядке возрастания степеней | Обратное упорядочение |
1 | 8 | 6, 9 | 10 |
2 | 6 | 5, 1 | 9 |
3 | 9 | 10, 7 | 8 |
4 | 5 | - | 7 |
5 | 1 | 4, 2 | 6 |
6 | 10 | - | 5 |
7 | 7 | - | 4 |
8 | 4 | - | 3 |
9 | 2 | 3 | 2 |
10 | 3 | - | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
1 | x | * | |||||||||
| 2 | * | x | * | * | * | |||||
3 | * | x | * | * | |||||||
4 | * | * | x | * | * | ||||||
5 | * | x | * | ||||||||
6 | * | * | x | * | |||||||
7 | x | * | |||||||||
Профиль стал также 18 | 8 | * | * | x | * | * | |||||
9 | * | * | * | x | * | ||||||
10 | * | * | x |
12.5. Сравнение методов упорядочения матриц.
Сравнение методов является трудной проблемой, так как эффективность метода зависит от конкретной задачи или от класса задач, для решения которых он используется.
Перечислим классы наиболее эффективных методов.
1. Ленточные методы (LR, CM).
2. Профильные методы (RСМ).
3. Универсальные разреженные методы (QMD).
4. Методы фактор-деревьев для конечно-элементных и конечно-разностных задач (RQT).
5. Методы параллельных сечений для конечно-элементных задач (IWD).
6. Методы вложенных сечений (ND).
LR – алгоритм Розена
CM - алгоритм Катхилла-Макки.
RCM - обратный алгоритм Катхилла-Макки.
RQT - алгоритм древовидного разбиения.
IWD - алгоритм параллельных сечений.
QMD - алгоритм минимальной степени.
ND - алгоритм вложенных сечений.
Нельзя заранее сказать - какой метод лучше, т.к. типы разреженности весьма разнообразны.
Главными критериями являются:
а) запросы к памяти,
б) время исполнения,
в) стоимость.
В одних случаях наибольшее значение имеет уменьшение запросов к памяти, в других - малое время исполнения.
Но чаще всего, по-видимому, интерес представляет выбор метода, для которого стоимость машинных ресурсов минимальна. Эта стоимость обычно является довольно сложной функцией от количества (S) используемой памяти, времени исполнения (Т), количества вводимой и выводимой информации и других параметров.
Для рассматриваемого класса задач и методов, которые мы рассматриваем, стоимость очень хорошо аппроксимируется функцией вида:
COST(ST)=Tx p(S)
где p(S) - многочлен степени di ; обычно d=1 (однако, иногда d=0, а в некоторых случаях, когда большие запросы к памяти нежелательны, d=2). Для наших иллюстративных целей вполне достаточно взять p(S)=S.
Если основой сравнения является общее время работы, то следует выбрать алгоритм RCM.
Если наибольшее значение имеют время решения, или суммарное время разложения и решения, или суммарная стоимость разложения и решения, то нужно выбрать алгоритм QMD.
Если наиболее важны критерии памяти, стоимости решения или общей стоимости, то предпочтительным оказывается алгоритм IWD.
QMD дает несколько лучшее упорядочение, чем ND, что отражается в меньших времени и стоимости на этапах разложения и решения и в меньших запросах к памяти.
Однако упорядочение для ND вычисляется значительно быстрее, чем для QMD, что в итоге приводит к меньшим значениям для общей стоимости и общего времени для ND по сравнению с QMD.
У IWD - превосходные характеристики в категориях стоимости и памяти.
Запросы к памяти
1. Для некоторых методов накладная компонента памяти очень значительна, даже для больших задач, где ее относительная важность несколько уменьшается.
Д ля QMD
Д ля RCM накладная память
2. Основная память является очень ненадежным показателем общих запросов программы к памяти.
Например, при сравнении RCM и QMD исходят только из объема основной памяти, то при всех N следовало бы выбрать QMD.
Между тем, реально потребляемая память у метода RSM меньше, вплоть до N=1500.
Время исполнения
1. Вообще говоря, эффективность (т.е. число операций в секунду) подпрограмм увеличивается с ростом N. Этого и следовало бы ожидать, т.к. циклы, будучи инициализированы, выполняются все большее число раз.
Тем самым при возрастании N относительно уменьшаются издержки, связанные с инициированием циклов.
В работе Collins R.J. Bandwidth reduction by automatic remembering // Iut.I Number. Meth. Eng/ - 1973/-Vol.1, No. 6 p.345 представлен метод перенумерации узловых неизвестных, основанный на фронтальном алгоритме СМ. Здесь же представлена таблица наиболее распространенных алгоритмов минимизации ширины ленты системы уравнений МКЭ применительно к 11 примерам, реализованным на ЭВМ IBM 360/85.
№ при-мера | Чис-ло уз-лов | Чис- ло эле-мен-тов | Перво-началь-ная ширина ленты | Окончательная ширина ленты CM RR AU HG RC | Время [мин] RR AU HG RC | |||||||
1 | 16 | 16 | 16 | 3 | 6 | 6 | 4 | 3 | 0,005 | 0,005 | 0,005 | 0,003 |
2 | 45 | 85 | 37 | 6 | 13 | 8 | 8 | 6 | 0,04 | 0,03 | 0,02 | 0,03 |
3 | 19 | 34 | 19 | 5 | 6 | 6 | 6 | 5 | 0,005 | 0,005 | 0,005 | 0,004 |
4 | 42 | 81 | 38 | 10 | 10 | 10 | 8 | 9 | 0,01 | 0,01 | 0,01 | 0,005 |
5 | 56 | 4 | 53 | - | 27 | 29 | 20 | 17 | 0,04 | 0,02 | 0,04 | 0,006 |
6 | 20 | 9 | 17 | - | 10 | 10 | 10 | 7 | 0,01 | 0,005 | 0,005 | 0,003 |
7 | 324 | 245 | 326 | - | 64 | 38 | 39 | 37 | 8,00 | 1,78 | 1,28 | 0,044 |
8 | 515 | 178 | 147 | - | 82 | 85 | 71 | 47 | 3,17 | 1,76 | 8,00 | 0,086 |
9 | 499 | 503 | 195 | - | 80 | 73 | 72 | 51 | 6,5 | 6,51 | 7,07 | 0,81 |
10 | 298 | 151 | 223 | - | 46 | 43 | 45 | 36 | 4,93 | 2,10 | 1,13 | 0,039 |
11 | 574 | 2222 | 568 | - | - | - | - | 79 | - | - | - | 0,118 |
1) Катхилл и Макки (СМ).
Cuthill E., Mc.Kee T. Reducing the Bandwidth of Space Symmetric Matrices//ACM, Nat. Conf. - San Francisco, 1969, P157-172.
2) Розен (RR).
Posen R. Matrix Bandwidth Minimization// Prac. Of ACM Nat. Conf. - 1968. - P.585-593.
3) Акьюца и Утку (AU).
4) Грумс (HG).
5) Коллинз (RC).