Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 46
Текст из файла (страница 46)
Для некоторых методов накладная компонента памяти очень значительна, даже для больших задач, где ее относительная важность несколько уменьшается, Так, для метода (;!М(3 отношение (накладная память)/(общая память) изменяется примерно от 0.48 до 0.34 при росте й! от 268 до 2233. Следовательно, хотя это отношение убывает, оно еще весьма внушительно даже для очень больших задач. Для сравнения укажем, что в методе КСМ, использующем очень простую структуру данных, отношение (накладная память)((общая память) изменяется для тех же задач от примерно 0.17 до 0.07.
4 Улх Зависимость от структуры данных 2ЗЭ 2. Другой момент (по существу являющийся следствием пункта 1) — это то, что основная память является очень ненадежным показателем общих запросов программы к памяти. Например, если бы мы сравнивали методы КСМ и ЯМР, исходя только из объема основной памяти, то при всех И следовало бы выбрать ЯМР. Между тем реально потребляемая память у метода КСМ меньше вплоть до Л' ж 15001 Это сравнение демонстрирует также потенциал, заключенный в возможности хранить целые числа более компактно, чем числа с плавающей точкой. Во многих случаях число двоичных разрядов в представлении числа с плавающей точкой по крайней мере вдвое превосходит то, что необходимо для представления целых чисел достаточной величины.
Если возможно использовать это обстоятельство, то роль накладной компоненты, очевидно, станет менее заметной. Так, если бы для целых чисел требовалось ровно в два раза меньше разрядов, чем для чисел с плавающей точкой, то память, потребляемая методами КСМ и ЯМР, выравнивалась бы уже при М ж 600, а не при М ж 1500, как указано выше. 3. Вообще говоря, информация из таблицы 9,4.! показывает, что, хотя сложные алгоритмы упорядочения существенно сокращают основную память по сравнению со своими более простыми конкурентами, чисгьсй выигрыш в общей памяти не так значителен как можно бы предположить, исходя нз различия в основной памяти. Причина состоит в использовании более сложных схем хранения.
Например, показатель основной памяти для 1%Р при М ) 778 составлиет менее 50с7с от аналогичного показателЯ длн КСМ, и это преимущество увеличивается с ростом М. Если же рассматривать общую память, то, хотя и здесь превосходство 1%Р над КСМ растет с увеличением Лс, момент, когда память для 1ЮР вдвое меньше памяти для КСМ, не достигнут и при Ф = 2233. 9.4.2. Время исполнения В таблице 9.4.2 представлены значения показателя «число операций в секунду» для подпрограмм разложения и решения каждого нз пяти методов в применении к тестовым задачам набора 4~2.
Эта информация подсказывает такие выводы. !. Вообще говоря, эффективность (т. е. число операций в секунду) подпрограмм увеличивается с ростом Л'. Этого и следовало ожидать, так как циклы, будучи инициированы, выполняются все большее число раз. Тем самым при возрастании й! относительно уменьшаются издержки, связанные с инициированием циклов. Отметим в этой связи, что повышение эффективности на отрезке от Л' = — 265 до Л' = 2233 существенно разное для рассмат.
риваемых нами шести подпрограмм и пяти упорядочений 800 Гл. 9. Численные эксперименты Таблица 9.4.8 Показатель «число операций в секунду» дли каждого метода в применении к тестовым задачам набора чга (число операций масгитабироваио умножением на !О-') Рооложенив число уРоунений таувотОЗГ 265 406 577 778 !009 1270 1561 1882 2233 9.0! 9.37 9.91 10.58 10.92 1!.24 1! 59 11.76 12.06 6.78 7.19 7.57 7.93 8.22 8.51 8.76 8.90 9.02 5.68 6.33 7.07 7.63 8.10 8.53 8.92 9.2! 9.37 7.07 7.42 7.75 7 78 8.20 8.38 8.52 8 62 8 69 7.30 8.10 8.19 8.87 9.01 9.27 9.39 9 59 9.88 КСМ 1%'!7 Кт)Т )9 13 С)М!3 Решение число уроонений Меотод 265 406 577 778 !009 1270 156! 1882 2233 КСМ 3Ц)Т )ь1!3 ОМ!3 !02! !069 1087 1!.21 11.50 11.81 1!.97 !1 87 !2.08 7.96 8.05 8.50 8.27 9.00 9.01 9.3! 9.30 9.50 6.79 7.45 8.38 8.78 9.16 9.83 9.95 !0.35 10 47 10.25 10.28 10.49 9.8! !0.71 10.83 !0.89 11.00 ! 1.20 9.77 10.52 9.98 10.65 10.50 10.65 10.89 11.12 10.89 (Вспомните, что методы !'тт'Р и ЩТ используют одни и те же подпрограммы численного решения, и это же верно для методов )т)Р и ЯМР.) Например, для подпрограммы ЙБВьтг метода !!Р эффективность повышается незначительно — от 9.44 Х !04 до 10.15 Х!04 на полном отрезке изменения )т'.
В то же время эффективность подпрограммы ТВЯьЪ' метода ЩТ возрастает с 6.07 Х 10' до 9.50 Х 104. Эти различия, по-видимому, объясняются разным количеством вспомогательных подпрограмм. Например, ТВИСТ использует подпрограммы ЕЕЯьЧ, Е!)Я!Л! и ЕВЕСТ (которая в свою очередь обращается к ЕЕВИЧ), а у СгВЕСТ вспомогательных подпрограмм вообще нет. Вызовы подпрограмм при малых порядках задач существенно изменяют время исполнения. Различия в эффективности подпрограмм численного решения показывают, насколько нереалистично делать выводы практического характера только на основании числа операпий.
Так, если бы мы сравнивали методы ЙСМ и ЯМР по числу операций при разложении, то для задач тестового набора $~ 2 мы выбрали бы во всех случаях !!МР. Однако по времени работы 1;!МР уступает ЙСМ до тех пор, пока не будет !т' ж 1600 2. Мы уже отметили, что эффективность различна для разных подпрограмм и разных й!. Интересно и то, что при фиксиро- 0 9.4. Зависимость ат структуры асиных 301 ванной задаче и подпрограмме эффективность зависит от примененного упорядочения. В качестве примера рассмотрим показатели разложения для методов 1%0 и ЩТ при У=2233.
(Вспомните, что оба метода используют подпрограмму ТЬГСТ). Различие в эффективности методов можно объяснить таким образом. В отличие от подпрограмм ЕЯГСТ и ЙЯРСТ, где болыпая часть арифметической работы выделена в один цикл, вычисления, проводимые ТРЕСТ, распределены между тремя вспомогательными подпрограммами (с различной эффективностью) и основным вычислительным циклом внутри ее самой. Поэтому для одного упорядочения ТРЕСТ может оказаться эффективчей, чем для другого, просто по той причине, что ббльшая доля вычислений выполняется самым эффективным из четырех вычислителей: трех вспомогательных подпрограмм и цикла из ТРЕСТ.
Дополнительное усложнение в это сравнительное исследование показателей разложения для 1%0 и ЙЯТ вносит то обстоятельство, что доля вычислений, выполняемых различными вычислительными циклами подпрограммы ТЯГСТ, по-видимому, меняется вместе с Ж, и зависимость от т1~ различна для упорядочений 1%0 и КЯТ. Для малых задач ТРЕСТ эффективнее работает при упорядочении 1%0, но с ростом У ситуация обращается, причем показатели обоих методов сравниваются при У ж 1700, Мы должны предостеречь читателя от того, чтобы делать слишком глубокие заключения иа основании частного примера. На другой машине с другим транслятором и набором команд относительные эффективности вспомогательных подпрограмм и вычислительного цикла в ТРЕСТ могут быть совершенно иными. Однако этот пример все же показывает, что эффективность является функцией ие только используемой структуры данных, но и может зависеть довольно неочевидным образом от упорядочения и порядка задачи.
Приложение А, Некоторые указания к использованию подпрограмм А.1. Примеры скелетных ведущих программ В главах 4 — 8 были описаны различные методы решения разреженных линейных систем. Они различаются схемами хранения, с С СФОРМИРОВАТЬ ДЛЯ СИОТЕМЫ АХ ~ В с мАссиВы ХАОТ и дохнет. С САЬЬ 6ЕМЯСМ(М,ХАО1,АО)МСУ,РЕЯМ,МАЗК,ХЬЗ) САЬЬ 1МЧЯЗЕ(М,РЕЯМ.1МЧР) САЬЬ РМЕМЧ(М,ХАО),АО)МСУ,РЕЯМ, 1МЧР,ХЕНЧ,ЕМЧЗЕЕ,ВАГЕ)Н) ВВЕСТИ ЧИСЛОВЫЕ ЗНАЧЕНИЯ и О1А61 ЕМЧ И ИНВ. САЬЬ ВЕРСТ(М,ХЕНЧ,ЕМЧ,О1А6,1ЕЯЯ) СА)ЗЬ Е( ЗЬЧ(М, ХЕНЧ, ЕМЧ,О1АО,ВНЗ, 1ЕЯЯ) САЬЬ ЕЗЗЗЬЧ(М,ХЕ)(Ч,ЕМЧ.О1АО,ЯИЗ,)ЕЯЯ) СЕЙЧАС В ЯНВ - ПЕРЕХПОРЯДОЧЕННОЕ РЕШЕНИЕ.
ВОССТАНОВИТЬ ИСХОДНЫЙ ПОРЯДОК НЕИЗВЕСТНЫХ. САЬЬ РЕЯМЯЧ(М,ЯНЗ,РЕЯМ) Рис. А.1.1. Скелетиая Ведущая программа для профильиого метода. стратегиями упорядочения, структурами данных и/или численными подпрограммами. Однако общая процедура при исцользовании зтих методов одна и та же. В ней можно выделить четыре фазы: Шаг 1. Упорядочение.
Шаг г. Формирование структуры данных. Р А.!. ))римеры скелетных ведущих программ 303 Шаг 3. Разложение Шаг 4. Решение треугольных систем. В главы 4 — 8 включены подпрограммы, реализующие эти шаги для каждого метода. На рис. А.!.1 — А.!.3 приведены тексты трех скелетных программ; они обслуживают соответст- с С СФОРМИРОВАТЬ ДЛЯ СИСТЕМЫ АХ м В С МАССИВЫ ХАОа И АОБИСУ. с САЬЬ СЕМЯ()Т(М, ХАОЮ, АО1МСУ, МВ1 КБ, ХВЬК, РЕЯМ. ХЬБ, ЬБ, МООЬЧЬ) сАЕЕ Взнорь (хаог, Аогмсу, Рекм, мвькэ, хВ1.к, Вмом, мАБк, Боно, х1.5 ) САЬЬ 1МЧЯБЕ(М РЕКИ 1МЧР) САгн РМТАО1(ХАОЮ,АОЛЕСУ,РЕЯМ, 1МЧР,МВЬКБ,ХВЬК,РАТНЕК,МАЕК) СА(Ь РМТК))Ч(ХАОЗ,АВ1МСУ,РЕЯМ, 1МЧР,МВЬКБ,ХВ)К,ХЕНЧ.ЕВ)У57Е) сА(ь Рвюрм7(хао),Аогмсу,Реям,1НУР,мвькз,хвьк,хмомх, МЕБПВ5,НОРМЕ) ВВЕСТИ ЧИСЛОВЫЕ ЗНАЧЕНИЯ В МОНЕ, ОЕАОт ЕМЧ И ИНВ. САЬЬ ТЕКСТ (МВ1 КБ .
ХВ1 К, РАТНЕК, О1АО, ХЕ)(У, ЕМУ, ХМОМ7, МОМ7, М75ПВ5,ТЕМРУ,Р1К5Т,1ЕКЯ) СА(Ь ТББЬЧ(МВ1КБ,ХВ1.К,В1АО,ХЕНЧ,ЕМЧ,ХВ)ОВП,МОНЕ,МЕБПВБ, КНБ,ТЕМРЧ) С С С С С С Сейм~о В ЯИВ НАХОДИТСЯ ПЕРЕУПОРЯДОЧЕИИОЕ ~ЕШЕНИЕ. ВОССТАНОВИТЬ ИСХОДНЫИ ПОРЯДОК НЕИЗВЕСТНЫХ. САЬЬ РЕЯМЯЧ(М,КНБ.РЕЯМ) Рнс. АА.2. Скелетная ведущая программа для метода древовидного раабне- ння. венно профильный метод (глава 4), метод древовидного разбиения (глава 6) и метод вложенных сечений (глава 8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
