Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 11
Текст из файла (страница 11)
РО1ВЙЕ использует стратегию ИМЯ, а У12М вЂ” 16МЯ. Суммарный эффект от применения 1К (Т = = 0.01) и более удачной стратегии выбора виден из табл.4,4, где указано время счета для тех же матриц, что и в табл.4,3. Матрицы Е (п, с) — это симметричные и положительно определенные ленточные матрицы. Мы сравнивали У12М с про~раммой, специально составленной для та~их Матриц, но не использующей разреженность; а именно, с программой 1..'04АСЕ из библиотеки МАб 11081. Следует отметить, что ГО4АСЕ наиболее эффективна для ленточных матриц с узкой лентой.
Тем не менее она до- Таблица 4,4. В рема счета (в секундах; машина 1ЛЧ1ЧАС 1100/82) для матриц класса Е (и, 44). 111 используется при Т = 0.01 Р01ВЯŠ— ОБ вОльнО хорОЕО работает дли МЯтриц класса Е (и, '~~~ Все же при больших значениих и Она уступает разреженной матричной программе '1'12М, написанной дли матриц Об1цего вида и не использующей ни симметрию, ни положительную Опре" ДЕЛЕННОСТЬ.
Таблица 4.5. Время счета (в секундах; машина ВЫПАС 1100/82) для матриц класса Е (и, с). 1К используется при Т 0.01. Р04АСЯ Мы провели несколько серий экспериментов, чтобы выявить зависимость времени счета от и и характера разреженности, а также чтобы сравнить программы библиотеки ХАЙ с обоими режимами (М- и И-) программы У12М. В табл.4.6 показаны результаты 1(ли тестовых матриц класса 0(п,с), 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 2304 22.47 28.46 53,67 58.54 57.35 115.58 152.31 7.40 8,29 12.62 13,93 8.15 8.84 10.02 10.'57 11.23 11.86 12.65 13.33 14.23 14.76 21.45 с = 4(40) 204, и = 650(50) 1000, Эти числа являются сум.
мами времени счета (в секундах) для шести значений с„ эксперименты проводились в КЕСК13 на машине БХИАС 1100/82. Таблица 4.6. Время счета (в секундах; машнна 11%ЧАС 1100/82) для матриц класса О (п, с); с = 4(40)204 гО1вйе В табл, 4.7 приведены аналогичные числа для матриц класса Е(п, с). Таблица 4.7. Время счета (в секундах; машина Б1ч1УАС 1100/82) для матриц класса Е (п, с) н с ° 4(40) 204 Б табл. 4.8 мы показываем зависимость времени счета от с для и = 800. Похоже, что для всех трех программ малые и большие значения с являются кболее легкимиэ; правда„ для т*12М вЂ” 1й время слабо зависит от с.
Промежуточные значения с особенно трудны для ГО1ВКЕ, хотя и У12М вЂ” ВЯ испытывает здесь некоторое напряжение; именно в этом причина больших Различий в эффективности трех программ, ко- 52.45 1О9.38 131.07 143.69 227.23 253,87 29.59 33.81 34.99 36.22 26.63 41.41 42.13 25.53 29.09 31.82 42.68 46.31 52.04 58.62 13Л6 13.ОО 13.77 14,55 15.'16 16,ОО 16.28 17.85 Таблица 43. Время счета (в секундах; машина БМ1УАС 1100/82) длн матриц 0(800, с) Е (800, с) У! 2М вЂ” ОЗ у12м — оя т12м — эя РО1ВЯЕ Т= 10-' 2.37 2.09 В табл. 4.9 программы Р01ВКЕ и 712М вЂ” 1К сравниваются на матрицах класса Г2 (500, 500, 20„г, 100). Меняя г, Г = 5(5) 40„мь! изменяем разреженность атрицы, усло ня Я задачу.
Во всех случаях У12М вЂ” 1Я в 3 — 5 раз быстрее, чем программа РО1ВКЕ, Таблн!1а 4.9. Время счета (в секундах", машина УИ1ЧАС 1100/82) для матриц класса Р2(500, БОО, 20, г, 100) -! 712М вЂ” 1К т=10-' РО1ВЙЕ 4.5. Выбор барьера и коэффициента устойчивости Мы видели, что применение итерационного уточнения вместе с большим значением барьера Т дает очень эффективный метод вычислений. Было проведено несколько экспериментов с целью выяснить, какой величины следует выбирать Т. В табл.
4.10 и 4,11 сопоставлен 1;)Я-вариант (Т = 10-") про- торые видны из табл. 4.6 и 4.7, Но.во всех случаях У12М вЂ” 05 :лучше, чем РО1ВКЕ; в свою очередь У12М вЂ” 1К еще лучше„ за исключением (подтверждающим общее правило) матрицы Е (800,4). граммы У12М с 1К-вариантом при трех различных значениях Т. Из табл. 4.10, 4.11 видно, что большое значение барьера сокра1цает вре~я счета; раньше мы отмет~~и, что и требования к памяти при этом меньше и что итерационное уточнение дает к тому же лучшу1о точность„чем прямое решение. Точное значение Т не очень критично; конечно, Т нужно выбирать достаточно малым, чтобы итерационное уточнение сходилось. Таблица 4.И.
Суммарное время счета (в секундах; машина (ЛЧ1УАС 1100/82; программа У!2М) для матриц класса О (и, с)1 с 4(40) 204 4 ~ 1,, з т=1о 9.09 9.48 11.16 Общее время Таблица АП. Суммарное время счета (в секундах; машина 13ИИАС 1100/82; программа т'12М) длв матриц класса Е (а, с); с =4(40) 204 эз т ш-' т=-1О-' Общее время Эмпирическ~е пр~вил~ для не слишком плохо обусловленных матриц, у которых ненулевые элементы имеют один и тот же порядок величины а, состоит в том, чтобы выбирать значение Т в интервале 110 †'а„ 10-'а). Чтобы обеспечить сходи- 8.83 16.52 19.00 21.11 30.13 24„11 38,47 5.87 8,31 9.07 11.56 11,93 14,52 Ттблячо 4.12. Сравнение барьер~и~ стратегий на яримере химической задачи.
В графе „Число итераций" указано среднее число итераций," в графе „Время" — среднее время при решении дзух систем; а =255, МХ =7715, СОПИТ вЂ” наибольшее для двух систем значение Нач аль- ное Т Коиеч. нос т Число итераций Алгоритм 10-14 о4547 10-" 10-' ЗЛ 15.77 5.54 13,00 Мы вводили большое Т„чтобы ограничить размер заполнения. Той же цели мы пытались достигнуть в гл. 3, используя бОльшОЙ коэффициент и и рискуя устоЙчивОстью процесса.
Интересно поэтому исследовать комбинированный эффект и и Т. Был проВеден эксперимент с мзтрицей класса 1"'2; его результаты суммированы в табл. 4.13. Из табл. 4.13 видно, что при большом Т память и время счета уменьшаются независимо от и, хотя число итераций может Возрасти, Эффект от изменения ц Выражен гораздо слабее; однако имеется указание на то, что при большом ц не следует выбирать слишком большое Т. Этот довольно неОжиданный результат, возможно, сВяззн с тем, что при бОль шом ц глаВными могут Оказаться малые элементы; поэтому мость в случае плохо обусловленных матриц, может потребоваться меньшее значение Т (см.
(2.1)). Для задач категории 4 (см. ~ 2,7), где нужно решать много систем одинаковой структуры, можно применить специальную стратегию,.-В этом случае может оказаться выгодно установ~т~ б~~ь~о~ н~~~л~~~е значен~~ для Т и по~ы~а~ься решать системы с таким Т, Если какую-то систему не удается решить при заданном допуске на погрешность (КЕ1.ЕБТ ~ е), то Т умножается каждый раз на один и тот же множитель, Т:= сТ (с:. 1), после чего решение систем возобновляется. При такой стратегии мы соглашаемся на некоторую дополнительную работу В начале процесса с тем, чтобы НЗЙТИ Оптимальное Т и сократить общую работу; см. 170, 87, 90, 101~.
Эта стратегия использовалась для линейных систем, возника1ощих при применении двухшаговых, модифицированных диагонально неявных методов Рунге — Кутта к большим системам обыкновенных дифференциальных уравнений химического происхождения 170~. В табл. 4.12 показаны результаты ее сравнения с У12М вЂ” ОЯ и У12М вЂ” 1К. Таблица 4.Ж Влияние а и т на аффективность программы '1'12М вЂ” 1Й для матрицы А Г21125„125, 15, 6, 4); машина СПС Суьег 173 сомнит сопит Время 3376 1790 1475 1120 860 5.68 2.44 2.25 1.79 1.27 3044 2218 1947 1333 946 7 11 11 15 21 вполне вероятно появление новых злементов бо~~шой величины.
Таким образом, хотя размер заполнения уменьшается '1, мы сохраняем большую его часть вследствие большого значения Т. Табл. 4,13 отражает результаты только для одной мат- рицы, и из нее самой по себе не следует делать какие-либо выводы об1цего характера, Однако иескОлько зкспериментов с тестовыми матрицами класса Й(п, с) указывают в том же направлении„см. 19О~.
'~ Поскольку прн большом и выбор главного элемента фактически подчинен только требованию сохранения разреженности. — Лпцм, церер. Мы видели несколько примеров, где применение итерационного уточнения с большим. барьером оказывалось эффективней прямого Решения. Разумеется, так будет не всегда, и стоит упомянуть о трех типичных исключениях. (1) Если матрица А обусловлена очень плохо, точнее : если м(А)е ~ 1, то итерационное уточнение может не сходиться.
Это условие — машинно-зависимое; поэтому можно было бы перейти на другую машину (для СВС СуЬег 173 .:в ж 1Π— 'а, и этого для многих случаев достаточно) или же вычислять прямое решение с двойной точностью. . (2) Если матрица А очень велика, а ресурсы памяти ограничены, то места для хранения 1 (см. ~ 2.6) и дополнитель:: ной копии А может не быть, С другой стороны, 1К при большом Т обычно дает значительно меньшее заполнение, и очень часто 1К окупает себя. (3) Когда заполнение мало уже при прямом решении, то ' 1К не приводит к большому выигрышу, Задачи такого сорта : будем называть «дешевыми». Типичным примером очень де-: шевой задачи является матрица с плотной лентой, например :::::. Е(п, 2), где никакого заполнения не происходит.
Используя модель из ~ 4.3, можно оценить размер допол- нительной (относительно БЯ) памяти, необходимой для 1К: Яа — Бя 2ХК + 4п (6.1) 82 ЗУХРА + 13п Это означает, что объем дополнительной памяти для 1Я никогда не превосходит 67% памяти„нужной для В8; эта верха'>д при =1 и б ЯХ, От да следует, что если в ходе ВЯ заполнения не возникает, то прямое решение более эффективно. Это иллюстрируется таблицей 4.14, где показаны результаты для пяти тестовых матриц харуэллской коллекции ~231.
Эти матрицы не порождают заполнения и близки к наихудшим возможным для 1К случаям: для некоторых из них увеличение памяти для 1К (вычисляемое по формуле (6.1) достигает 53%, а увеличение времени — 29 %, Б более реалистической «дешевой» задаче следовало бы ожидать„что ~ '.- 2, а тогда дополнительная память для 1К будет~1 меньше, и еще меньше — увеличение времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
