Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 51
Текст из файла (страница 51)
119-130. [РоосЬ 1973] $). %. РоосЬ, апб А !ч!е!Вег, "А кигчеу оГ !пбех)п8 |есЬп|Киев Гог крапе та|псе|," АСМ Сотриплу Яитчеук 5 (1973), рр. 109-133. [Коке 1972а] О, Л. Коке, "А ВгарЬ-йеогеВс в!лбу оГ |Ье пивепса1 во!ибоп оГ враг;е ров|пче деВв|е вув|етв оГ !)пеаг ег!иабопв," в Старб ТЬготу аи|Г Сотрийлу, еб!|ег! Ьу К. С. Кеаб, Асаг)ев!с Ргем, Хекч Уотерс (1972). [Коке 1972Ь] О. Л. Коке, апб К. А. %!ВоиВЬЬу, ед., братке Матисе| ал|Г йети Арр!Гсайоы, Р!епип| Ргев (1972).
[К те 1974] О. Я. Коке, апг) С. Г. %спел, "Атовабс лев!еб г)!ввесг)оп," Ртос. АСМ )уаг. СолГ. (1974), рр, 82-88. [Кове 1975] О. 3. Коке, апб К. Е. Тат)ап, "'А!Вопйпис авресп оГ чег|ех е!1в(па| !оп," Ртос 7|Ь Алииа! ЯутровГит ол йе ТЬеоту оГ Сотриг(лу (! 975), рр. 245-254. [Коке 1976а] О.
Л. Коке, К. Е. Тиг1ап, апг! С. Б. ЕпеЬег, "А18опйпис а|реев оГ чег|ех е! ишпаИоп оп ВгарЬ|," ЕГАМ Х ол Сотрийлх 5 (1976), рр. 266-283. [Коке 1976Ь) О. 3. Коке, апд С. К %спел, "А гесигв!че апа!ув!в оГ гВввесВоп вггаге8!ев," !п Ератке Магг(и Сотригабол, егВ|еб Ьу 3. К. Випсб апг) О, 3. Коке, Асабев!с Ргевв (1976), рр. 59-84. [Кубег 1974] В. С. Кубег, "ТЬе РРОКТ Чег)Г!ег," Зоуг|чате Ртасгссе ал|Г Ехргпелсг 4 (1974), рр. 359-377, [ЯЬеппап 1975] А. Н. ЯЬегвап, "Оп йе еГВс!еп| во(иВоп оГ врагке вувевв оГ!!пеаг апд поп1веаг ециайопв," Лерг. Аго. 46, Оер|.
оГ Соврыег Зс!епсе, Уа!е Оп(четв!!у (1975). [ВЫег 1976) 11 К. БЬ!ег, "1пчегВп8 враг|с та|псе| Ьу |гее рагг!1!оп(п8," Х Кег оГ гба )Чаг. Вит„ау Игал|уатт)к, УВОЬ, ~Чо 2 (1976). [Бвуй 1974] %. Р. Яву|Ь, апг) %, М. ) Вела), "Ап а18опЦ|в Гог ВпгВп8 йе гВа|песег оГ а ВгарЬ," ГРГР Солбтевв 74, Хогй-Но)!апд РиЬЬ Со. (1974), рр. 500-503. [Бгеччагг 1973) С. %. Йгемагг, Глгтогуисг(ои го Ма|туп Сотри|а||от, Асаг)ев!с Ргев, )4ечт УогЬ (1973).
[Яггапб 1973] СВЬеН %. Вггаи8, апд Сео|8е 3. Р(х, Аи АиаГув(к о2 йе РГи(гг ЕГетет Мегбог(, РгепВсе-НаВ Гпс., Лигерогурп Епа!епооб СНГ/в, )Ч. 3 (1973). [Зггаввеп 1969) Ъ'. Еггаавеп, "Сапвяап е!/гптабоп В пог орнгла1," /читег. Мл/К /3 (1969), рр 354-356 [Т/ппеу 1969) "гхг. Г. Т1ппеу, "Сопппепм оп пяпа врагвну гесьпщпев Гог роюег вувгегп ргоЫетв," /п Ярлгзе Млгг/л Ргосеег//луз.
1ВМ КевеагсЬ Кер!. КА) 3 — 12 — 69 (/969) [газка 1962) и. Я. )газка, Млгпх Веглг/уе Алл/уз/я Ргепг(се-На)1, Еп81еэоог/ С/!Г/в. )Ч (1962) [)гоп Рпсьв 1972) С. гоп Рпсьв, К и. Коу, апб Е. Ясьгет, "Нуреггоагг(х во1п6оп оГ /агае вега оГ вупппегпс ровнгее бейпне 1теаг еяпанопв," Сотр Мегй гл Арр/ МесЬ ллг/ Елугу / (1972), рр. 197-216 [й/1/Ыпвоп 1961) К Н. %ВИпят, "Еггог апа!увj оГ 6/гесг гпегнобв оГ глагпх тгегяоп," з Аззос Сотриг МлсЬ 8 (1961), рр.
281 — 330 [йг//воп 1974) Е. 1 тг/1!воп, Е. 1, Ванге, апб %. Р. )уоЬег!у, "Гу)гесг во1и6оп оГ 1агае вувгегпв оГ 1)пеаг еяпа6опв," Сотригегз ллг/ оиисгигез 4 (1974), рр 363-372 [г'оппа 1971) О. М. вопия, Ееглгме Яо/иг/ол оГ Глгхе Етелг Кузгетз, Асабепис Ргевв, /Чеи Уогх (1971). [2/епЫеп/сх 1977) О. С. 21ягИеп!сх, ТЬе р/л/ге Е/стел/ МегЬогй Мсбгап Н/Н, 1.опбоп (1977). Работы, переведенные на русски/7 язык Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.— М,; Мир, 1979. Берж К. Теория графов и ее применения.— М.: ИЛ, 1962.
Форсайт Дж. Еп Молер К. Численное решение систем линейных алгебраических уравнений. — М.: Мир, 1969. Мартин Р. С., Уилкинсон Дж.— в сб. Уилкинсон Дж., Райнш. Справочник алгоритмов иа языке АЛГОЛ. Линейная алгебра.— М.: Машиностроение, 1976. Стренг Г., Фикс Дж. Теория метода конечных элементов. — М.: Мир, !977. Оглавление адачи я иещнх с От переводчина Предисловие Глава 7.
Введение . з 1.О. Об этой книге . !.1. Метод Холесского и проблема упорядочения . 1.2. Положительно определенные и неопределенные матричные з $ !.3, Итерационные н прямые методы . Гаева 2. Вводные сведения 3 2.0. Введение 2.0.1. Обозначения Упражнения 3 2.1. Алгоритм разложения 2.1.1 Существонаиие и единственность разложения . 2.!.2. Вычисление разложения 2.1.3 Разложение разреженных матриц, Упражнения $2.2, Решение треугольных систем, 22.! Вычисление решения 2.2.2. Число операций Упражнения $2.3.
Некоторые практичсские замечания 2.3.1. Запросы к памяти . 2.3.2 Время исполнения Упражнения Глава 3. Некоторые сведения из теории арифов и ее применение вледоввнию реареаеенных симметричны» матриц. 3.0. Введение 3.1. Основная терминология и некоторые определения . Упражнения 6 3.2. Машинное представление графов 9 3.3.
Некоторые общие сведения о подпрограммах, оперирую Р г афами празкнення Глава 4. Ленточные и нрофиланые методы . 9 4.0. Введение $4.1. Ленточный метод Упражнения $4.2 Профильный метод 4.2.! Матричная формулировка 4.2.2 Интерпретация иа языке графов Упражнения 9 4.3. Профильные упорядочения 4.3! Обратный алгоритм Катхилла — Макки . 4.3.2 Определение начально~о узла . 5 7 9 9 !0 П 18 21 2! 21 23 23 23 25 29 32 зз Зз 35 36 Зз 39 42 43 44 44 44 49 49 52 54 56 56 59 59 бч 63 64 65 65 69 Оглавление 331 4.3.3.
Подпрограммы поиска начального узла . . . . . . . . 72 4.3.4. Подпрограммы обратного алгоритма Катхилла — Макки . 76 Упражнения.................... 83 $4.4. Реализация профильного иетола............. 85 4.4.1. Профильная схема хранения ........... 85 4.4.2. Подпрограмма распределения памяти Р14ЕХЧ (Р!)44-Е(4- Не!оре)........,.........., .
86 в 4.5. Подпрограммы численного решения ЕВРСТ, ЕЕВИЧ и Е1)БЕН 88 4.5.1. Подпрограммы для решения треугольных систем ЕЕ51Ч и ЕОЯЧ................, 88 4.5.2 Подпрограмма разложения ЕВРСТ.......... 92 Упражнения 96 $4.6. Дополнительные замечания . . . . . . . . . . . . . . 96 Глава 6. Унавереальлме разрелгенкме методм......,.... „. 98 6 5.0. Введение 98 6 5.1, Симметричное разложение 98 5.1.1. Модель графов исключения....,....... 99 5.1.2.
Моделирование исключения посредством достижимых множеств !02 Упражнении . . . . . . . . . . . . . . . . . . . . 107 6 5.2. Машинное представление графов исключения...,.... !07 5.2.1. Явные и неявные представления.......... 108 5.2.2. Модель фактор. графов.............. 109 5.2.3.
Реализация фактор-модели ............ 114 Упражнения .................... 119 й 5.3. Алгоритм минимальной степени 119 5.3.1. Основной алгоритм , , . . . . . . . . . . . . . 121 5.3.2 Описание алгоритма минимальной степени посредством достижимых множеств................. 121 5.3.3. Ускорение алгоритма . . . . . . . . . . , . . . 124 5.3.4. Реализация алгоритма минимальной степени . . .
. . . !29 Упражнения.......,............ 141 6 5.4. Схемы хранения разреженных матриц.....,,... 143 5.4.1. Обычная схема 143 5.4.2. Компактная схема.....,,......... 145 5,4.3. О символическом разложении....,...... 148 5.4.4, Распределение памяти для компактной схемы и подпрограмма 5МВРСТ 152 Упражнения 157 6 55 Подпрограммы численного разложения н решения,..... 157 5.5,1. Подпрограмма ОВРСТ (Оепега! зрагзе Бушше!пс РаСТопха!1оп) ..................... 158 5.5.2.
Подпрограмма ОВВЕЧ (Оепега( зрагзе Вупппе1гк Во1.Не) 162 6 56. Дополнительные замечания ...........,,, !63 Глава 6. Методы фактор-деревьев для колечноэлементнык и коаечнорвзноетнмл задач . . 164 6.0. Введение . 164 6,1, Решение блочных систем уравнений.......,... 165 6.!.1. Разложение матрицы блочного порядка два...., 165 6.1.2. Решение треугольной системы блочного порядка два ., 170 Упражнения......,....,...,... 171 $6,2.
Фактор-графы, деревья в древовидные разбиения . . . . . . 172 6.2.1. Блочные матрицы и фактор. графы . . . . . . . . . . 172 62.2. Деревья, фактор. деревья и древовидные разбиения . . . 175 6.2.3. Асимметричное блочное разложение и неявное блочное ре. шенне систем с древовидным разбиением . .
. . . . . . . 178 Упражнения °,,..., ...,, 179 332 Озлавление $ 6.3. Алгоритм вызволения древовидного разбиения' . . . . . . 182 6.3.1, Эвристический алгоритм . . . . . . . . . . . . . 182 6.3.2. Подпрограммы аля вычисления зревоаидиаго разбиения . 185 Упражнение.............. - 198 $6А. Снима хранения н процедура распределения памяти .. !99 6.4.1. Схема храпения .............. 199 6.4.2. Внутреннее ьереупаряаочеиие блоков . . . . . , .
. . 202 6Аля Рвспределение памяти н подпрограммы Р(чТЕ(ч"т', Р(чОЕ(чХ и Р(ч"ТАРЗ 207 $6.6. Подпрограммы численных этапов ТЬРСТ (Тгее Ьушше(г!с РаСТопзабоп) и Т56(.'т' (Тгее 5упппе!гм 3о(Ле) ..., . 2Н 6.5.1, Вычисление матричной поправки......... 2И 6.5.2. Подпрограмма ТЬРСТ (Тгее 5ушп|е1г1с РаСТопхабоп), . 2!7 6.5.3 Подпрограмма ТББРУ (Тгее Бушгпе1г(с 5о(.Уе)..... 222 Упражнение.............., 230 $6.6.
Дополнительные замечания ..........,... 230 Глава 7. Методы иараллеланмг сечений для каивчиоэ*ементямк задач 232 7.0. Введение .........,.......... 232 7А. Пример — задача на (ш л, !).сетке............ 232 7.1.1. Упорядочение посредствам параллельных сечений.... 232 7;1.2, Требования к памяти..........,.... 235 7.1.3. Число операций при разложении.......... 237 7.1.4.
Число операций прн решении.......,..., 240 Упражнения ............... 240 $ 7.2. Алгоритм построения параллельных сечений для задач на яерегуляриых сетках . . . . . . . , . . . . . . . , 242 7.2.1. Алгоритм.........,......,,, 242 7.2.2. Подпрограммы для вычисления разбиения методом параллельных сечений , 244 $ 7.3. Об определении структуры оболочки диагональных блоков . . 250 7 3.!.
Постановив задачи . . . . . , . . . . , . . . . 250 7.3.2. Характеризация оболочлн блочной диагонали посредством достижимых множеств Глава 9, гуислеиимв екслеримеитм .....,...,.... 282 9.0. Введение 9.1. Описание тестовык задач 9,2.
Что означают приведенные числа 9.3. Срзвяение методов 9 3,1 Критерии сравнения методов . . 282 . 286 293 . 293 7.3.3, Алгоритм и подпрограммы вычисления оболочки диаго. нальных блоков............... 254 7.3.4. Анализ временной сложности алгоритма....... 260 Упражнения.................... 260 $7А. Дополнительные замечания .............. 261 Глава 8.
Методы влоткеилмл сечений 263 $8,0. Введение.....,....,,...,, 263 $8.1. Вложенные сечения регулярной сетки........... 263 8.1.1. Упорядочение...,,.........., 263 8.1.2. Требования к памяти.........,, 266 8.1.3. Числа операций................. 270 8.1.4. Оптимальность упорядочения...'........ 272 Упражнения ..........,....., .. 274 $82. Вложенные сечения для произвольных задач......., 275 8.2.1, Эвристический алгоритм . . . . . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
