Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 43
Текст из файла (страница 43)
Таким образом, построенные сетки можно рассматривать как графы соответствующих матричных задач, 4 5 6 7 8 9 10 11 12 32 8 9 8 12 9 б 6 19 265 406 577 778 1009 1270 1561 1882 2233 744 1155 1656 2247 2928 3699 4560 5511 6552 1089 1009 1180 1377 936 1440 1138 1141 1349 3136 2928 3285 3808 2665 4032 3156 3162 3876 286 Гл. 9. Численные эксперименты Из этих сеток конструируются два набора тестовых задач.
В тестовый набор ~1 входят девять осйовных сеточных задач, взятых с такими коэффициентами разбиения, чтобы получающиеся нз иих системы имели примерно от 1000 до 1500 уравнений (см. таблицу 9,1.1). Второй набор — это последовательность из девя1и задач, полученных разбиением основной сетки (градуированное Е иа рис. 9.1.1) с коэффициентами з = 4, 5, ..., 12. Данные об этих задачах см. в таблице 9.1.2.
$9.2. Что означают приведенные числа В главах 4 — 8 были описаны пять методов, для которых здесь будет использоваться следующая мнемоника: КСМ вЂ” обратный алгоритм Катхилла — Макки, КЯТ вЂ” алгоритм рафинированного древовидного разбиения, 1ФР— алгоритм параллельных сечений, ЯМР— алгоритм минимальной степени с использованием факторизации и ХР— алгоритм вложенных сечений. В то же время мы описали лишь три основные структуры данных и соответствующие подпрограммы численных этапов. Дело в том, что алгоритмы 1%Р и ЩТ могут использовать одни и те же структуры данных, и это же относится к алгоритмам ЯМР и ХР. В таблицах, приводимых в конце этого параграфа, слово «операции» означает лсультипликативные операции (умножения и деления).
По причинам, уже обсуждавшимся в главе 2, мы рассматриваем число таких операций как разумную меру количества выполненной арифметики: ведь в матричных вычислениях арифметические операции обычно образуют последовательность пар «умножить — сложить». Время исполнения измеряется в секундах и сообщается для машины 1ВМ 3031. Эта машина имеет весьма современную архитектуру и использует сверхоперативную память. Типовые операции иа ией требуют от 0.4 микросекунды для операций с фиксированной точкой иад регистровыми операндами до примерно 7 микросекунд для деления с плавающей точкой. Как обычно, в вычислительной среде с многопрограммной обработкой трудно получить точное время работы программы; поэтому приводимые нами ре-. зультаты могут содержать ошибки в пределах 10е)е.
Мы пытались несколько уменьшить эти ошибки, прибегая к неоднократному повторению счета или выходу иа машину в такое время, когда она слабо загружена. Программы компилировались в оптимизирующем режиме транслятора, что обычно дает очень эффективные машинные программы. Напомним один из выводов параграфа 2.3: при сравнении различных стратегий упорядочения может оказаться разумным игнорирование одного или нескольких из четырех основных б 2.2. Чга означают приведенные числа 287 Таблица 2.22 Массивы, учитываемые в статистике памяти для каждой фазм каждого иа пяти методов. Память, необходимая для подчеркнутых массивов в столбце «числеииые етапым регистрируется как «иакладиая память» ХАОз,лизнет, ХЛО1,АОЛЧСХ, РЕЕМ 1МЧР,ЙНБ )сСМ Рейм,х).5, Рерм, 1мчР, хеьзч хеьзч, емч,в1АО МАБК Р ЕЙМ, ВМ(ЗМ, 1%'зз ьэ(вовс),хвьк, млак.хз 5 ХЛО1,ЛВ1МСЧ, РЕЙН 1МЧР,ЙНБ, РЕЙМ, 1МЧР, ХВЗ.К, ХЕНЧ, ЕМЧ,О1АС, МАЯК,М,АЙКЕЙ, ХЭКЗМЕ,МЕ5ПВ5,МСМЕ, РАТНЕЙ, ХЕМЧ, ТЕМРЧ, Р1Й5Т тиэ()ВБ, Йсн5ет(хзчо)ю) ХЛвз,Лизнет, Хавз,лвзнсу, РЕЙН,ХВЫ(,МЛБК, РЕЙН,ТМЧР,ХВЗК, от м(юьчь(вм(ы), млэк,рлтней, зяпже, чп|о и еьмяе ЗОБ,ЬБ(2ПВС) ХЕМЧ,ХМОМЕ, МЕБИВ5 ХЛО1,ЛОЛЧСТ, РЕМИ ПЧЧР.ЙНБ, масычк, Йсньмк, темРч МАЙКЕЙ ХЛВ1 .
ЛОЛЧСУ . РЕЙН,ЬБ, 1Ч1) хьэ,нлБК хлвз. 2 коппи ЛО1МСЧ, РЕЙМ, мликеа, Оес, ЙСНБЕТ,МВЙНО, Ч51ЕЕ ()1™К (сМ0 пзе же, чяю и выме пю иы, чмо и палее шагов общей процедуры решения. По этой причине в численных экспериментах мы регистрировали время исполнения каждого из четырех шагов: упорядочения, распределения памяти, разложения и решения треугольных систем. В таблицах приводятся четыре вида статистики, связанной с памятью: палзять на этапе упорядочения, память на этапе распределения, общая память (память на численных этапах) и накладная память.
Все наши эксперименты проводились с помощью пакета для разреженных матриц, называемого ЯРА)сВРАК (беогйе, 1978 а, 1979 а). В нем все необходимые для работы массивы распределяются из одного большого одномерного мас. сива. Сообщаемые нами данные о памяти на этапах упорядочения, распределения и численного решения относятся как раз к количеству памяти, использованной в рамках этого большого массива. Мы полагаем, следовательно, что эти числа отражают 288 Гл У.
Численные зоспераменчы Таблица У.2.2 Результаты алгоритма НСМ длз тестовых задач набора 4ч! (число операций и памигь масштабированы умножением на 1О-') ЗаВача ЯмРпбечвние ~фДшапнснае Чнспеинша атапьг Время Памшнь Врнча Пшшшь Время Чнюо операшш Память женив Решшше Раино"решеноа Пггвьап жш тш 936 0.2! 0.91 0.04 0.91 2.85 0.40 1009 0.27 0.99 0.04 0.99 3.43 0.46 1089 0.24 1,06 0.05 1.06 3.25 0.45 1440 0.32 1.38 0.06 1,38 4.74 0,62 1180 0.32 1.13 0.06 1.13 2.86 0.44 1377 0.30 1.31 0.06 1.31 !.99 0.40 1138 0.30 1.09 0.06 1.09 2.81 0.45 1141 0.25 1.09 0.05 !.09 4.40 0.52 !349 0.36 1.31 0.06 1.31 5.74 0.69 30.18 4.55 2.65 0.28 37.49 5,25 3.03 0.30 34.46 5.11 2.99 0.33 53.77 7.23 4.!9 0.43 31.87 '5.17 3.06 0.35 18,64 4.34 2.72 0.41 28.88 4.92 2.92 0.34 54.08 6.75 3.83 0.34 64.95 7.95 4,52 0.40 Таблица 9.2.2 Результаты алгоритма !цг(3 дла тестовых задач набора (ч! (число операций и память масштабнрованы умножением на !О ') зорана Ппоьшуочвинв нио осанне Часпенншв отавы Время Пенять Време Пемшгн Прелы число операциу Память еопо- рошапав оо"о решенно ущою он" маньи менее наг скорее количества памяти, нужной при работе подпрограмм в практических ситуациях, а не тот неприводимый минимум, который требуется для каждой из них в отдельности.
Проиллюстрируем сказанное примером. Подпрограмма упорядочения ОМ0 при работе портит входной граф. При пользовании этой подпрограммой самой по себе нет необходимости сохранять граф исходной матрицы, однако в большинстве случаев он все же бу. дет сохранен, так как нужен для следующего шага — символического разложения, Цифра, приводимая для ЯМ() в столбце 936 1009 1'89 1440 !!80 1377 1138 !!41 !349 0.38 1.
! 9 0.25 О 47 1.29 О 28 0.45 1.39 0.30 0.60 !.8! 0.39 0.55 !.48 0.33 0.57 ! 73 0.37 0.52 !.43 0.30 0.46 !.43 0.31 06! 1.72 О 36 !.24 1.35 1.46 1.89 1.56 !.82 !.49 1.49 1.79 3.39 0.36 5.47 0.40 5.23 0.42 4.43 0.52 3.35 0.42 3.25 0.49 3.!7 0.41 5.10 0.44 7.03 0.56 26.60 3.06 44.90 3.66 41.48 3.62 33.04 4.32 24.50 3.48 21,41 3.57 23.56 3.48 41.08 3.77 58.38 4.79 1.72 0.61 1.94 0.66 2.03 0.72 2.5! 0.94 2.03 0.78 2.21 0.92 1.98 0.75 2.07 0.74 2.57 0.88 б 9.2. Что означают нриоеденнь!е «исла 289 Таблица 9.2.4 результаты алгоритма К!27 для тестовых задач набора ~1 (число операпий и память масштабироваиы умножением иа 1О-В Видена Упорядочение Рисляе еление яанягнн Чигеенные этапы дрони Память врете понять Вренгн чиале онеричий потеть ееэннен Решенне, еэнэ решениедйыел еиеа 0.53 32.84 0.59 39.32 0.61 37.04 082 5546 0.54 13.52 0.58 11.69 0,60 31.98 0.72 63.98 0.86 67.68 0.18 1Л 9 0.15 0.26 1.29 0.16 022 1 39 017 0,2() 1,81 О 22 ОЗ! !.48 О 19 О 28 1,73.
О 2! 0.30 1.43 0.17 0.23 1.4 3 О.! 7 0.36 1.72 0.2 1 1.19 4.17 1.30 4.88 1.40 4.68 1.81 6.75 1.49 2.39 174 230 1.43 4.32 1.42 7.18 1,72 7.79 Таблица 9.2р Результаты алгоритма М$3 для тестовых задач набора 4Я1 (число операпий и память масштабяроваиы умиожеиием иа 10-') аогуочи йзгорядотояиорое Чирритмт лтаяьг ирштяПаттиьареггиПатет тютя ииоеооиоявьмй Палгягрь. те о решмтожвна рмттие 4!умея иея 16.25 2.96 2.73 1.15 3!.1! 4.00 3.38 1.29 26.82 3.91 3.43 1.36 19.05 4.06 3.90 1.72 !4.22 3.15 3.09 1.40 15.71 3.59 3.54 1.61 16 89 3.32 3.!4 !.37 17.23 3.34 3.16 1.38 35.48 4.98 4.31 $.69 0.24 1.78 0.25 1,97 0.27 2.10 0.34 2.68 0.28 2.! 7 0.32 2.5! 0.27 2.1 $ 0.27 2,13 0.33 2.60 2.
$9 0.29 337 0.37 3.40 0.37 2.69 0.41 2.05 0.31 2.34 0.36 2.32 0.32 2.35 0.32 4.41 0.48 «память на этапе упорядочения», включпег в себя память, необходимую для хранения исходного графа. Еше один пример, Очевидно, что нет нужды сохранять массивы РЕгсМ и $$ч$3ТР после того, как завершено распределение памяти, поскольку подпрограммы разложения и решения треугольных систем не используют эти массивы. Однако, как правило, нх сохраняют, чтобы правильно разместить числовые значения коэффициентов А и Ь в структуре данных и чтобы восстановить исходный порядок компонент вектора д после того, как будет вычислено (переупорядоченное) решение. В таблице 9.2.! 936 1009 1089 !440 1!80 1377 1!38 114! 1349 936 1009 1089 !440 1180 1377 !!38 1141 1349 0.77 1.00 0.95 1.09 0.92 1.17 1.35 $.53 !.$0 1.25 $. 0 1.45 1. $5 1.20 1.$4 1ДО $.39 1.45 4.83 2.14 0.75 5.49 2.3Я 0 81 5.43 2.45 0.88 7.44 3,29 1.1 5 3 41 2.04 0.95 3.5 3 2.27 1.! 2 5.
1 3 2.4 1 0,9 1 6.92 2 86 0.91 8.30 3 42 1.08 290 Гл. У. Численные енснериненгы Таблица 92.б Результаты алгоритма ()М)3 длв тестовмх задач набора чг! (число операцнй и память масштабированы умножением на 1О-') Варвчи Улорярочвнив асл тичтяи Числоннтв отелы Врвнтртчляш|ремябамять Время Число овере лед Память щД~~~~а РвшалиежшД решеноваризоя 936 1.47 1.91 0 21 !.80 2 27 О 30 1009 !.57 2.08 0.24 1.97 3,37 0.37 1089 1.78 2.23 0.26 2.12 3.00 0.36 !440 2.33 2.91 0.34 2.74 2 70 0.42 1180 1.89 2.38 0.27 2.!9 1.44 0.27 1377 2.09 2.76 0.30 2.52 1.50 0.30 1!38 1.97 2.29 0.27 2.15 1.82 0,29 !141 2.07 2.29 0.27 2.17 2.03 0 31 1349 2.07 2.76 0.32 2.62 3.70 0.46 Таблица 92.7 Результаты алгоритма ИСМ длв тестовых задач набора чгз (число операций и память масттабнрованы умножением на 10-') Пирона илсрябечвн е исл~е июню Итлоьнив жюли Время Память Време Память Време числа еворипий Петтш жение РешениЕ женка РеетнавОйцаи тт лю- лю- клИ- 2.97 0.75 0.48 0.08 6.62 1.39 0.86 0.12 12.88 2.32 1.39 0.17 22.78 3.59 2.10 0.23 37.49 5.25 3.03 0.30 58.37 7,36 4,19 038 86.95 9.97 5.61 0.47 !24.90 13.14 7.32 0.56 174.10 16.91 9,35 0.67 перечислены массивы, учитываемые в нашей статистике памяти, для различных фаз вычислительного процесса (упорядочение, распределение памяти, разложение, решение) и для каждого из пяти методов.
Обозначение А(В) в этой таблице имеет следующий смысл: массивы А и В один вслед за другим используют одно и то же место в памяти. Строго говоря, следовало бы различать память на этапе разложения и память на этапе решения треугольным систем, так как несколько массивов, используемых подпрограммами ТЬгСТ и ОогСТ, не нужны соответствующим подпрограммам для треугольных систем, Однако эти массивы обычно малы в срав- 265 406 577 778 1009 1270 1561 1882 2233 0.07 0.25 0.12 0.39 0.16 0.56 0.22 0.76 0.27 0.99 0.34 1.25 0.42 1.54 0.51 1.86 0.62 2,.20 0.01 0.25 0.02 0.39 0,03 0.56 0.03 0.76 0.05 0.99 0.06 !.25 0.07 1.54 0.09 1.86 О.! 0 2.20 0.33 0.07 0.7 1 0.1 3 1.30 0.21 2.15 0.32 3.43 0.46 5,!9 0.62 7.50 0.83 !0.62 !.11 !4.44 1.40 19.34 3.! 1 30.91 3.95 2631 3.85 2!.62 4.21 9.86 2.72 10.00 2.99 13.80 3.04 16.24 3.20 32.41 4.82 2.83 1.18 3.36 !.29 3.42 !.38 4.04 1,79 2.90 1.42 3.25 !.62 3.04 !.41 3,14 1.43 4.26 1.71 б 9.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
