Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 42
Текст из файла (страница 42)
Сначала подпрограмма генерирует структуру уровней с корнем в псевдопериферийном узле. Для этого вызывается подпрогрьмма РИ)(ООТ. Если число уровней меньше, чем 3, го вся компонента в качестве «разделителя» передается иа выход. В противном случае определяется средний уровень с номером Р" 82, Вложенные сечение длл нроизеольных задач 279 САЬЬ РМКООТ ( КООТ, ХАОЗ, АОЗМСУ. МАБК, МЬУЬ, ХЬБ, 1.5 ) 1 С С С С если уРОВней меньше 3 передать Всю КОМПОНЕНТУ КАК РАЗДЕЛИТЕЛЬ НА ВЫХОД.
1Р ( МЬУЬ СЕ 3 ) СО ТО 200 МЕЕР ХЬБ(МЬЪЧ.Ч)) ОО 100 1 1, МБЕР МООЕ ЬБ(1) БЕР(1) НОВЕ МАБК(МООЕ) 0 СОНТ1МОЕ кетокм 100 С С С 200 НАЙТИ СРЕДНИЙ УРОВЕНЬ КОРНЕВОЙ СТР-РЫ УРОВНЕЙ . М1ОЬУЬ (МЬУЬ + 2)/2 м1ОВес х) 5(м1ОЕУь) МР1ВЕС Х(.Б(М10).У( + 1) М1ОЕМО МР)ВЕС вЂ” 1 МР1ЕНО ХЬБ(М1ОЬЧ)Ч2) — 1 С С С С С С В РАЗДЕЛИТЕЛЬ ВКЛЮЧАЮТСЯ ТОЛЬКО УЗЛЫ СРЕДНЕГО УРОВНЯ, ИМЕЮИ(ИЕ СОСЕДЕЙ В СЛЕДУЮ(КЕМ УРОВНЕ ХАОЗ ИСПОЛЬЗУЕТСЯ ДЛЯ ВРЕМЕННОЙ МАРКИРОВКИ УЗЛОВ УРОВНЯ М10(З/Ь+ 1. ОО 300 1 МР1ВЕС, МР)ЕМО МОВЕ ЬБ(1) ХАОЗ(МООЕ) - ХАОЗ(НООЕ) СО(ЧТ 1 МОЕ ИБЕР « 0 ОО 500 1 М1ОВЕС, М1ОЕЗ(О МООЕ ЬБ(1) ЗБТКТ ХАОЗ(МООЕ) ЗБТОР 1АВБ(ХАОЗ(МОСЕ+1)) - 1 ОО 400 3 ЗБТКТ, ЗБТОР МВК АОЗМСУ(З) 1Р ( хноз(мвк> .Ст о > со то Чоо М5ЕР М5ЕР + 1 5ЕР(М5ЕР) МООЕ МА5К(МООЕ) 0 СО ТО 500 Со ЧТ1 МОЕ СОМТ)МОЕ 300 400 500 С С С ВОССтлновить ЗнАки компонент В хАОз.
ОО 600 1 МР1ВЕС, МР)ЕНО МОВЕ ЬБ(1> ХАОЗ(МОВЕ) - ХАОЗ(МООЕ) СОМТ1 МОЕ КЕТИОЧ ЕМО 600 1'1)чл1уг., В цикле 00 500 1=... Обходятся узлы этого сред- него уровня Узел включается в разделитель, если у него есть сосед в следующем уровне. Разделитель помещается в ()Ч)ВЕР, ВЕР). 280 Гж 8. Методы вложенных сечений Упражнения 8.2Л. Эта задача предполагает модификацию подпрограмм СЕ)Ч)ЧР и ГХРБЕР, с тем чтобы реализовать некоторый вариант «неполного алгоритма вложенных сечений».
Введите в обе подпрограммы параметр М1(ЧБЕЕ н модифнцируйте Е)ЧРБЕР таким образом, чтобы она выполняла сечение переданной ей компоненты лишь в том случац если число узлов комтюненты превышает М!)»ЬУЕ. В противном случае компонента упорядочивается посредством подпрограммы КСМ нз главы 4, Проведите эксперимент с целью проверки, будет ли тот результат, который требовалось доказать в упр. 8.1.7, сохранять силу для эвристических упорядочений, получаемых алгоритмом данного параграфа. Одним из способов такой проверки является решение последовательности задач возрастающего порядка, например задач тестового набора чР из главы 9, причем М1!432Е следует положить равным т/У.
(Заметьте, что для сеточной (лХп)-задачи условие 1~!оя»(ч/Л~) означает, что независимые блоки последнего уровня имеют 0(п) = 0(т'Ф) узлов, где У = и!), Зафиксируйте число операций для каждой задачи и сравните эти числа с соответствующими значениями для исходного (полиого) алгоритма вложенных сечений, Аналогичным образом вы можете сравнить требования к памяти, с тем чтобы проверить, будут ли они расти в вашем неполном алгоритме со ско. ростью й!.т/Ф. 8.2.2.
Покажите, что в алгоритме нз раздела 8.2.1 число элементов запол. пения и число операций при разложении не зависят от порядка нумерации узлов разделителя. ф 8.3, Дополнительные замечания В работе (1.!р(оп, Тат!ап, Козе 1979) достигнут значительный прогресс в направлении создания автоматических алгоритмов вложенных сечений. Авторы предложили алгоритм, основанный на следующем фундаментальном результате (1(р(оп, Тат)ап 1977). Пусть 6 — произвольный плоский граф с А! узлами. Узлы графа 0 можно разбить на три множества А, В и С таким образом, чтоАб) (А)ПВ = 8 )С) = 0(т/А()„а ~А! и (В) ограничены числом 2А!/3.
При этом существует алгоритм, который находит А, В и С за время 0(А!). Липтон и соавторы построили для двумерных конечноэлементных задач алгоритм упорядочения с гарантированными оценками 0(А'ч) для числа операднй н 0()У )одз А!) для памяти. Сам алгоритм упорядочения имеет временную сложность 0(А()опт А!), Недостатком алгоритма является значительно большая сложность по сравнению с простым эвристическим методом данной главы. Возможно, что практичным решением была бы комбинация обоих методов; при этом более сложная схема использовалась бы лишь тогда, когда простой алгоритм, описанный нами, дает «плохой» разделитель, Использование идеи вложенных сечений оказалось эффективным и для задач, связанных с трехмерными структурами ф В.З.
доаолнительнме замечания 28! (беогце 1973, 0ц(1, Ке!б !976; )тозе, %ЛИ!еп 1976; Е!зепз!а1 1976). Поэтому исследования, имеющие целью разработку автоматических алгоритмов вложенных сечений для этих неплоских задач, представляются потенциально плодотворной областью. Рядом авторов (Са!а!зап 1975, 1976, беогпе е! а!. !978ц, (.аптЫо!!е 1975) рассматривалась организация методов сечений на параллельных и векторных машинах.
Векторные машины наиболее эффективны, если они могут оперировать с «длинными» векторами; использование же техники сечений обычно порождает короткие векторы, если только не применяются какието нестандартные способы организации данных. Поэтому главной задачей в этой области является балансировка нескольких конфликтующих критериев с целью получить наименьшее время решения. Часто такая балансировка ие соответствует минимизации выполняемой арифметики. У. Численные эксперименты 5 9.0. Введение В главе ! мы сделали такое утверждение. успешность алгоритмов для разреженных матричных вычислений решающим образом зависит от качества нх машинной реализации Вот почему мы включили в книгу программы, реализующие описанные в ней алгоритмы, и дали детальный разбор того, как работают эти программы В этой главе мы приведем результаты численных экспериментов, в которых наши программы использовались для решения некоторых тестовых задач.
Наша главная цель здесь — подкрепить конкретными примерами основные положения $ 2.3, где обсуждались «практические замечания» и где было отмечено, как трудно сравнивать различные методы. Структуры данных различны по сложности, а время решения задачи состоит из нескольких компонент, относительная важность которых зависит от стратегии упорядочения и типа задачи.
Численные результаты, приведенные в этой главе, дадут пользователю информацию, позволяющую оценить значение высказанных положений. Кроме того, полезными для читателя будут сведения о времени и памяти, требуемых для разреженных матричных вычислений довольно представительного класса на типовой вычислительной машине. Тестовые задачи имеют общий характер, типичный для конечноэлементных приложений. Причина такого самоограничения та, что мы хотим лишь проиллюстрировать основные положения. Попытку собрать информацию об относительных достоинствах различных методов для большого числа разных классов задач мы сочли для себя слишком амбициозной.
Более или менее самоочевидно, что для некоторых классов задач один пз методов может равномерно превосходить все остальные или что относительные достоинства методов из нашей книги могут быть совершенно разными для разных классов задач. Ограничивая свое внимание задачами одного класса, мы просто устраняем одну из переменных н без того в сложном исследовании. И все же наши тестовые задачи представляют большую н важную область приложений разреженной матричной технологии. й 9 О Введение 283 Га> Кдадрат (б) Грпддиродпнное ~ (о) Крестообразная область (з' Н-образная область 1р) Квадрат с дырой (малая Зыра1 (о) Кдадрат с Зырай (большая аырп1 (нт) Область с время 3ырками (з1 01лпсть с шестью дырками (и) Область с граничным прокопом Рне.
9.11. Сеточные задачи нрн е 1. 284 Гл, Р. Численные эксперименты У них есть то дополнительное преимущество, что они связаны с физическими объектами (сетками), которые дают картину (граф) матричной задачи. Остальная часть данной главы устроена следующим образом. В $ 9.1 мы описываем тестовые задачи. В 9 9.2 мы объясняем, какая информация содержится в таблицах, н причины, почему она приведена. Сами таблицы с «сырым» экспериментальным материалом находятся в конце $ 9.2. В 9 9.3 мы даем обзор основных критериев, использующихся при сравнении методов, а затем переходим к сравнению а соответствии с этими критериями наших пяти методов в применении к тестовым задачам.
Наконец, в $9.4 исследуется зависимость между схемой хранения, с одной стороны, и памятью и эффективностью подпрограмм численных этапов — с другой. 9 9.1. Описание тестовых задач Два наших набора тестоных задач — это положительно определенные системы, типичные для тех, что возникают в структурном анализе или исследовании теплопроводности (Х!еп!Веча!сх !977). (Отличным введением в предмет может служить Рис.
9.!зк Область с граничным проколом. Коэффициент раабиеиии е равен 3. глава 6 книги (В(гапд 19?3).) На рис. 9,1.1 показаны сетки, составленные Из треугольных элементов. Этн сетки и порождают наши задачи следующим образом. Основная сетка (нз тех, что показаны на рисунке) подразделяется очевидным обра- 8 9.1. Описание тестовых задач 286 зом с коэффициентом разбиения з. В результате получится сетка, имеющая треугольников в зз раз больше, чем исходная.
Рис. 9.1.2 иллюстрирует этот процесс разбиения для области с граничным проколом; здесь з = 3. Задание основной сетки и коэффициента разбиения определяет новую сетку с Л! узлами. Таблица 9.1,! Данные о тестовых задачах набора ~1 приведены коэффициент разбиения, использованный при построении задачи, число полученных уравнений и число ребер в соответствующем графе Козгрграцаент развесная 1т' 1 Е ~ Краррат Граарарараннае Е Крестаауразнан айяасть Н -справная авлнасть Тетиная Уьгра Баяьгвая утра 8 атрее 6 Уьгр Гроничньлб нроиоя Таблица 9.12 Данные о тестовых задачах набора 462 Этн задачи получены нз основной сетки — градуированное С вЂ” прн зиачениах коэффициента разбиения з, равных соответственно 4, б, ..., 12 Иаегяаргнцнент Далее, при фиксированном помечивании этих й! узлов мы строим симметричную положительно определенную систему Ах = Ь порядка У, в которой ао чь 0 тогда и только тогда, когда узлы сетки г и 1' соединены ребром.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
