Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 31
Текст из файла (страница 31)
ДЛЯ КАЖДОГО БЛОКА НАЙТИ УЗЛЫ, НЕ ИМЕЮЩИЕ СОСЕДЕЦ В ПРЕДЫДУЩИХ БЛОКАХ, И ЗАНЕСТИ В ВОВС. ИХ НОМЕРА ПРЕДШЕСТВУЮТ НОМЕРАМ ОСТАЛЬНЫХ УЗЛОВ БЛОКА. Б Б 4 С«ема «ранения и ярацедура раеаредезения аамяти 205 ОО БОО К ),МВЬКБ >Бтет хв> к(к> 1ЯТОР ХВ).К(Ке>) - 1 МЯИВО 0 ОО 400 1 1ЯТВТ, 1ЯТОР МОРЕ РЕЕМ(1) ЗЯТНТ ХАО>(МООЕ) ЗБТОР ХАО>(МООЕ«1) - ! 1Р (1БТОР ЬТ. >БТЕТ) 00 ТО 400 ОО ЗОО 1 >БТЕТ, >ВТОР МАВОЕ АО>МСУ(Ю) МВВВ).К ВМСМ(МАВОЕ) 1Р (МВЕВЕК ьт К) 00 ТО 400 СОМТ>МОЕ МЯОВО - ИВОВО + 1 ЯОВО(МБИВО) - М(ЮЕ 1Р 1БТЕТ е МБОВО - 1 РЕЕМ(1) РЕЕМ(1Р) СОМТ1МОЕ 400 С С ВЫЗВАТЬ ЗПВЙСМ ДЛЯ ПЕРЕУПОРЯДОЧЕИИЯ ПОДГРАФАт С ХРАИИМОГО В (ИВОВО, ЕОВО) .
С )Р ( мяово От о > 1 САЬЬ БОВЕ(.М ( ХАОЮ, АО«МСУ, МАЯК, ИВОВО, 1 50504 РЕЕМ(15ТНТ), Хйв) ВОО СОМТ1МОЕ ЕЕТТ)ВМ ВЯНЦР1. (В1ос1( ЯН()РП.е) Входной информацией для этой подпрограммы являются: структура графа, хранимая парой массивов (ХАОС, АОЗ(н(С'1'), древовидное разбиение, задаваемое посредством (КВ(.КЯ, ХВ(.К), и вектор РЕЯМ. Подпрограмма переставит компоненты вектора РЕЯМ в соответствии со схемой, описанной ранее в этом разделе. Требуются четыре рабочих вектора. ВКЦМ хранит блочный номер каждого узла; ЯЦВО накапливает узлы подграфа; МАЯК и Х(.Я нужны подпрограмме ЯЦВВСМ.
Работа подпрограммы начинается с присвоения начальных значений рабочим векторам ВКЦМ и МАЯК (цикл ОО 200 К = ...). Циклом ОО 500 К = ... обходится каждый блок разбиения. Для каждого блока в векторе ЯЦВО накапливаются узлы, не имеющие соседей в предыдуших блоках (цикл 1«О 400,..). Переменная (н(ЯПВО указывает число узлов подграфа. Затем вызывается подпрограмма Я()В((СМ, которая переупорядочивает этот подгпаф, используя алгоритм КСМ. Выход из программы про)исходит после того, как все блоки будут обработаны. 200 Гл д Методы Фактор-деревьев ЯЗВВСМ (3ОВегар)) МСМ) Эта подпрограмма аналогична подпрограмме ОЕ(ч)(СМ, за исключением того, что оиа оперирует с подграфом.
Подграф, который може~ быть и иесвязен, задается парой ()ЧВОВО, 3ОВО), Массивы МАВК и Х) 3 — это рабочие векторы, используемые подпрограммами гг(БООТ и )(СМ (см. разделы 4.3.3 и 4.3.4). с ° ь ° ° ° ° ° с ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Сь ° ° ° ° ° ° ° БОВЕСМ ... ОБРАТНОЕ УПОРЯДОЧЕНИЕ КАТХИЛЛА - ИАККИ с ° ИСПОЛЬЗУЕИЫЕ ПОДПРОГРАНИЫ Рмкоот, асм . Сь ° С Боваопгпче Бпвесм < хАВ1, Аозмст, мчзк, мзпвп, Бпвп, 1 Реам, хьз ) С Сь ь*ь ° ° ° ь ° ° С С" ° ° ° ° ° ' ° ° ° ° ° С 100 с с с с с с с с с с с с с с с с с с с с с с с НАХОДИТ ЯСМ - УПОРЯДОЧЕНИЕ ЛЛЯ ЗАДАННОГО ПОДГРАФА (ВОЗМОЖНО т НЕСВЯЗНОГО) . ВХОДНЫЕ ПАРАМЕТРЫ(ХАВ1, АВ)МСЪ') - СТРУКТУРА СМЕЖНОСТИ.
(Мзпвп, 5066) - ЗАДАННЫЙ ПОДГРАФ. НБ()ВО - ЧИСЛО УЗЛОВ ПОДГРАФА, БОВО СОДЕРЖИТ ЕГО УЗЛЫ ВЫХОДНОЙ ПАРАМЕТР- РЕЕМ - ВЕКТОР ПЕРЕСТАНОВКИ . ИСПОЛЬЗУЕТСЯ ВРЕМЕННО ДЛЯ ХРАНЕНИЯ СТРУКТУРЫ УРОВНЕЙ. РАБОЧИЕ ПАРАМЕТРЫ- МАБК - ВЕКТОР ИАРКИРОВКИ С НУЛЕВЫМИ КОИПОНЕНТАИИ. ИСПОЛЬЗУЕТСЯ ДЛЯ УКАЗАНИЯ УЗЛОВ ПОДГРАФА. хьз - индексный Вектор для ст укту ы уровней, ХРАНИМОЙ В ЧАСТИ ВЕКТОРА РЕЯМ. 1мтеоеа Апзмст(1), мАБк(1), Реем(1), Бпво(1), ХЬБ(1) тмтеоеа хАВЗ(1), сс5125, 1, мьуь, мове, м5056, мьм е ° ° т ° ° ° ° ° ° ° ° ° ° ° ° ° ° ьь ° ° ь ° ььье ВО 100 1 1, МБПВ6 МОВЕ 5056(1) МАБК(МОВЕ) 1 СОМТ1МОЕ МОМ 0 ВО 200 1 1, МБПВО МОВЕ Бпап(1) 1Р ( МАБК(НОВЕ) .).Е. 0 ) 60 ТО 200 КАЖДУЮ СВЯЗНУЮ КОМПОНЕНТУ ПОДГРАФА я 84 Схема хранения и нроиеаура раенределения памяти 207 УПОРЯДОЧИТЬ ВЫЗЫВАЯ ЕМЯООТ И ЯСМ .
СА11 Р)(ВООТ ( МОВЕ, ХАО1, АОЛ4СТ, МАЯК, 1 мьиь, х15, РеВИ(мои+1) ) СА11. ВОЮ ( МОВЕ, ХАВ1, АО)МСТ, МАЯК. 1 РЕЕМ(МОМе1), ССЯ12Е, Х1.8 ) МОМ МОМ + ССЯ12Е 1Р ( МЦМ .ОЕ МЯОВО ) ВЕТОВМ 800 СОМТ1МЦЕ ВЕТОВМ В)1)) 6,4.е. Распределение памяти и подпрограммы Рб)ТЕУ(Ч, РАЗОРА!Е и РЕЙТАР.) Теперь мы опишем две подпрограммы Р!х!ТЕ(ХЧ (Р11))б Тгее Е(х(Че!Оре) и Р1)ОР(че (Р!11(1 ОР1-618(гопа! !МОПЕегоз), предназначенные для того, чтобы по графу (е, упорядочению а и разбиению $ сформировать структуру данных, описанную в разделе 6.4.1. Кроме того, чтобы получить эффективную реализацию процедуры численного разложения, необходимо построить вектор, содержаший структуру смежности ассоциированного фактор-дерева 6/$.
Это является функцией третьей подпрограммы Р(1)ТАР( (Р111!(1 Тгее АР)асепсу), которую мы также описываем в данном разделе. Р(1)ТЕ(1)Ч (Р!(х(б Тгее ЕХЧе!оре) Эта подпрограмма определяет структуру оболочки диагональных блоков блочной матрицы. Входной информацией являются: структура смежности (ХАР(, АР)ХСУ), упорядочение (РЕЕМ, 1(х)ЧР) и древовидное разбиение (1)В(.КВ, ХВ(.К).
Структура, полученная подпрограммой и помещенная в ХЕ)х(Ч, может не совпадать в точности со структурой оболочки диагональных блоков, хотя она всегда содержит в себе реальную оболочку. Для достижения большей простоты и эффективности при построении структуры оболочки используется следующее замечание. Пусть $ =(У), ..., Уе) — заданное древовидное разбиение и хь х, ~ Уя. Если Аб) (х,) П (У„..., УА,) ЯА О, Аб)(х,)()(УО ..., У,,) М 8, то подпрограмма включает (х(, х() в структуру оболочки диагональных блоков. Хотя этот алгоритм может приводить к чрезмерно большой оболочке диагонального блана (приведите пример почему), для упорядочений, генерируемых алгоритмом (х(;~Т, он обычно дает результат, очень близкий к точной оболочке.
Так как Гл 6 Методы фактор деревьев * ь * С»е ° ° ь ° ГМТЕЬМ ... ПОСТРОЕНИЕ ОБОЛОЧКИ ДИАГОНАЛЬНЫХ °" С е ь ° ° ° ° БЛОКОВ ДРЕВОВИДНО УПОРЯДОЧЕННОЙ МАТРИЦЫ С С«ьь ° ь ь ЕМУЗЕЕ 1 С С С ЦИКЛ ПО бЛОКАМ РАЗбИЕНИЯ .. 00 400 К 1 МВ!КЗ ВСКВЕС ХВЕК(К) ВСКЕМО ХВЕК(Ке 1) - 1 С С С С С с С С 1Р1НЗТ 1 00 гоо 3 . ЗЗТНТ, ЗЗТОР МВН АОЗМСУ(3) МВК 1МУР(МВН) С С С С С С С С С С С С С ОПРЕДЕЛЯЕТ ИНДЕКСНЫЙ ВЕКТОР ДЛЯ ОБОЛОЧКИ ДИАГОНАЛЬНЫХ БЛОКОВ ДРЕВОВИДНО УПОРЯДОЧЕННОЙ МАТРИЦЫ .
ВХОДНЫЕ ПАРАМЕТРЫ(ХА03, АОЗМСУ) - СТРУКТУРА СМЕЖНОСТИ ГРАФА . (РЕКИ, 1МУР) - ВЕКТОРЫ ПЕРЕСТАНОВОК. (МВ1КН, ХВСК) - ДРЕВОВИДНОЕ РАЗБИЕНИЕ. ВЫХОДНЫЕ ПАРАМЕТРЫХЕМУ - ИНДЕКСНЫЙ ВЕКТОР ОБОЛОЧКИ. ЕМЮЗЕЕ - ЧИСЛО ЭЛЕМЕНТОВ НАЙДЕННОЙ ОБОЛОЧКИ. ЗСВКОСТ1МЕ РМТЕМУ ( ХАВЗ. АОЗМСУ, РЕНИ, 1МУР, 1 МВСКЗ, ХВ1К, ХЕМУ, ЕМУЗЕЕ ) 1МТЕСЕК АОЗМСУ(1), 1МУР(1), РЕКИ(1), ХВЕК(1) 1МТЕСЕК ХАОЗ(1), ХЕМУ(1), В(.КВЕС, В(.КЕНО, 1 1, 1Е1НЗТ, 3, ЭКТОР, ЗЗТНТ, К, КР1ННТ, 1 емузге, НВЕкз, мнн, м00е КГ1йВТ УКАЗЫВАЕТ ПЕРВЫЙ УЗЕЛ К- ГО БЛОКА, ИМЕЮЩИЙ СОСЕДЕЙ В ПРЕДЫДУЩИХ БЛОКАХ. КР1КЗТ В!НЕМО 00 300 1 ВСКВЕС, ВСКЕМТ) хему(1) емунге МОРЕ РЕНИ( 1) ЗЗТКТ ХАОЗ(МОВЕ) ЗЗТОР ХАОЗ(МОВЕ+1) - 1 1Р ( ЗНТОР .ЕТ. ЗЯТКТ ) Со То Эоо 1Е1йЗТ УКАЗЫВАЕТ ИНДЕКС ПЕРВОГО НЕНУЛЕВОГО ЭЛЕМЕНТА 1 в Й СТРОКИ ВНУТРИ К " ГО БЛОКА .
й 5.4. Скена кранемия и процедура раслределения ланята 209 1Р ( МВЯ .1.Т. ВЬКВЕС ) СО ТО 100 1Р ( ИВЯ .Ьт. 1Р1ЯБТ ) 1Р1ЯБТ МВЯ СО ТО 200 1Р ( КР1ЯБТ .1.Т. 1Р1ЯБТ ) 1Р(ЯБТ КР1Я5т 1Р ( 1 .Ьт. КР1ЯБТ ) КР1ЯБТ 1 СОМТ1МПЕ ЕМЧБЕЕ НВБЕЕ т 1 - 1Р1ЯБТ СОИТ1МСЕ СОМГ1ИЦЕ ХЕМЧ( ВЬКЕМВт) ) Е)(ЧБХЕ ЕМ(ГБКЕ ЕВ)ЧБЕЕ - 1 ЯЕПЛНЧ Н'Ф 300 400 он работает очень хорошо, мы пользуемся им, а не более сложной (и более дорогой) схемой, которая бы определяла точную оболочку. Для других алгоритмов древовидного упорядочения, например для описываемого в главе 7 алгоритма параллельных сечений, требуются более сложные схемы.
~) В отличие от описания, приведенного в разделе 6.4.1, подпрограмма РХОРХ2 определяет столбцовые индексы элементов нижнего треугольника матрицы. — Прем, нерее. а) ХЕЯ/ВЬ. — Прим нерее, РХОРИХ (Р(Мб ОЛ-б(арона! Хоп Еегоз) Подпрограмма Г)ч)Огг)Х используется для определения структуры ненулевых элементов заданной блочной матрицы, расположенных вне блочной диагонали. В терминах схемы хранения из раздела 6.4Л эта подпрограмма находит индексный вектор ИХЗ()ВЬ и индексный вектор ХИОг)Е. Выходным значением переменной МАХ(т)Х является число ненулевых элементов матрицы, находящихся вне диагональных блоков.
Входная информация подпрограммы: структура смежности графа (ХАО), АШИСУ), древовидное упорядочение (РЕ(хМ !)ч')(Р), древовидное разбиение (ХВ) КЬ, ХВ(.К) и длина массива ХУБОВА, задаваемая переменной МАХНУ. Подпрограмма проходит циклом блоки разбиения. Для каждого блока выполняется цикл ОО 200 ) =..., в котором исследуется каждый узел блока. Всякий сосед, принадлежащий одному из предыдуших блоков, соответствует ненулевому элементу, расположенному вне блочной диагонали; этот элемент добавляется к структуре данных.
Когда определены все индексы данной строки '), они упорядочиваются по возрастанию посредством подпрограммы ЗОЙТ5); последняя очень проста и не нуждается в объяснениях. Ее листинг следует за листингом РХ ОР)Чг. Заметим, что если длина заданного пользователем индексного вектора ') недостаточна, то подпрограмма обнаружит это ф 6.Е Схема хранения и арацедура расаределенил памати 2)1 С С С 1 200 300 400 Се С„, е е, ° ° ° е ° БОНТЯ1 ... СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКЛ О С* С С УПОРЯДОЧИВЛЕТ ЗАДАННЫЙ МАССИВ КОРОТКИХ ЦЕЛЫХ С ЧИСЕЛ ПО ВОЗРАСТАНИЮ МЕТОДОМ ПУЗЫРЬКЛ.
С С С С С С С С * ° ВХОДНОЙ ПЛРЛМЕТРМА - ДЛИНА ЦЕЛОГО МЛССИВА . ИЗМЕНЯЕМЫЙ ПЛРЛМЕТРАЯЯЛУ - ЦЕЛЫЙ ВЕКТОР, ЕГО КОМПОНЕНТЫ НЛ ВЫХОДЕ УПОРЯДОЧЕНЫ ПО ВОЗРАСТАНИЮ. С ЯОВйО!)ТПЧЕ ЯОНТБ1 ( МА, АЙНАУ ) С С' 1МТЕСВН АЙНАУ(1) 1МТЕСЕН К, 1, МА, МОВЕ С С ° 1 ° 1Р (МА .ЕЕ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
