Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 26
Текст из файла (страница 26)
Стоимость вычисления !тттй — 10 операций, а общая стоимость асимметричной схемы — 86 операций. С другой стороны, стоимость вычисления ИУтИУ равна 10 к', 10 = 100 операций. В дополнение к потенциальной возможности сократить число арифметических операций асимметричная схема может позволить значительно уменьшить запросы к памяти по сравнению го стандартной схемой. Главный момент состоит в том, что при вычислении к можно обойтись без ИУ, если только сохранена К Всякий раз, когда нужно вычислить произведение Изота нли !йг, т -т мы можем вычислять и' (.(в г) или Ьв (!тг), т. е. решить тре- б 6.1.
Решение блонньзх систем уравнений 169 угольную систему и умножить на разреженную матрицу. Если У значительно более разрежена, чем Ф', как часто и бывает, то мы сэкономим одновременно и память, и арифметическую работу. С точки зрения вычисления разложения важно отметить следующее: если мы не планируем сохранить Ж, то вычисление С в асимметричной схеме (6.1,4) позволяет вообще избавиться от хранения )о', Произведение УФ можно вычислять столбец Стоггбео, оа оогоггоггогг Рис. 6.1.3.
Лиаграмма, показывающая характер доступа к столбцам 1О или Р прн вычислении нижнего треугольника матрицы У"и 'У столбец за столбцом либо строка за строкой за столбцом, стирая вычисленный столбец, как только он был использован для модификации С. Требуется лишь один рабочий вектор длины г. Напротив, если вычислять УгВ-'У как )УгФ, то, по-видимому, нельзя избежать хранения иа каком-то этапе всей матрицы тр, хотя бы она и не была нужна в дальнейшем.
Асимметричный вариант алгоритма разложения можно описать следующим образом. т Шаг А Разложить матрицу В в произведение Т,аЬн. Шаг 2. Для каждого столбца о = У., матрицы У: 2.1) Решить систему е.вти = и. г- 2.2) Решить систему Т.пто = то. 2.3) Положить Сел = ф— Утто. т Шаг 3. Разложить матрицу С в произведение д,оСс. Разумеется, при формировании С„на шаге 2.3 используется симметрия С.
Как1зм бы из указанных двух способов мы ни вычисляли произведение Ут — '1г, все еще остается некоторая !70 Гл б Методее фактор-деревьев свобода в выборе порядка вычисления элементов. Считая, что определяется нижний треугольник, мы можем вычислять элементы строка за строкой либо столбец за столбцом (см. рис, б.1.3); при этом нужен различный порядок доступа к столбцам %' или Г б.1.2. Решение треугольной системы блочного порядка два Если вычислен множитель Холесского блочной матрицы, то решение линейной системы выполняется очевидным образом. Прямой ход Решить систему Ову~ = Ьь Вычислить Ье = Ьв — )у~уь Решить систему Есув = Ьь Обратный ход т Решить систему е.сх, = у, Вычислить у~ = У1 — )ухта т Решить систему Евх~ = у~ Этот метод решения мы будем именовать стандартной схе- мой.
Однако, как было отмечено в разделе 6.1.1, может ока- заться выгодным не строить матрицу $у, сохраняя у; при этом всякий раз, когда нужно оперировать с )У, используется опре- деление %'=Ев У. Идя таким путем, мы получим следуюший алгоритм, называемый в дальнейшем неявной схемой. В нашем описании 71 — это рабочий вектор. Прямой ход Решить систему е ву~ = Ьь т Решить систему Евт~ =У| Вычислить Ье — — Ье — УЧь Решить систему ~сух = Ье Обратный ход т Решить систему х,сх, =у,.
Решить систему 1.вт1 — — Ухь Вычислить у| = у| — ть т Решить систему Евх~ = Уп В неявной схеме нужны лишь подматрицы (в.в, вс, у), а в стандартной — подматрицы (е.в, Ес, Щ. Согласно следст. вию 2.2.5, Ч1У) (Ч()У), и для разреженных матриц У может иметь значительно меньшее число ненулевых элементов, чем )У. Для матрицы на й 6.1. Решение блочных систем уравнений 17! рис. 6.1.2 в то время как Ч(У) 4, Ч(Ж) =40.
Таким образом, с точки зрения величины основной памяти применение неявной схемы может оказаться очень привлекательным. Что касается числа операций, то относительные достоинства двух схем зависят от разреженности матриц Еа, У н Иг. Так как стоимость вычисления Иуг равна Ч(%'), а стоимость вычисления Ее'(уг) равна Ч(У)+ Ч(де), то получаем следующий результат (разреженность вектора г здесь не используется). Лемма 6.1.2.
Стоимость вычислений по неявной схеме не превосходит стоимости стандартной схемы в том и только том случае, когда Ч(У) + Ч(х.в)(Ч()к). В следующем параграфе мы распространим эти идеи на линейные системы блочного порядка р, где р ) 2. Для разреженных блочных систем типично, что асимметричный вариант блочного разложения и неявная схема решения предпочтительнее с точки зрения вычислительной работы и памяти. Поэтому в остальной части главы мы рассматриваем толькоэтотвариант.
Упражнения 6.1.1. Пусть А — симметричная положительно определенная блочная мат- рица вида А ( т — ), где обе матрицы В и С вЂ” трехдиагональные порядка ш, а У вЂ” диагональная. В своих ответах иа приводимые ниже вопросы считайте, что ги велико, и пренебрегайте младшимн членами при подсчете числа операций. а) Представим треугольный множитель матрицы А в виде '=(.,) Опишите структуру ненулевых злементав Св, Ьг и )У.
б) Определи~с число операций (умножений и деленна), необходимых для вычисления Ъ посредством описанных в разделе 6.1.1 алгоритмов симметричного и асимметричного разложения. в) Сравните стоимость явной и неявной схем из раздела 6.!.2 для втой задачи. Можно считать заполненной правую часть Ь системы Ал = Ь. г) Ответьте на вопросы а), б) и в) для случая, когда В н С заполнены, и У вЂ” диагональная д) Ответьте иа вопросы в), б) н а) для случая, когда В и С заполнены, а У вЂ” нулевая, за исключением заполненной первой строки. 172 Гл 6 Методы фактор-деревьев 6.!.2. Асимметричную схему разложения можно рассматривать как метод вычисления следующей факторизации матрицы А где йт В '!Г и предполагается, что хранятся множители матриц В и С, а не сами зти матрицы Опишите для такой факторизации явную н неявную процедуры, аналогичные тем, что приведены в разделе 612 Будет ли получено какое-нибудь сокращение числа операций по сравнению с разделом 6 1 2з Что мох но сказать о запросах к памяти, если в каждом случае хранить внедиагональные блоки сомножителей? 6.!.3, Доказать теорему 6.1.1, 2 6.2.
Фактор-графы, деревья и древовидные разбиения Читателю, по-видимому, ясно, что успех неявной схемы, рассмотренной в разделе 6.1.2, был связан с очень простой формой внедиагонального блока ИУ. В случае произвольной блочной матрицы блочного порядка р внедиагональные блоки множителя не будут иметь столь простой формы; хранить вместо них исходные блоки А и затем по сушеству перевычислять их при необходимости было бы слишком дорого с точки зрения вычислительной работы. Это сейчас же приводит к вопросу; какие характеристики должна иметь блочная матрица, чтобы внедиагональные блоки ее множителя имели нужную простую форму? В данном параграфе мы ответим иа этот вопрос и заложим основы алгоритма, определяюшего подходяшие разбиения. б.2.1.
Блочные матрицы и фактор-графы й1ы уже установили связь между симметричными матрицами и графами, В этом параграфе приводятся дополнительные сведения из теории графов, которые позволят нам оперировать с блочными матрицами. Пусть А разбита на р' подматриц Аго 1 (1,1«= р. Будем рассматривать каждый блок как единственный элемент, равный нулю, если блок нулевой, и отличный от нуля в противоположном случае. Тогда мы можем связать с матрицей А блочного порядка р граф с р узлами, соединяя любые два узла ребром, если соотвстствуюший внедиагональный блок ненулевой.
Рис. Гх2.1 иллюстрирует эту конструкцию. Заметим, что, как и в с;алярном случае, упорядочение этого нового графа определяется матрицей, которой он отвечает. Как и прежде, мы должны находить разбиения и упорядочения непомеченных графов. Это мотивирует определение фактор-графов, введенное нами в главе 5. р' б.а. Фактор-графьи деревья и древовидные разбиения 173 Пусть 6 = (Х, Е) — заданный непомеченный граф, и пусть й1 — разбиение его множества узлов Х: 'тт = (У! 1'2 ° ° ° 1 р). Напомним (глава 5), что фактор-граф графа 6 относительно $ есть граф ($,8") такой, что (у„у,) еню, если и только если Лс(1(У,)п У, Ф- 8. Этот граф будем обозначать через 6/й1, Отметим, что наше определение фактор-графа относится к непомеченному графу.
Говорят, что упорядочение а графа 6 Рис. 6.2.1. Блочная матрица А, индуциронанное ею разбиение миожестиа узлов ее графа и граф ее блочной структуры совместимо с его разбиением $, если а нумерует узлы каждого множества У, из й) последовательными целыми числами. Ясно, что упорядочения и разбиения графов, отвечающих блочным матрицам, должны иметь это свойство. Упорядочение сс, совместимое с $, индуцирует или подразумевает упорядочение на 6/11; обратно, упорядочение це на 6/$ индуцирует класс упорядочений 6, совместимых с йь. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
