Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 44
Текст из файла (страница 44)
Что означают приведенные числа 291 пении с общей памятью, необходимой при решении треугольных систем. Поэтому в наших таблицах приводится только «память на численных этапах». До сих пор мы говорили лишь о первых трех категориях памяти: на этапах упорядочения, распределения и численного решения. Четвертая категория — зто «накладная памятый Мы включили ее, чтобы показать, какая часть всей памяти, используемой на этапах разложения и решения, занята информацией, не являюи(ейся значениями ненулевь1х элементов матрицы л' и право!1 части Ь (на место которой записывается х). Если ячейка памяти Таб цп 9.2.В Результаты алгоритма 1190 для тестовых задач нзбора 4)2 (число операций и память масштабированы умножением на 10-4) Задача Ваарядачерие Численные етилт Вртталанмве Вренл Панеть Време мимо тмрапав Панать Таблица 9.2.9 Результаты алгоритма КОТ для тестовых задач набора ~2 (число операций и память масатабированы умножением на 10-4) эаВпче 5)тара Втюаее Чаелемтею милам ВренеЛмюнм Пратт глвююм аргане юмма ет р юаа Ввчмтм лтю ретенаа ржтеюамт 3.24 0.81 0.47 0.21 7.11 1.49 0.78 0.33 13.70 2.46 1.19 0.46 24.03 3.78 1П2 0.63 39.32 5.49 2.38 0.81 60.94 7.67 3.19 1.02 9043 10.35 4.!5 1,25 129.48 13.59 5.28 1.51 179.99 17.44 6.60 1.79 265 О.!2 0.33 0.01 0.35 0.65 009 406 О.!8 0.52 О.! 1 0.54 1.29 0.15 577 0.27 0.74 0.17 0.77 2.39 0.22 778 0.35 0.99 0.20 1.04 3.69 0.32 1009 0.48 1.29 0.28 1.35 5.46 0.41 1270 0.60 1.63 0.35 1.70 7.76 0.54 1561 0.70 2.00 0.43 2.09 11.09 0,68 1882 0.91 2.42 0.5! 2.51 14.73 0.85 2233 1.05 2.87 0.62 2.98 19.64 !.04 265 0.07 0.33 0.04 0.34 0.57 0.12 406 0.10 0.52 0.07 0.52 !.12 0.20 577 0.16 0.74 0.09 0.74 1.94 0.29 778 0.20 0.99 0.12 1.ОО 3.15 0 43 ! 009 0.26 1.29 0.16 1.30 4.86 0.60 1270 0.33 1.63 0.20 1.63 7.!5 0.78 1561 0.40 2.00 0.25 2.01 10.14 !.04 1882 0.48 2.42 0.30 2.43 14.06 1.31 2233 0.56 2.87 0.35,.
19.20 1.67 4.38 0.69 9.25 1.18 18.1! 1.87 29.22 2.68 44.90 3.66 66.00 4.87 97.14 6.36 !31.13 7.90 !77.17 9.91 0.42 О.!8 0.69 0.27 !.04 0.38 1.45 0.51 1.94 0.66 2.53 0.83 3.25 1.02 4.00 1.22 4.89 1.45 292 Гд 9. Численные ьислерименты Таблица 9,2.10 Результаты алгорнтна МР для тестовых задач набора 4Г2 (число операций и память насштабнрованы умножением на 1О ') Звйочо Упорядоченно ,г миг, Чооненные лшопы ВреняПомятьВршгя посеять Время Чьоно аеероннй Понять Решеинежтше Рннгвнвейй т ю- ролш. еннпу Таблица 9.2.11 Результаты алгорнтиа !2М!7 для тестовых задач набора цг2 (число операций и память иасштабированы умножением на 10 ') Зодочо Ппорндоченне Чнеяеиные етнпы ВремяЛонятьбремяПонять Время Чинно операций Понять жение нешешлеже е решение ййтвя неель- еене- еяче 265 0.39 0.54 0.06 0.49 0.36 0.07 406 0.72 0.83 009 0.78 0.78 0.11 577 1.01 !.18 0.13 1.12 !.26 0.18 778 1,39 1.60 0.19 !.52 2.22 0.26 1009 1.55 2.08 0.24 !.97 3.43 0.38 1270 2,48 2.62 0.34 2.53 4.59 0.48 1561 2.56 3.23 0,39 3.09 5.90 0.60 1882 3.32 3.90 0.48 3.76 8.36 0.76 2233 3.53 4.63 0.55 4,43 12.06 0.98 ае предназначена для хранения элемента Е либо Ь, то мы относим ее к накладной памяти.
Массивы, составляюшие накладную память, подчеркнуты в таблице 9.2.1. Заметим. что разряд апамята иа численных этапах» включает в себя накладную намять. Есть еше одна причина для того, чтобы выделить накладную память в отдельную рубрику, На машинах с длинным словоы может оказаться разумной упаковка нескольких целых чисел в одном слове, Некоторые производители ЭВМ даже включают возможность работать с короткими целыми числами в свои версии Фортрана, Например, 1ВМ рог!сап допускает описание це- 265 0.20 0.28 0.06 0.49 406 033 043 0.10 077 577 0.49 0 62 0.14 1.10 778 0.68 0 84 0.20 1.51 1009 0.95 1.09 0.26 1.97 ! 270 1.22 !.38 0.32 2.49 1561 1.56 1.69 0.39 3.08 1882 1,93 2.04 0.50 3.74 2233 2,35 2.43 0.58 4.45 0.46 0.07 0.93 0.12 1.62 0.19 2.58 0.29 3.80 0.37 5.30 0.49 7.34 0.63 9.73 0.78 12.79 0.94 3.25 0.72 0.70 0.32 6,93 1.27 !.17 0.50 12.56 1,99 1.77 0.72 20.10 2.88 2.50 0.99 3!.11 4.00 3.38 !.29 44.45 5.27 4,39 1.63 62.57 6.82 5.58 2.01 83.85 8.54 6.90 2.44 111.!8 10.57 8.42 2.92 2.65 0.65 0,67 0.32 6.35 1.19 1.14 О 50 10.35 !.83 !.70 0.73 19,65 2.80 248 1.00 30.91 3.95 3.36 1.29 42.56 5.15 4.37 1.66 55.43 6.53 5.45 2.03 80.10 8,49 6.91 2.47 1 1 9.! 3 1 0.7 1 8.47 2.89 9 9.8.
Сравнение методов 29З лых чисел как 11)ТЕОЕК «2 или как 1г)ТЕОЕК в4. В первом случае для представления числа используется 16, а во втором— 32 бита. Так как большую часть накладной памяти составляет целочисленная информация, то читатель сможет оценить потенциальную экономию памяти в том случае, если доступный ему транслятор с Фортрана позволяет использование коротких целых чисел. Заметим, однако, что все наши эксперименты были выполнены на 1ВМ 303! с обыкновенной точностью и как целые числа, так и числа с плавающей точкой представлялись посредством 32 битов.
й 9.3. Сравнение методов 9.3.1. Критерии сравнения методов В этом параграфе мы не пытаемся в обшем виде разрешить вопрос, какой метод следует использовать. Типы разреженности весьма разнообразны, а наши тестовые задачи принадлежат лишь одному специальному классу. Наша цель здесь — проиллюстрировать, опираясь на данные $9.2, факторы, которые нужно учитывать при выборе метода для конкретной задачи или конкретного класса задач. Эти факторы уже обсуждались или по крайней мере упоминались в 3 2.3.
Главными критериями были: а) запросы к памяти; б) время исполнения и в) стоимость. В одних случаях наибольшее значение имеет уменьшение запросов к памяти, в других — малое время исполнения. Но чаще всего, по-видимому, интерес представляет выбор метода, для которого стоимость машинных ресурсов минимальна. Эта стоимость обычно является довольно сложной функцией от количества (5) используемой памяти, времени исполнения (Т), количества вводимой и выводимой информации и других параметров.
Для нашего класса задач и методов, которые мы рассматриваем, стоимость очень хорошо аппроксимируется функцией вида со5т (5, т) = т х р (5), где р(5) — многочлен степени е); обычно д=! (однако иногда г) = О, а в некоторых случаях, когда большие запросы к памяти нежелательны, Ы = 2). Для наших иллюстративных целей вполне достаточно взять р(5) = 5. В 3 2.3 было отмечено, что относительная важность этапов упорядочения, распределения памяти, разложения и решения зависит от контекста, связанного с разреженной матричной задачей. В некоторых ситуациях нужно решить лишь одну задачу данной структуры, поэтому любое сравнение методов, конечно, должно учитывать стоимость упорядочения и распределения памяти, В других случаях приходится решать большое число задач 294 Гл.
Р. Численные эксперименты УХ2. Сравнение методов для тестовых задач набора ~! Рассмотрим теперь таблицу 9.3.1, полученную усреднением результатов таблиц из $ 9.2, относящихся к тестовому набору ~ 1, и последующим вычислением различных стоимостей. Один Таблица УДЛ средние значения различных критериев для задач набора 4т1 (число операинй и память масжтабнроааны умножением на !О-') Пвлтвть Врвлтл исполнения йпаижапь ~Й 14.60 13.86 3.32 !ЧЧ)З 12.22 ! 1 72 2.12 )ЩТ 15 60 15.11 2.58 7Ч!9 15.63 ! 2 92 3.41 (~м!3 16.66 ! 4.52 3.36 406 049 4.94 0.45 5.59 0.65 3.19 0.36 2.77 0.34 4 39 577 6.04 4. 59 4.96 13.47 1.64 10 45 0.95 14 44 1.68 10 89 1.22 9.30 !.15 из наиболее важных выводов, которые из нее следуют,— это то, что для девяти задач данного тестового набора выбор метода сильно зависит от критерия, который желательно оптимизировать.
Например, если основой сравнения являвтся общее время с одинаковой структурой, Здесь может быть разумно игнорировать затраты на упорядочение и распределение, Наконец, нередки обстоятельства, когда нужно решать ряд систем, отличающихся только правыми частями. Тогда вполне уместно рассматривать лишь время и/или память, необходимые для решения треугольных систем при вьщисленном разложении. В некоторых таблицах, приводимых ниже, мы сообщаем «минимальную» и «максимальную» общую стоимость. Различие между ними состоит в следующем. Максимальная стоимость вычисляется в предположении, что каждый из четырех этапов . (упорядочение, распределение памяти, разложение, решение) использует одно и то же количество памяти, равное максимальному из тех запросов, которые выдвигает каждый этап в отдельносги (обычно этот максимум достигается на этапе разложения). Минимальная стоимость вычисляется исходя из того, что память для каждого этапа равна тому минимуму, который необходим именно этому этапу (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
