Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 45
Текст из файла (страница 45)
таблицу 9.2.1), Мы приводим оба вида стоимости, чтобы показать, что для некоторых методов и задач они могут очень заметно различаться, В таких случаях имеет смысл сегментирование общего вычислительного процесса на отдельные этапы и использование для каждого этапа только обязательной для него памяти. в 9.8. Сравнение методов Я% Ствветтнл АЬ ветл 4июв авввввввнв слйивв сйхвв Рвввтнвивв Рвтвлвв свисав Риыннвшы рвншкзв (МЫв) ТНав) +Рвавяив +Рванине КСМ 1%9 й(уг 190 Омгз 0 4 О О 9 0 0 0 ! 0 0 0 3 2 3 0 ! т а работы, то следует выбрать алгоритм КСМ.
Если наибольшее значение имеют время решения, или суммарное время разложения и решения, или суммарная стоимость разложения и решения, то нужно выбрать алгоритм ЯМР Наконец, если наиболее важны критерии памяти, стоимости решения пли обшей стоимости, то предпочтительным оказывается алгоритм 1%Р. Заслуживают внимания еше некоторые аспекты таблицы 9.3.1. Очевидно, что ЯМР дает несколько лучшее упорядочение, чем НР, что отражается-в меньших времени и стоимости на этапах разложения и решения и в меньших запросах к памяти.
Однако упорядочение для ХР вычисляется значительно быстрее, чем для ЯМР„что в итоге приводит к меньшим значениям для общей стоимости и оби(его времени для ХР по сравнению с ЯМР. Еше одно интересное обстоятельство, связанное с общей стоимостью г(Р и ОМР, — это существенное различие между максимальной и минимальной стоимостями. Напомним (см, раздел 9.3.1), что максимальная стоимость вычисляется в предположении, что память, испоаьэуемая на любом этапе (упорядочение, распределение памяти, разложение, решение), равна максимуму из тех запросов, которые выдвигает каждый этап в отдельности; минимальная же стоимость вычисляется исходя из того, что каждый этап использует только необходимый минимум, указанный таблицей 9.2.1.
Наши данные свидетельствуют, что да'ке для «одноразовых» задач вполне оправдано сегментирование Обшего вычислительного процесса на естественные составные чаоти и использование для каждого этапа лишь необходимой ему памяти. Изучив таблицу 9.3,1, читатель может задаться вопросом, имеют ли какой-нибудь практический смысл такие методы, как К1 гТ или ХР, которые ни по одному из рассматриваемых критериев не превосходили три других метода. Однако усреднение имеет тенденцию сглаживать различия между задачами. Чтобы показать, что для каждого метода есть место, мы приводим Таблица 9.89 Для тестового набора ~1 н различных критериев приведено число задач, для которых тот или иной нетод оказывался лучше других 296 Тл.
9. сгислеинэ~е эксгеримеиты таблицу 9.3.2. В ней для тестового набора чр1 и различных критериев указано число задач, для которых тот или иной метод оказывался лучше других, Заметим, что в этой таблице нет нулевых строк. Это свидетельствует, что даже внутри фиксированного класса задач и при фиксированном критерии (скажем, времени или памяти) выбор метода существенно зависит от задачи.
Нужно также иметь в виду, что почти для любой задачи каждый метод может при подходящей комбинации критериев считаться лучшим. В таблице 9.3.2 бросаются в глаза превосходные характеристики метода 1%!) в категориях стоимости н памяти. 9.3.3. Сравнение методов для тестовых задач набора 4~2 Для иллюстрации некоторых дополнительных соображений мы приводим в данном разделе таблицы 9.3,3 и 9.3.4. Эти таблицы получены из таблиц 9.2.7 — 9.2.11 параграфа 9.2; последние содержат экспериментальный материал для тестовых задач набора ~2.
Таблица 9.3.3 дает ту же информацию, что и таблица 9.3.1, для задачи «Градуированное Е» с з = 4 (при этом )т' 265), Такова же таблица 9.3.4, только коэффициент разбиения з равен 12, а Лг = 2233. Таблица 9.8,3 Значения различных критериев для задачи «Градуированное 7.» прн з = 4, )Р 866 (стоимость я память масштабнрованы умножением на 10 †') Юетсср Стссмссть Памята Время испапиепия сгсхся В ягсп Рееяеегеяеереиинне ОйцееРезпешеяееяееге- 1.мсяс) Тмин) +Решеяее +Решееее «ее Т«СМ О 23 О 21 О.!9 1 %Р 0.39 0.37 0.3 1 К! )Т 0 38 0.36 0.32 Х!3 056 046 037 ОМ!3 059 053 029 0.04 0.48 0.04 0.42 0.06 0.47 0.05 0.70 0.04 0.67 0.48 0.93 0.8! ОП9 0.88 0.40 0.07 0.73 0.09 0.69 0.12 0.53 0.07 0.43 0.07 Отметим прежде всего, что для )т' = 265 метод ГсСМ обнаруживает значительное преимущество в большинстве характеристик, а в остальных он вполне конкурентоспособен.
Однако для Ф = 2233 он теряет преимущество во всех разрядах, кроме общего времени исполнения. (Некоторые другие эксперименты показыва!от, что и в этой характеристике он уступает методу М!) дтя несколько большей задачи того же класса.) Один из глав. ных выводов, которые мы хотим здесь сделать, таков: даже для таких по существу одинаковых задач, как эти, порядок задачи 6 9.4. Зависимость от структуры данных 297 Таблица У.З.4 Значении различных критериев для задачи «Градуированное А» при в = 12, 87 2233 (стоимость и память масштабнрованы умноасеннем на 1О-'1 44еитеУ Опал»терть л~ лл, 0щая ОщеяяешювеиееРешеяее 0Ещеерееиевенаерешертттие1 1нии1 +Решеиее +решение иее 16.56 15.84 1.40 22.35 20.69 1.04 21.78 20.87 1.67 16.67 13.74 0.94 17.13 13.04 0.98 !54.83 !49.69 148.10 13,09 9.35 109.41 106.10 101.25 5.11 4.89 ! 43.69 140.30 137.67 10.99 6.60 140.45 124.03 ! 15 74 7 95 8.42 145.07 129.28 110.49 8.33 8.47 Г«СМ 1%0 И37 1Ч !3 (3МР может повлиять на выбор метода.
Грубо говоря, для «малых задач» нет смысла применять сложные методы. Снова обращает на себя внимание эффективность метода 1%Р в смысле памяти н стоимости. Отметим еще, что вес этапов упорядочения и распределения памяти в общей стоимости снижается с ростом йГ для всех пяти методов. Для методов КСМ, 1%Р и КЯТ эти два этапа становятся относительно маловажными в общих стоимости и времени уже при У, близких к 2000. Однако для методов ХР и Г7МР этапы упорядочения и распределения прн У = 2233 требуют все еще значительной доли общего времени.
Так как эти этапы в общем используют меньшую память, чем последующее численное решение, то различие между максимальной и минимальной стоимостями остается существенным даже для Ф = 2233, й 9.4. Зависимость от структуры данных В нескольких местах этой книги мы подчеркивали рольструктур данных (схем хранения) в вопросах, связанных с разреженными матрицами. В 9 2.3 мы провели грань между основной и накладной памятью и проиллюстрировали простым примером, что программы нельзя сравнивать между собой, исходя лишь нз потребляемой ими основной памяти, так как накладная память этих программ может быть весьма различной.
Там же было отмечено, что разные структуры данных могут вести к существенно различающимся значениям показателя «число арифметических операций в секунду» для соответствующих подпрограмм численного решения. Основная задача данного параграфа — представить некоторые экспсриментальные свидетельства в поддержку этих заключений и показать возможную величину упомянутых различий. 898 Гд 9.
Чиеленнвге эксперименты 9.4.!. Запросы к памяти В таблице 9.4.1 для каждого из пяти методов, в применении к тестовым задачам набора ~$2 указана основная и общая память. Напомним, что основная память — это то, что используется для хранения числовых значений коэффициентов Е и Ь, а накладная память — это «все остальное», и состоит она главным образом из целочисленной информации — указателей, необходимых для компактного представления А, Таблица 9.4.! Основная н общая намять для каждого метода в врнмененнн к тестовым задачам набора 468 (числа масштабнрованы умножением на !О-') Осисдиси псягяаь Числа урс3неиий эвтсягсгт 265 406 577 778 1009 1270 1561 !882 2233 КСМ 15Ч0 КОТ !ч0 ЯМ0 0.40 0.74 1.22 1 87 2.73 3.81 5.14 6.76 8,68 0.24 0.42 0.66 0.94 1.28 1.70 2.23 2.78 3.45 0.26 0.45 0.73 1.10 1.57 2.17 2.90 3.77 4.80 0.39 0.67 1.05 1.52 2.10 2.76 3.57 4.46 5,5! 0.35 0.64 0.97 1.48 2.08 2.70 3.42 4.43 5.58 27са(ся ссгтиягь Числа урсдисиий тГЕСЯГСС 265 406 577 778 1009 1270 1561 1882 2233 КСМ ! 5Ч0 К!3Т тч0 Г)М0 0.48 0.86 1.39 2.10 3.03 4.19 5.61 7,32 9.35 0.42 0.69 1.04 1.45 1.94 2.53 3.25 4.00 4.89 0.47 0.78 1.19 1.72 2.38 3.19 4.15 5.28 6.60 0.70 1.17 1.77 2.50 3.38 4.39 5.58 6.90 8.42 0.67 !.14 1.70 2.48 3.36 4.37 5.45 6.91 8.47 Данные таблицы 9.4.1 иллюстрируют следующие практически важные моменты; 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
