Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 47
Текст из файла (страница 47)
Эти программы указывают, каждая для своей схемы, порядок, в котором должны вызываться подпрограммы при решении данной разреженной системы. Заметьте, что это всего лишь скелетные программы; предполагается, что нужные массивы были описаны соответствующим образом и не выполняется никакой проверки возможных ошибок. При вызове подпрограммы упорядочения считается, что расположение ненулевых элементов разреженной матрицы гв задано 304 Приложение А.
йзказания к использованию подпрограмм посредством структуры смежности, хранимой парой массивов (ХАРЗ, АР,)!ь(Су). Маловероятно, чтобы у пользователя были под рукой удобные средства для заготовки такого представления. Поэтому он должен самостоятельно сформировать требуемую структуру до выполнения упорядочивающего шага. СФОРМИРОВАТЬ ДЛЯ СИСТЕМЫ АХ = В МАССИВЫ ХАОг И АОЗМСУ. скз ь семя)(м. хлпз, Аозмст, мАБк. Рекм, хьз, ьз ) САЬЬ 1МЧК5Е(М, РЕКМ, 1МЧР) САЗ 3. БМВГСТ(М, ХАО), АО1МСЧ, РЕКМ, 1 МУР, ХЬМХ, МОРЯ, ХМХБНВ, Мха ОВ, ЗЧОГЯЗВ, НСНЗ.МК, МНСЗ.МК, МА 5 К, ГЬАС ) ВВЕСТИ ЧИСЛОВЫЕ ЗНАЧЕНИЯ В йн2 ОТАВ И ЙНВ. САЬЬ СБГСТ(М, ХЬМЕ, ЬМЕ, ХМЕБОВ, МЕБОВ, О1АС, ЬЗМК, Г1КБТ .
ТЕМРЧ,1ЕКК) САЬЬ СББЗ Ч(М,ХЬМХ,1МХ,ХМЕЯЗВ,МЕБНВ,О1АС,КИБ) с с с с с с СЕЙЧАС В ННВ НАХОДИТСЯ ПЕРЕУПОРЯДОЧЕННОЕ РЕШЕНИЕ- ВОССТАНОВИТЬ ИСХОДНЫЙ ПОРЯДОК НЕИЗВЕСТНЫХ. САЗ Ь РЕКМКЧ(М,КНБ,РЕКМ) Рнс. А.З.Б. Скелетная ведущая программа для метода вложенных сечений. Формирование структуры смежности не является тривиальной задачей, особенно в тех случаях, когда пары (з, !), для которых ап ныл, задаются в произвольном порядке. Мы не будем здесь обсуждать эту задачу. Упражнения 3.3.! и 3.36 главы 3 указывают способ частичного ее решения.
Описываемый в Приложении В пакет ВРАВВРАК дает средства для генерирования структуры смежности в формате пары массивов (ХАР3, АШ !х) С'1') . В текстах скелетных программ встречаются две подпрограммы, которые не упоминались прежде. Подпрограмма 1)х(ЧВВЕ, вызываемая после того, как было определено упорядочение РЕ!(М, используется для вычисления обратного упорядочения (или перестановки) 1)Х)Ъ'Р. Вектор 1!ч'и'Р нужен при формировании структуры данных для разложения и при занесении в нее числовых значений. й А г Пример ноднрограммы ввода числовых значений ЗОБ Когда проработают численные подпрограммы разложения и решения треугольных систем, будет получено решение х переупорядоченной системы (РАР )х=РЬ.
Подпрограмма РЕКМКЧ используется для обратного переупорядочения вектора х к исходному порядку неизвестных. После того как формирование структуры данных для треугольного множителя успешно завершено, пользователь должен задать реальные числовые значения коэффициентов матрицы А и правой' части Ь. Чтобы правильно разместить эти числа в структуре данных, пользователю требуется детальное знание схемы хранения. В следующем параграфе мы опишем одну иэ подпрограмм, осуществляющих ввод матрицы.
Понятно, что для разных методов хранения такие подпрограммы ввода должны быть различны. Разобрав пример из $ А.2, читатель сможет самостоятельно написать аналогичные подпрограммы для других методов. Нужно подчеркнуть, что в пакете ЗРАЕЗРАК (см. Приложение В) имеются все необходимые подпрограммы ввода й А.2. Пример подпрограммы ввода числовых значений Прежде чем обратиться к численным подпрограммам разреженного метода, необходимо ввести в структуру данных число вые значения коэффициентов.
Здесь мы разберем подпрограмму которая в рамках метода древовидного разбиения вводит число вое значение элемента аи в соответствующую структуру данных. Напомним (глава 6), что в этой схеме хранения предусмотрены три вектора для числовых значений. Вектор Р1АО содержит диагональные элементы матрицы Элементы, принадлежащие оболочке диагональных блоков, хранятся массивом ЕМЧ. Наконец, в векторе МОМУ находятся ненулевые элементы, расположенные вне блочной диагонали. Для заданного ненулевого элемента а„подпрограмма АРА1) модифицирует один из трех векторов хранения Р!АС, ЕМЧ или МОМУ, в зависимости от местонахождения этого элемента в матрице.
Оператор вызова подпрограммы ввода матричного элемента выглядит так: СА11. АРА1Л (1, Л, ЧА1Л)Е, 1МЧР, Р1АО, ХЕМЧ, ЕМЧ, ХМОМХ, МЕЯ()ВБ, 1ЕЙВ). Здесь 1 и Л вЂ” индексы элемента в исходной (т. е. еще не пере- упорядоченной) матрице А, а ЧАШŠ— его числовое значение. Подпрограмма прибавляет ЧАШЕ к значению ао, находящемуся в данный момент в памяти. Сложение вместо присваива. ния используется для того, чтобы приспособиться к ситуациям, э А.8 Совмещение паиеги в Фореране 307 НОМЕ(К) МОНЕ(К) 4 ЧА1.ОЕ НЕТОЯМ СОМТ1МОЕ 0') ТО 500 С С С 400 ЭЛЕМЕНТ НАХОДИТСЯ НА ДИАГОНАЛИ МАТРИЦЫ.
01АО(1) 01АО(1) 4 ЧАШЕ ЯЕТОйМ С С С 500 УСТАНОВИТЬ ИНДИКАТОР ОШИБКИ. о 1ЕЯЯ 5 НЕТОНМ Ввод числовых значений для вектора правых частей Ь можно выполнить аналогичным образом. й'А.З. Совмещение памяти в Фортране Рассмотрим скелетную ведущую программу профильного ме. тода (рис. А.1,1), Подпрограмма ОЕХКСМ генерирует упорядочение РЕЯМ, исходя из структуры смежности (ХАО,), А1УЯМС'1') Она использует также два рабочих вектора МАЯК и Х1В После ввода числовых значений в структуру данных для обо лочки рабочие векторы МАВК и Х1.$ уже больше не нужны. когда значения элементовматрицы получаются путем накопления (так обстоит дело в некоторых конечноэлементных приложе- НИЯХ). Подпрограмма проверяет, будет ли заданный ненулевой элемент принадлежать диагонали или оболочке диагональных блоков. Если да, то его значение прибавляется к соответствующей компоненте векторов О!АО или ЕМУ.
В противном случае производится поиск в структуре индексов (ХХОХЕ, ХЕЯЯВВ), со. ответствующей ненулевым элементам, расположенным вне блочной диагонали; после этого Ъ'А1.(ЯЕ прибавляется к соответствующей компоненте вектора ХОМЕ. Именно по той причине, что в подпрограмме АОА1Я присваивание заменено сложением, до ввода числовых значений элементов А нужно установить нулевое начальное состояние на пространстве, отведенном для хранения Я, Поэтому ввод матрицы ч в методе древовидного разбиения должен осуществляться так( ° Установить нулевое начальное состояние для векторов О1АО, ЕМУ и ХОМЕ.
° (Повторные обращения к подпрограмме АЭА1Я). Зоа Приложение А указания к использованию подпрограмм Более того, даже структура смежности (ХАШ, АР,)ХС'1') в дальнейшем не понадобится. При необходимости экономии память, отведенная для указанных векторов, может быть переструктурирована и использована подпрограммами численного решения для других целей.
Аналогичные замечания применимы и к остальным разреженным методам. В этом разделе мы покажем, как можно осуществить совмещение памяти в Фортране. Общий прием состоит в том, что в ведущей программе описывается большой массив, из которого распределяется память для всех массивов, необходимых подпро; граммам.
Ведущая программа управляет памятью с помощью указателей, регистрирующих положение массивов нз подпрограмм в основном векторе хранения. В качестве иллюстрации предположим, что имеются две подпрограммы ЯЗВ! н Я)В2: БОВКООТ!!МЕ Я)В 1 (Х, 1', Е), Я)В(<01)Т11!Е Я)В 2 (Х, 1', 1), Ч). Для подпрограммы Б<ЗВ! нужны два целых массива Х и 1' длиной соответственно 100 и 500 н еще рабочий целый массив Е длины 400.
Подпрограмме 81)В2 требуются четыре массива: Х и '1' — векторы на выходе ЯЗВ! — н еше два массива П и Ч длины 40 и 200 соответственно. Т Т (х (т )Х тт 11) 1Ч Нижеследующая иллюстративная ведущая программа использует основной вектор хранения Б(1000) и последовательно вызывает подпрограммы 81)В! и Я)В2.
Она управляет. памятью с помощью указателей, «перемещаемых» в массиве Ь, 1мтесеа 5<1000) 1Х - 1 1Ч - 1Х + 1ОО 4г - 1ч + аоо сяьь зпв1 (а(1Х),5(1У).5(17)) то = тт ь 5ОО 1Ч. Гнь Вф сил. ацва (5<тх),5<тт),5<то),5<тч)> Э АЗ. Совмещение намети в Фортране 809 Таким образом, память, использовавшаяся рабочим вектором Е, может быть распределена для векторов (3 и Ч. Ту же технику совмещения памяти можно использовать при работе с последовательностью подпрограмм, реализующих метод решения разреженных систем.
Пакет БРА)тЬРАК (Приложение В) по существу опирается на эту самую технику в системе подпрограмм интер4ейса, которая избавляет пользователя от всех задач управления памятью при использовании подпрограмм этой книги. Приложение В. БРАКЬРАК. Пакет для разреженных матрац $ В.1. Мотивировка Скелетные программы Приложения А иллюстрируют некоторые важные характеристики разреженных матричных программ и подпрограмм. Во-первых, нестандартные структуры данных, используемые для хранения разреженных матриц, приводят к тому, что подпрограммы имеют чересчур длинные списки параметров.
Смысл большей части этих параметров мало или вовсе ие знаком пользователю, если только он (или она) не понимает и помнит все детали применяемой структуры данных. Во-вторых, процесс вычислений состоит из нескольких различных фаз с многочисленными возможностями совмещения памяти. Чтобы повысить эффективность подпрограмм, пользователь должен определить, какие массивы, эксплуатируемые в одном модуле, понадобятся в качестве входных для другого, а какие больше не потребуются, и, следовательно, память, занимаемая ими,может быть использована для других целей.
В-третьих, во всех случаях количество памяти, необходимой для этапов численного решения, неизвестно до тех пор, пока не будет завершен хотя бы один из предыдуших этапов. Обычно вто количество становится известно лишь по выполнении подпрограммы распределения памяти (например, гИЕ)чУ). В некоторых случаях нельзя заранее предсказать даже, какой объем памяти нужен для успешного выполнения самой подпрограммы распределения (так обстоит дело, например, с ЬМВгСТ). Поэтому нередко вычисления приходится прерывать на полпути изва недостатка памяти, и пользователь, если он желает избежать повторения законченных фрагментов процесса, должен каким-то способом сохранить информацию, необходимую для возобновления вычислений. Указанные обстоятельства, а также наша собственная практика в использовании «разреженного» матобеспечения побудили нас сконструировать для пользователя удобный интерфейс с описанными в этой книге подпрограммами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
