Разряженные матрицы. Р. Тьюарсон (984138), страница 8
Текст из файла (страница 8)
3 обсуждаются дополнительные методы создания разреженных форм ЕР1. Некоторые из них требуют предварительной перестановки строк и столбцов матрицы А для приведения ее к форме, при которой заполнение ограничено только определенными областями этой матрицы. Глава 3 ДОПОЛНИТЕЛЬНЫЕ МЕТОДЫ МИНИМИЗАЦИИ ПАМЯТИ ДЛЯ ХРАНЕНИЯ ЕЕ! ЗА. Введение В этой главе нас будут интересовать главным образом методы, обеспечивающие небольшое заполнение при прямом гауссовом исключении и не требующие в то же время больших затрат. Эти методы обычно именуются «апрнорными» методами, так как информация для выбора главного элемента на каждом шаге преимущественно получается из исходной матрицы, а не из преобразованных форм на каждом шаге. Они обычно приводят к значительной экономии времени и усилий.
Однако такие априорные методы, вообще говоря, менее эффективны для минимизации локального заполнения, чем методы, приведенные в гл. 2. Методы этой главы преследуют цель получения разреженной ЕРЕ Они могут быть разбиты на две категории: первая включает методы, в которых предполагается главным образом априорное упорядочение столбцов, вторая содержит методы, состоящие из таких априорных перестановок строк и столбцов, которые преобразуют матрицу А к различным формам, удобным для гауссова исключения, При прямом гауссовом исключении такие формы или обеспечивают отсутствие заполнения или ограничивают заполнение некоторыми известными областями матрицы. 3.2.
Методы, основанные на априорных перестановках столбцов Наша цель состоит в том, чтобы определить одну матрицу перестановок Я прежде, чем приступить к' гауссовому исключению, а другую матрицу перестановок Р в процессе исключения; причем они должны 52 Гл. а Дополнительные методы минимизации памяти удовлетворять условию РАЯ= А, (3.2.1) где матрица А имеет диагональные элементы, которые обеспечат наименьшее значение общего заполнения, если их, начиная с верхнего левого угла, последовательно брать в качестве главных элементов. Желательно, конечно, минимизировать затраты усилий на определение матриц Р и Я. Опишем некоторые априорные методы нахождения аппроксимации для Я, затем изложим метод аппроксимации для Р, основанный частично на информации, полученной при каждом шаге прямого гауссова исключения.
Из формулы (3.2.1) ясно, что матрица Я определяет порядок, в котором столбцы матрицы А следуют друг за другом при выборе главного элемента. Таким образом, определение матрицы Я эквивалентно предварительному упорядочению столбцов матрицы А, Опишем три метода упорядочения столбцов матрицы ' А, при котором заполнение будет приемлемо малым. Определение, Будем обозначать через ть и сь соответственно общее число ненулевых элементов в 1-й строке и )чм столбце матрицы Вь определенной в равд.
2.5. Из этого определения следует, что где (Гп — (и — й + 1)-мерный вектор-столбец, все элементы которого единицы, и ес — 1-й столбец единичной матрицы (и — й + 1)-го порядка. Теперь из формул (2.5.16) н (3.2.2) имеем ассьс'=(тссьс — 1) (осси> — 1). (3.2.3) Поэтому для данного 1-го столбца минимальное значение фьс> бУдет уссь> = т(п Яссьс' = (ссм — 1) ппп (тсьс — 1) с с с для всех с, для которых Ьссьсс=1, или Уссьс = (сссм — 1) (тсьс — 1), пРичем Ьсьсс = 1.
(3.2.4) З.с Метадон основанные на аерестиновнак столбцов 53 В силу теоремы 2.5.14 очевидно, что из всех элементов (1+ й — 1)-го столбца матрицы АМ1, которые могли бы играть роль главных, тот, что находится в (а+Й вЂ” 1)-й строке, обеспечивает наименьшее значение максимума локального заполнения.
Следовательно, чтобы заполнение было малым, необходимо априорно упорядочить столбцы матрицы А по возрастающим значениям всех у~". Такое упорядочение столбцов матрицы ведет к последовательному ухудшению оценок максимумов локальных заполнений при изменении Й от единицы до и. Это следует из того, что для данного столбца может оказаться невозможным выбрать главный элемент в той строке, которая требуется из условия наименьшего значения максимума локального заполнения, если ранее эта строка была использована при выборе главного элемента для других столбцов. Для получения одного из разложений на множители обратной матрицы А-', которое рассматривается в гл. 5, Орчард-Хейс (1968) рекомендует пользоваться набором у1тп для выбора подмножества столбцов матрицы А и выполнить для этих столбцов прямое гауссово исключение.
После того как исключение произведено для текущего подмножества столбцов, следующее подмножество выбирается исходя из набора у~те', где р — общее число столбцов матрицы А, для которого осуществлено прямое гауссово исключение. Второй метод упорядочения столбцов, оказавшийся полезным на практике, заключается в следующем (Тьюарсон (1967 6)). В 1-м столбце имеется с)е> ненулевых элементов, и каждый из ннх является потенциальным главным элементом. Поэтому, учитывая равенство (3.2.3), среднее значение максимума локального заполнения (если каждый ненулевой элемент столбца имеет ту же вероятность стать главным, что и другие) имеет вид ~ (т$1 — 1) (с)е1 — 1) 11Е1 т (е) с1 54 Гл. а дополнительные методьь минимиэации памяти (для всех ю', при которых Ьф= 1), или Л~ь~ = (4(Ф вЂ” о1Ф) 1 1 —, 1м ), (3.2.5) о~~ где о('ь' = ~ т',ь' (3.2.6) т для всех значений 1, при которых Ь<ад= 1.
Поэтому если столбцы матрицы А упорядочить по возрастающим значениям всех Л'ь>, то, очевидно, заполнение будет сохраняться малым. Третий метод, очень простой, но практически намного менее точный, состоит в упорядочении столбцов матрицы А по возрастающим значениям о'". Практика показала, однако, что использование Л(н' или у'ьэ ! ! приводит к значительно лучшим результатам лишь при небольшом увеличении затрат труда на начальном этапе вычислений (Тьюарсон, 1967 б; Орчард-Хейс, 1968). Можно также выразить у)м в формуле (3.2.4) и Л)м в формуле (3.2.5) следующим образом.
Из теоремы 2.5А4 имеем (3.2.7) для всех значений 1, для которых е',.В е,. =1. Так же, учитывая формулу (3.2.2), имеем е;6ье4 Лм'= —, для всех е'В е =1, $" В е. яе й нт' или Л)ь) = е В,0ье (3,2.8) 4ть В„е4 так как Я е,'. для всех значений 1, для которых е,'.В„е =1, идентично выражению 4 8.2. Методы, основанные на перестановках столбцов бб Перегруппировка столбцов матрицы А с использованием е)п, у'и или Х)п (для всех /) приводит к матрице А, такой, что Л=Аф (3.2.9) Если Р-й столбец матрицы А становится й-м столбцом матрицы А, тогда, имея в виду формулы (3.2.9), получим Аер — — Аев = ЛЯем н, как следствие, ер = Яен, т, е.
р-й столбец единичной матрицы с„является й-м столбцом матрицы Я. Таким образом, перестановка столбцов, которая преобразует матрицу А в матрицу А, примененная к единичной матрице с'„, даст матрицу Я. Получив матрицу А с помощью всех ссс'>, у<пили с)п, мы затем производим прямое гауссово исключение для последовательно взятых столбцов А' и в каждом столбце ищем главный элемент, который лежит в строке с наименьшим числом ненулевых элементов. Очевидно, такой выбор главного элемента должен обеспечить небольшое заполнение на каждом шаге гауссова исключения, Все сказанное можно математически описать таким образом.
Пусть А<П = А и вместо формулы (2.5.3) матрицу А<м определяет выражение Апп = РвА ">, (3.2.10) где матрица Рд получена из единичной матрицы У„ путем перестановки ее (ос+ Й вЂ” 1)-й и Й-й строк, причем значение а 'определяется из условия т~~~ = пип тсм (3.2.11) с длЯ всех значений с, длЯ котоРых ~с)<~'в, ~>е, ив<ив аппроксимация для ф, определяемого формулой (3.2.2). Допустимое значение главного элемента в то же, что и в формуле (2.5.10). Аппроксимация т~м для г!" может быть получена с помощью следующей теоремы (Тьюарсон, 1966). Вб Гл. 8. Г(онолнител»ные методы минимизации памяти Теорема 3.2.12. Если ненулевь<е элементы в последних и — А+ 1 строках и столбцах матрицы А<М распределены случайным образом в этих строках и столбцах и Р',»' является числом ненулевых элементов в ((+й — 1)-й строке матрицы А<»(, то ожидаемое число ненулевых элементов Р',»+о соответствующей строки матрицы А<»+'! равно для ! ) 1 г(»+'>=Р)»(, й(!»+!» ! „=О, (3.2.13) (Р(!»!--!) (Р(!»!- () г<" + и = Рьи + Р'»! — 2— <-! ! ! п — » (3.2.1 4) где матрица А<»+И определяется формулами (2.5.2); (3.2.10) и (2.5.4).
Доказательство. Получим матрицу В» из последних и — й + 1 строк и столбцов матрицы А<»(, заменив в них ненулевые элементы единицами. Из определения матриц В» и В»+, следует, что <-я строка матрицы В» соответствует (! — 1)-й строке матрицы В»+! и (<+Й вЂ” 1, 1+й — 1)-й элемент матрицы А(»! для всех ! и 1 соответствует Ь<! — (<, 1)-му элементу мат'и! рицы В». Если й',+» (, »=О, то о<! =О и ясно, что<-е строки матриц А(»! и А("+и совпадают, из чего следует, что г<»+о = г(»»и = Р(»(, и, таким образом, равенство (3.2.13) доказано. В противном случае, если й<+» ! » ~ О имеем (»! "(»! Ь<! = 1 и новый ненулевой элемент будет появляться во всех случаях, когда й~(~<~=1 и Ь<~!'=О. Обозначим "(Ю через Г(о) вероятность того, что событие о произойдет.
Так как элементы матрицы В» распределены случайным образом (поскольку так распределяются соответствующие элементы матрицы А(Ю), то Г(',Ь((<(=1 и Ь(<<(= О) =Г(Ь<!'= 1) ГЯ'=О) = ( „) (1 — ~) . (3.2.1»( 8 2. Методы, основанные на перестановках столбцов 57 Здесь использовано то обстоятельство, что если исключить первый столбец матрицы Вм то относительное число ненулевых элементов первой и <-й строк для оставшихся п — й столбцов соответственно равно (Р1х> — !)/(и — й) и (Р<<х> — 1)/(и — й), так как й<е> = = Ь>~~>~ = 1. Теперь из формулы (3.2.15) следует, что ожидаемое значение заполнения (-й строки матрицы В» равно Прибавляя к этому Р<сх> (начальное число ненулевых элементов) и вычитая единицу, поскодьку а<"+'>, =О, имеем Р1е> 1 ~ у<~ми Р<а>+ (Рю 1) (1 ) ! что после упрощения дает формулу (3.2.14).
Этим завершается доказательство теоремы. Применение установленной теоремы начнем со значения у<<а= т",>, где т',о е,'В>т'„а матрица В, получена из матрицы А<'> = Х (см. формулы (3.2.2) и (3.2.9)). Чтобы сохранить простоту обозначений, будем понимать под т<е' не только точное число ненуле вых элементов (<+й — !)-й строки матрицы А<к>, но и его приближенное значение. Для каждого й, учитывая формулы (3.2.10) и (3.2.11), вычислим Р<м Р т<е> (3.2. 16) где Р<к> и т<"> — (и — й+ 1)-мерные векторы, компоненты которых определяют соответственно число ненулевых элементов строк матриц А<к> и А<к>, Затем мы используем формулы (3.2.13) и (3.2.14), чтобы по значениям Р<<х> получить значения те+>< для всех 1 «с ( и — й+ 1 на каждом шаге Й. Этот метод позволяет избежать вычисления точного значения т',х' для каждого й из соответствующих матриц Вд. 88 Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
