Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 6
Текст из файла (страница 6)
Ненулевые элементы А обозначаются символом е, а элементы заполнения в а, или Х— звездочкой в кружочке. Рнс. 2.3,2. Два различных упорядочения разреженной матрнпы А н структура ненулевых элементов соответствующнх треугольных множителей Е н и Примеры на рисунках 2,3.2 и 2.3.3 иллюстрируют некоторые важные моменты, связанные с упорядочениями и схемами хранения На поверхностный взгляд упорядочение 1, соответствующее А, кажется лучше, чем упорядочение 2, поскольку оно вообше не приводит к заполнению, в то время как при втором упорядочении заполнение состоит из двух элементов. Кроме того, и схема хранения, выбранная для з., кажется хуже той, что использована для т., поскольку первая игнорирует наличие некоторых нулей, а в Ь разреженность эксплуатируется на сто процентов, Однако из-за различий в накладной памяти комбинация упорядочения и хранения во втором случае приводит к меньшим общим запросам к памяти.
Конечно, различия здесь тривиальны, но сам вывод полностью сохраняет силу. По мере В 2.8, Некоторые крактичеекие замечания 41 того как усложняется схема хранения, во все большей мере используя нули, основная память уменьшается, а накладная обычно возрастает. Наступает момент, когда имеет смысл игнорировать некоторые нули, поскольку накладная память, необхо- Скена кранения Х олени кранения Х дсподпая поняпть 19 Накяавпая понкьть га Ющая понятие Зз Яюинпит од метка Вской 24 1такяодпая папань т т Жщая понянь 35 Рис.
2Л.З. Схемы хранения матриц ь, и Е рисунка 2,3.2. димая при их использовании, превышает уменьшение основной памяти. Подведем итоги. Главные выводы этого раздела таковы: 1. Схемы хранения разреженных матриц состоят нз двух компонент: основной памяти и накладной памяти.
2. Сравнение стратегий упорядочения должно принимать в учет используемую схему хранения; иначе оно не имеет практического смысла, 42 Гл. 2. Вводные сведения 2.8.2. Время исполнения Перейдем теперь к критерию времени исполнения. При обсуждении полезно выделить четыре этапа всего вычислитель. ного процесса: упорядочение, распределение памяти, разложение и решение. Как мы увидим в главе 9, время исполнения, необходимое для различных упорядочений, может меняться в очень широких пределах.
Но даже если упорядочение найдено, остается сделать еще многое, прежде чем можно будет начать реальные вычисления, Нужно сформировать подходящую схему хванения для Ь, а чтобы сделать это, нужно определить структуру Т.. Этот этап распределения памяти также различен по стоимости в зависимости от того, какие упорядочение и схема хранения применены. Наконец, как демонстрируют многочисленные эксперименты, представленные в главе 9, различия в схеме хранения могут повести к существенным различиям в числе арифметических операций, выполняемых в секунду, иа этапах разложения и решения треугольных систем. Обычно время исполнения разреженной матричной программы примерно пропорционально>(или должно быть пропорционально) количеству производимой арифметики, Однако различия в упорядочении и структуре данных могут привести к большим различиям в константе пропорциональности.
Таким образом, число арифметических операций может быть не очень надежной основой сравнения различных методов решения; по крайней мере им следует пользоваться осмотрительно. Не константу пропорциональности влияет не только примененная структура данных, ио также архитектура машины, транслятор и операционная система. В дополнение к вариации относительных стоимостей исполнения каждого из рассмотренных выше этапов сравнение различных стратегий часто зависит от конкретных обстоятельств решаемой задачи. Если данную матричную задачу нужно решать лишь однажды, то сравнение стратегий, конечно, должно включать время, необходимое для определения упорядочения и формирования схемы хранения.
Напротив, если предстоит решать много различных задач с одинаковой структурой, то при сравнении методов может оказаться оправданным игнорирование стоимости этого начального этапа, поскольку львиную долю машинного времени забирают разложение и решение треугольных систем. При других обстоятельствах нужно решать ряд систем, различающихся лишь правыми частями. В такой ситуации, может быть, разумно сравнивать различные стратегии на основании времени, которого они гребуют при решении треугольных систем. р 28 Некоторые прахтинеские замечания 48 Подведем итоги. Главные выводы этого раздела таковы: 1.
Весь процесс решения системы Ах = Ь состоит из четырех основных этапов. Доля общего машинного времени, приходящаяся на каждый из них, в общем случае сугцественно меняется в зависимости от упорядочения и схемы хранения. 2. В соответствии с обстоятельствами конкретной задачи время исполнения некоторых из упомянутых этапов может быть практически несущественным при сравнении различных методов.
Упражнения 2.3.1. Предположим, что вы имеете выбор из двух методов решении разреженной системы уравнений Ах = Ь вЂ” метода 1 и метода 2, критерием выбора метода является время исполнения утаим упорядочения н распределения памяти для метода 1 требуют совместно 20 секунд; соответствующее время для метода 2 — всего лишь 2 секунды. Время разложения в методе 1 равно б секундам, а решения треугольной системы †,5 секунды; для метода 2 соответствующие показатели равны 10 секундам и 1,5 секунды а) Какой метод вы выбрали бы, если систему нужно решить лишь однаждыз б) Какой метод вы выбрали бы, если нужно решить двенадцать систем Ах = Ь с одинаковой структурой разреженности, но разными числовыми значениями А и Ьз в) Как бы вы отвесили на вопрос б), если бы у систем различались лишь числовые значении правых частей Ь? 2.3.2.
Предположим, что для данного класса разреженных положительно определенных матричных задач имеется выбор из двух упорядочений, условно называемых «черепаха» и «заяц» Ваш друг Питер показал, что упорядочение «черепахой» дает треугольные множители, каждый из которых имеет ненулевых элементов Ч!(У)яэУ + У вЂ” 'тУ;здесь У вЂ” порядок задачи. Он показал э/2 также, что соответствующая функция для упорядочения «зайцем» есть (У) м 7 75У 1ояз (~/У+ 1) — 24У + 11 5 Ч/У!сиз (ЧУЙ + 1) + 11 Ч/У + +ОЛ5 1оиз(Ч/У+ 1).Еще один ваш приятель Гарольд написал программы решения линейных систем, использующие схемы хранения, подогнанные к соответствующему упорядочению. Гарольд обнаружил, что при реализации упорядочения «зайцем» ему требуются по одному целому числу (индексу) для каждого ненулевого элемента Ь и, кроче того, еще три массива указателей; каждый массив — длины У, При реализации упорядочения «черепахой» накладная память состоит лишь из У указателей.
а) Предположим, что ваш выбор метода основан исключительно на об. щем объеме памяти, необходимом для хранения «» и что целые числа, квк и числа с плавающей точкой, хранятся полным машинным словом. 11ля каких значений У вы использовали бы упорядочение «зайцем»» б) Что бы вы ответили на вопрос а), если бы Гарольд переделал свои программы так, чтобы целые числа были упакованы в машинном слове по три? 8.
Некоторые сведения из теории графов и ее применение к исследованию разреженных симметричных матриц $3.0. Введение В этой главе будут введены некоторые основные понятия теории графов и установлено их соответствие с матричными понятиями. Хотя лишь немногие результаты теории графов нашли прямое приложение в анализе разреженных матричных вычислений, ее обозначения и понятия удобны и полезны в описании алгоритмов, а также в опознании и характеризации структуры матрицы. Однако при использовании теории графов в такого рода анализе легко перейти разумную грань; результат часто будет тот, что терминологическая элегантность затемняет смысл некоторых по существу простых идей, Поэтому, принося, возможно, в жертву единообразие изложения, мы всюду, где это уместно и на пользу делу, даем определения и результаты в терминах как теории графов, так и теории матриц.
По тем же причинам мы предпочитаем вводить ббльшую часть терминов теории графов там, где в этом возникает потребность, вместо того чтобы ввести их все в этой главе, а затем отсылать к ней в последующем тексте. й 3.1. Основная терминология и некоторые определения Для наших целей граф 6 = (Х, Е) можно представлять себе состоящим из конечного множества узлов, или вершин, вместе с множеством Е ребер, которые суть неупорядоченные пары вершин.
Упорядочение (помечивание) и графа 6 = (Х, Е) есть попросту отображение множества (1, 2, ..., Ж) на Х; здесь й1 — число узлов 6. Если специально не оговорено противоположное, граф считается неупорядоченным. Граф 6, помеченный посредством и, будет обозначаться через 6' = (Х", Е), Вводя графы, мы намереваемся облегчить изучение разреженных матриц; поэтому сейчас мы установим связи между графами и матрицами, Пусть А — симметричная матрица порядка М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
