Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 33
Текст из файла (страница 33)
замечания относительно РОТ, приводимые ниже.) Подпрограмма ТЗРСТ начинает с присвоения начальных значений рабочим векторам ТЕМР и РПхЬТ (цикл 00 100 1= ...). Затем для каждого блока разбиения выполняется основной цикл 00 1600 К = .... В основном цикле прежде всего вызывается подпрограмма ЕЬРСТ, факторнзующая и-й диагональный блок. Следующий шаг — выяснить, где расположен внедиагональный блок; его указывает компонента РАТНЕР (й). Далее выполняются циклы ОО 200.... и ОО 400..., определяющие соответственно первый и последний ненулевые столбцы внедиагонального блока, так что поправку можно выполнять лишь в пределах, обозначенных этими столбцами. Рис. 6.5.3 показывает роль некоторых важных локальных переменных в подпрограмме.
Цикл ОО 1300 СОЕ ... осуществляет модификацию диагонального блока с номером РАТНЕЙ (й). Каждый столбец с" ° с ° ° ° » ° » » С» ° ° ТБРСТ ... СИММЕТРИЧНОЕ РАЗЛОЖЕНИЕ С °" " ° ° ° **"" ДРЕВОВИДНО УПОРЯДОЧЕННОЙ МАТРИЦЫ с ° ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫ " ЕБРСТ. ЕЬБЬУ, ЕОЯ.У. с с с» ' » »» ° ° ° » ° с с» » ° ° »»»»» с с с с ИНИЦИАЛИЗАЦИЯ ...
МВ155 ХВЗК(МВ1КБ»1) — 1 00 100 1 З,МЕОМБ ТКМР(1) О. ОЕО РЗЯБт(1> - хмомг(1) СО>>Т1МОЕ 100 с с с ЦИКЛ ПО БЛОКАМ .. 00 1000 К 1, МВЬКБ КОИВЕО ХВЬК(К) КОИШЯ> - ХЗЗХ(К»1> - ) с с с с с с с с с с с с с с с с с с с с с с с с с с с с с ВЫПОЛНЯЕТ СИММЕТРИЧНОЕ РАЗЛОЖЕНИЕ ДЛЯ СИСТЕГ(Ы СО СТРУКТУРОЙ ФАКТОР - ДЕРЕВА. ВХОДНЫЕ ПАРАМЕТРЫ(МБЬКБ, ХБЬК, РАТНКК> - ДРЕВОВИДНОЕ РАЗБИЕНИЕ ° хему - индексный вектоР оволочки. (ХМОМХ, МОИХ. МХБОВБ) — НЕНУЛЕВЫЕ ЭЛЕМЕНТЫ ИСХОДНой МАТРИЦЫ ВНЕ БЛОЧНОЙ ДИАГОНАЛИ. ИЗМЕНЯЕМЫЕ ПАРАМЕТРЫ " (01А6, КМУ) — ОСНОВНАЯ ПАМЯТЬ ДПЯ ОБОЛОЧКИ ДИАГОНАЛЬНЫХ БЛОКОВ МАТРИЦЫ. НА ВЫХОДЕ СОДЕРЖИТ ДИАГОНАЛЬНЫЕ БЛОКИ МНОЖИТЕЛЯ.
1Р>.АΠ— ИНДИКАТОР ОШИБКИ. РАВЕН 1» ЕСЛИ В ХОДЕ РАЗЛОЖЕНИЯ ВСТРЕТИТСЯ О ИЛИ КОРЕНЬ ИЗ ОТРИЦ. ЧИСЛА. РАБОЧИЕ ПАРАМЕТРЫТЕМР - РАБОЧИЙ ВЕКТОР ДЛЯ РЕАЛИЗАЦИИ АСИММЕТРИЧНОГО РАЗЛОЖЕНИЯ . г>ЕБт - РАБочнй вектоР, упйо(КАК>0(нй ИНДЕКСИРОВАНИЕ ВЕКТОРА МОНЕ (ИЛИ МЕБОВБ) ПРИ ОПЕРАЦИЯХ С НЕНУЛЕВЫМИ СТОЛБЦАМН ВНЕДИАГОНАЛЬНЫХ БЛОКОВ. БОККООТ1МК ТБРСТ ( МВ1.КБ.
ХВЬК, РАТНЕК, 01АО, ХХМУ, Е>ЗУ, 1 ХМОМХ, НОМЕ, МХЯЗББ, ТЕМР, Р1КБТ, 1РЬА6 ) 0(ИЗВ1.Е РйЕС151ОМ ОРБ СОММОМ /БРКОРБ/ ОРБ КЕА1. 01А6(1) ЕМУ(1) МОМХ(1) ТЕМР(1) 5 1МТХОЕй ГАТНЕК(1), МХЯЗВБ(1), ХВЬК(1) 1МТКОЕК Р1КБТ(1), ХЕМУ(1), ХМОМХ(З), БЬКБХЕ, СОЬ, СОЬЗ, СОЬБЕ6, ОХЕМО, СОЬБХЕ, РМХ, РМХ1, 1, 1РЬАО, 15ТКТ, 15ТОР, 1505, 3, ЗБТОР, ЗБТйТ, К, КЕМУ, ХЕМУС, КРАТНК, МВЬКБ, МКОМБ.
КОИ, КОИВЕ6, КОКЕ>>0 б ЕЗ Подлрогриииы ХЕРСТ и Т551! ЕЕ< РУО! МЕБПВБ(ХБТКТ) 1Р ( 15ТОР .Хт. 15ТКТ .ОК. Р)О! .СТ. КОНЕ)40 ) СО ТО 1100 1 С С С ВЫЧИСЛЯТЬ ЛИ СКАЛЯРНОЕ ПРОИЗВЕДЕНИЕ, хн < Р)ж) .хт. Рма ) со то иоо 1Р ( РМХ! .ЕО. Р)О .АМО. СО!.1 .).Т. СОХ ) 60 ТО 1100 5 О.ОЕО 00 800 1 ХБТКТ, 15ТОР 1508 М15085(1) 1Р ( ХБСВ .СТ. КОНЕМО ) 60 ТО 900 5 Б + ТЕИР(1508) г МО)!2(1) ОРБ ОРБ + 1.000 СОЧТХМСЕ 800 С С С 900 НОДИФ. ОБОЛОЧКУ ИЛИ ДНАГ. ЗЛЕ)ЧЕНТ.
1Р ( СОХ! .ЕО. СОХ ) СО ТО 1000 КЕМУ КЕМУО + СОХ! 1Р ( СОХ! .СТ. С01. ) КЕМУ ХЕМУ(СОХ!+!) — С01.1 + Сой ЕМУ<КВНУ) - ЕМУ<КВНУ) - 5 60 ТО !100 ВХАС(СОХ!) ВХАС(СОХ1) - Б СОМТЩЧНЕ 1000 1100 С С С УСТАНОВИТЬ О ДЛЯ ЧАСТИ ТЕ)ЧР. ОО 1200 КОН РМЕ, КОНЕМО ТЕМР(КОН) О.ОЕО СОМТ1МВЕ СОМТХМСЕ 1200 1300 С С С С С С МОДИФИЦИРОВАТЬ РХКБТ В ПОЗИЦИЯХ, ОТВЕЧАЮЩИХ СТОЛБЦАИ БЛОКА РАТНЕЙ(К) . ОНИ БУДУТ УКАЗЫВАТЬ НАЧАЛО СТОЛБЦОВ СЛЕДУЮШЕГО ВНЕВХ<АГОНАЛЬНОГО БЛОКА. ОО 1500 С01. СОХВЕС, С01.ЕМО 15ткт Рхкат(сох) ХБТОР ХМОМЕ(СОХ+!) - 1 1Р ( ХБТОР .Хт. ХБТКТ ) 60 ТО 1500 00 1400 Х ХБТКТ, ХБТОГ КОН )ОБСВБ(Х) 1Р ( КОН .1.Е. КОНЕМВ ) 60 ТО 1400 РХКБТ(СОХ) Х 60 ТО 1500 СО4Т1МСЕ РХКБТ(СОХ) 15ТОР + 1 СОМТХМОЕ СОМТХМОЕ К ГП)КМ ЕМО !400 1500 1800 внедиагонального блока распаковывается в векторе ТЕМР (цикл ()О б00 3 = ...), после чего происходит обращение к профильным подпрограммам решения треугольных систем Е1б1)х и 222 Гв 6 Методы фактор-деревьев Е1)51Л/ Наконец, внутренний цикл 00 1100 С01.1 = ...
вы. полняет модификацию так, как это описано в разделе 6.5.1. Прежде чем подпрограмма перейдет к рассмотрению следуюшего блока, она модифицирует рабочий вектор Г1КЯТ в тех позициях, которые соответствуют столбцам блока гАТНЕК (й). Эти компоненты Р1КЯТ будут теперь указывать на следующие элементы, которые нужно обработать а этих столбцах (цикл 00 ! 500 СО 1- = .") Когда все диагональные блоки обработаны, происходит вы. ход нз пода р огра м и ы.
б.бХ Подпрограмма ТЗЗЕЧ (Тгее Зупппе1Пс ЗОЕЧе) Реализация процедуры решения линейной системы со струк. турой фактор-дерева не следует той последовательности вычислений, что указана в разделе 6.2.3. Вместо этого используется альтернативное разложение, которое, согласно упр.6.1е2, приводит к асимметричной схеме: т — г ° (6 5 2) Здесь И7 = — 'У, причем Ят не вычисляется в явном виде, а С = С вЂ” Уг В-'К При записи А в этой форме решение системы (: ."-)(*,') =(".) сводится к решению систем (: -'И*.,')-(".) Предполагается, что подматрицы В и С были разложены в т т произведения ЕвЕв и ЕсЕс соответственно. Схему можно записать следуюшим образом. Прямой ход Решить Ев (Ева) = Ьь т Вычислить Ье — — Ьа — Ртам Решить Ес (Ессае) = Ь» б ба Подпрограммы Т2РСТ и Тазы'1г 226 Обратная подстановка Положить хз = хг.
Вычислить )г — — багха. Решить Ев (Ега г1) = 2ь Вычислить хг = хг — г,. ЕП = АПЕП!. (6.5.3) Мы хотим определить асимметричное блочное разложение (6.5.4) аналогичное разложению (6.5.2). Вид множителя Е очевиден: его элементы выражаются формулами ЕПЕгь т АП, О если э' = 1', если э') Е в противном случае.
Выпишем явное выражение для Е для случая р = 4')г Е„Е„ т О О О ЕгэЕД О О Ам Аэ| .4зэ ЕззЕээ Ам Агг Ам ЕггЕгг ') На приводимой картинке по крайней мере три виедиагоиальныл 6 ~ока Аи должны быть нулевыми (см. начало раздела 623) — Прим терев Эта схема является простым переупорядочеиием указанной в разделе 6.1.2 последовательности операций.
Единственное различие состоит в том, что в прямом ходе не требуется рабочего вектора. (Что, впрочем, не дает реального выигрыша! Почемуг) Мы выбрали эту схему по той причине, что она упрощает организацию программы для случая древовидно упорядоченной системы произвольного блочного порядка р Рассмотрим теперь обобщение описанной асимметричной схемы. Пусть А — древовидно упорядоченная матрица блочного порядка р с блокамв А„, ! е- Е) ( р.
Пусть Еч — соответствующие подматрицы треугольного множителя Е. Напомним (см. раздел 6.2.2), что для матрицы А с древовидным разбиением внеднагональные блоки Е„(э» 1) задаются формулами 224 Гл. 6. Методы фвигор.деревеев Лемма 6.5.2. ут т Доказательство. Утверждение леммы является прямым следствием формулы (6.5.3), связывающей внедиагональные блоки древовидно упорядоченной матрицы А и ее множителя Е. С помощью леммы мы можем представить верхний треугольный множитель 0 из (6.5.4) в виде йт л.тг ые т Отсюда выводим ввлм е ге им йи т3.ет, еелм 4с л й иначе При (( й выражению для егге можно придать другую форму, учитывая (6.5.3): т -т -! т -1 Цм Ь; (А~;Ь„тт) 4и тС„'А тг ИлЮ А е Теперь для случая р = 4 мы можем выписать явно оба сомножителя асимметричного разложения (6.5.4) '): ') См примечание иа стр.
223 4 ад. Подпрограмма ТБЭгСТ и ТЯЯэ.У 225 ЕнЕД О О О Ам ЕээЕээ О О 4эи Аээ ЕээЕээ О Агэ Агэ Агэ ЕиЕй э (ЕнЕй) А1э (Е|Аь) 41э (ЕмА~) 4м О 1 (ЕээЕээ) 'Аээ (ЕээЕээ) 'Аэг (ЕэзЕээ) гА34 О О О О О Чтобы перейти к процессу реального решения, мы должны связать асимметричное разложение с блочной схемой хранения, описанной в разделе 6,4.1. Как и прежде, положим Аы Аээ Метод решения должен быть подогнан под нашу схему хранения, в которой ненулевые элементы, расположенные вне блочной диагонали, хранятся столбец за столбцом, причем сохраняется естественный порядок матриц эгэ э'э ~Гр. В принятом нами методе используется то обстоятельство, что (Е„Е,',)-' (Е Ег)-э Зкб Гл б Методы фактор-деревьев Прямой ход Х.х = Ь Шаг 1.
Решить систему (ка11,и)х~ Ьь т Шаг 2. Для Ь 2, ..., р выполнить следуюшее: 2.1) Вычислить ܄— ܄— 1т т (к.аьЕк «) хк Ью 2.2) Решить систему Обратная подстановка Т1х = Шаг 1. Присвоить рабочему Шаг 2. Положить хе = хе. Шаг 8. Для Ь = р — 1, р— 3.1) х вектору х значение О. 2, ..., 1 выполнить следующею + Ук+~хь+т 3.2) Решить систему (1ц,укк~)ха= яь 3.3) Вычислить хк = хе — хь Отметим, что рабочий вектор х используется в обратной подстановке для накопления произведений. Как именно зто происходит, показано на рис.
6.5.4. Подпрограмма ТЗ31.Ч реализует зту схему решения. В отличие от ТЯРСТ она ие требует при задании древовидного разбиения вектора РАТНЕ)1, хотя и зависит от него неявно. Входной информацией для ТЫ11Г являются: древовидное разбиение (ИВ1К5, ХВЕК), диагональ О)АО, оболочка диагональных блоков (ХЕНЧ, ЕМУ) и ненулевые элементы внедиагональных блоков, хранимые посредством (ХЬ)ОХЕ, ЯО)к)Е, М23()ВВ). В подпрограмме Т331Ч вЂ” два основных цикла; один выполняет прямой ход, другой — обратную подстановку. В прямом ходе до обращения к подпрограммам Е(.31Ч и Е(131.7 модифицируется (циклом ОО 200 КО% =, ) вектор правых ча. ф б.б. Подпрограимы ТБРСТ и ТЗЯЕУ ййТ Рнс.
6.6А. Обратный ход н асимметричной схема с. с. с ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° » ° с с с с с с РЕШАЕТ ФАКТОРИЗОВАННУЮ СИСТЕМУ СО СТРУКТУРОЙ ФАКТОР " ДЕРЕВА МЕТОДОМ НЕЯВНОЙ ОБРАТНОЙ подстАновки. ВХОДНЫЕ ПАРАМЕТРЫ " (МВЬКБ, ХВ(.К) - РАЗБИЕНИЕ . (ХЕНЧ, ЕМЧ) - ОБОЛОЧКА ДИАГОНАЛЬНЫХ БЛОКОВ. (хмомх. НОВЕ, мавцвв) - структурА дднных ДЛЯ НЕНУЛЕВЫХ ЭЛЕМЕНТОВ ВНЕДИАГ, БЛОКОВ ИЗМЕНЯЕМЫЙ ПАРАМЕТРВНБ - НА ВХОДЕ - ВЕКТОР ПРАВЫХ ЧАСТЕЙ. НА ВЫХОДЕ - ВЕКТОР РЕШЕНИЯ. РАБОЧИЙ ВЕКТОРТЕИР - ИСПОЛЬЗУЕТСЯ В ОБРАТНОЙ ПОДСТАНОВКЕ.
С С С С С С С С С С С ПОДПРОГРАММЫ " ЕЬБ(.Ч, ЕНБЬЧ. С 3. ° ° ° * ° С ° » ° ° » ° ° »» ° »» ° ° » ° »*» ° ° ° ° ° » ° ° ° ° ° ° »» ° ° » ° » ° » ° » ° »»»»» ЗОВВООТ1МЕ ТББЬЧ ( МВЬКБ, ХВЬК, ЫАО, ХЕНЧ, ЕМЧ, 1 ХМ(ВЮ, МОМ2, МЕБОВБ, йНБ, ТЕМР ) С 3' ° ° ° ° ° ° » ° »»» ° ° ° ° » ° ° ° »» ° » ° » ° » ° ° ° ° ° » ° ° ° »» (ХЮВЬЕ РВЕС1$10М СООМТ, ОР$ С<ВЕКОМ /БРКОРБ/ ОРБ ВЕА!. РТАО(1), ЕМЧ(1), МОНЕ(1), ВНБ(1), ТЕИР(1), 3 1МТЕОЕВ МЕБОВБ(!), ХВ(К(1) 1МТЕОЕВ ХЕНЧ(1), ХМО)Е(!), СОЬ, СО!.1, СО!.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
