LEC-31 (Материалы к лекциям)

2017-06-17СтудИзба

Описание файла

Файл "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), где yX}

Диаметр графа G: (G)=max{e(x), xX}

или эквивалентно: (G)=max{d(x,y), x,yX}

Узел xX называется периферийным, если эксцентриситет равен диаметру графа, т.е. если 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).

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее