Разряженные матрицы. Р. Тьюарсон, страница 11

Из следствия 3,5.5 заключаем, что второй и третий столбцы матрицы В расположены в первом диагональном блоке, а остальные столбцы — во втором диагональном блоке. Поэтому Е 0 0 0 0 В= РВЯ= 1 1 1 0 0 0 О 0 3.6. Треугольная блочная форма Если матрица Л задана в виде (3.3.1), причем подматрицы Ар; — 0 для 1Ф р и подматрицы Ап, 1 = 1, 2, ..., Р, являются квадратными матрицами, то говорят, что матрица А имеет треугольную блочную грорму (ВТГ). В этом параграфе описываются некоторые методы перестановок, которые приводят матрицу В (а значит, и матрицу А) к форме ВТР. 1 0 0'0 0 0 0 1 0 1 0 0 , 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 72 Гл.

8. Дояолнительные 'методы минимизации иамяти Первый метод использует два вида перестановок: РВ4=В (3.6.1) И РВР'= В, (3.6.2) где  — матрица, у которой все диагональные. элементы равны единицам,  — матрица в форме ВТР. Из формул (3.6.1) и (3.6.2) имеем РВ9= В, Р = РР и О =г;1Р'. (3,6.3) Задача заключается в определении- матриц Р и (! по формулам (3.6.3). Если матрица А неособенная, то должен существо- вать по меньшей мере один ненулевой член в ее де- терминанте. Этот ечлен состоит из произведения п эле- ментов матрицы, взятых по одному в каждой строке и каждом столбце.

Таким образом, строки и столбцы матрицы А могут независимо друг от друга перестав- ляться так, 'чтобы все ненулевые элементы в этом члене были диагональными. Определение матриц Р и йг в формуле' (3.6.1), таких, при которых Бы — — 1 для всех ! = 1, 2, ..., и, производится следующим обра- зом (Стьюард (1962), (1965); Далмейдж и Мендель- сон (1963), Кеттлер и Вейль (1969), Харари (197!а), Дафф (1972)). Алгоритм 3.6.4. Положить н В=Во У,=~ ео 0~=Ут, т ! Р, Щ=! и м=!. Шаг 1 Для всех 1, у при Ьн= 1, е(Уя=! вычислить е,' ВУя+ (7иВея =ш!п(еЗУе+ ИяВе!).

(3 б 6) и мт З.б. Треугольная блочная форма Если нет такой пары (й 1), для которой выполняются условия (3.6.5), то перейти к шагу 2, в противном случае положить равными нулю аь-й элемент )гь и йь-й элемент (1ь Переставить й-ю и аь-ю строки в матрице Рь и й-й и рь-й столбцы в матрице Яь. Заменить й на й+ 1.

Если й = а+ 1, перейти к шагу 2, в противном случае вернуться к началу этого шага. Замечание. Для каждого значения й выбирается (ам рь)-й элемент матрицы В в качестве (й, й)-го элемента матрицы В, определяемой формулой (3.6.1). Так как все элементы, лежашие в гьь-й строке или рь-м столбце матрицы В, не могут быть выбраны позже в качестве диагональных элементов матрицы В, то формулы (3.6.5) и (3.6.6) гарантируют, что выбор остальных диагональных элементов матрицы В будет возможен из максимального числа ненулевых элементов матрицы В. Это в свою очередь означает, что к окончанию текушего шага только небольшое число строк и столбцов, вообше говоря, не будет использовано при выборе диагональных элементов матрицы В. Ерли й = л+-1, то это значит, что все ненулевые диаго. 'нальные элементы найдены.

Шаг 2. Вычислить В~м = РьВЯь. - (3.6.7) Если й = и+ 1, то В = В<ь> и перейти к шагу 3. В противном случае 'в соответствии с блок-схемой, представленной на рис. 3.6.1, привести матрицу В<я~ путем перестановок к матрице В<я+и, все диагональаые элементы которой равны единице. Замечания к рис. 3.6.1. Заметим, что переход к блоку 12 имеет место тогда, когда немаркированные строки маркированных столбцов не содержат ни одной единицы.

Так как число маркированных столбцов з этот момент на единицу больше чем число маркированных строк, то матрица является особенной. Следовательно, для неособенных матриц нет перехода к Рис. 3.6Л. Блок-схема для получения диагонали нз единиц в матрице В'й1. ЯС вЂ” номер выбранного столбца, Бй — номер выбранной строки, ПСС вЂ” список цепочки номеров столбцов. 2. Имеется ли едивица в немаркированной строке БС-го столбца? 3, Номер такой строки .+5Н. Маркировать БС-й столбец н БК-ю строку, Поместить БС в ь1СС. б.

Произвести циклическую перестановку столбцов в матрицах В~й~ в н Сй, используя номера столбцов в ь1СС. Очистить ь!СС и переставить й.ю и Бд-ю строки в матрицах Всйг и Рй. Заменить й на а+1. Ю. Имеется ли какой-либо маркированвый столбец с единицей в немаркн. рова ююй строке) Н.

Поместить вол~ар такого столбца в БС, а номер такой строки в БД, Маркировать 5П-ю строку. Исключить из ь!СС все номера столбцов, следуюшнх в списке за БС. З.б. Треугольная блочная форма блоку 12 и всегда возможно получение матрицы Во тн со всеми единицами на диагонали.

Матрица Вио содеРжит все нУли в юго-восточном УглУ, т. е.е,'. Воаег = 0 для всех ь, 1) й. Преобразование матрицы Вии в матр|шу В<а+') предполагает предварительное определенне цепочки от единицы й-го столбца в северо-восточном углу к единице какой-нибудь строки в юго-западном углу матрицы Вьа~, как показано на рис. 3.0.2.

Список столбцов хранится в Е1СС. Затем осуществляется / у г' у циклический перенос столбцов й-ь-)г — ь-)а-~)з-ь. й, ко- ° торый обеспечивает переход ° ! единицы из юго-западного угла в юго-восточный угол, Если в какой-либо момент вычислений в немаркированпой строке рассматриваемого столбца единицы нельзя найти, то с помощью 0 блоков 10 и 11 (рис. 3.6.1) производится поиск другой последовательности столб- Ряс. з.блк цепь от ссвсроцов, образукнцих цепочку восточного до юго-запад- ного угла.

до тех пор, пока она не будет включать столбец с единицей в юго-западном углу. Маркировка строк и столбцов матрицы Вио обеспечивает то, что процесс вычислений, приводящий к столбцу, в котором отсутствуют единицы в немаркированных строках, не может быть снова повторен и цепочка определяется за конечное число шагов. Заметим, что ЫСС должен быть списком номеров столбцов матрицы В(">, которые образуют цепочку от единицы в я-м столбце к единице в юго-западному углу, и поэтому в блоке 11 из 11СС необходимо исключить столбцы, приводящие к тупику в процессе образования всей цепочки. Шаг 3. Положить Ра = Р и Яа = 0. Диагональ матрицы В состоит из одних единиц и алгоритм завершен.

76 Гл. г дополнительные методы минимизации памяти Замечание. Определение таких матриц Р и ее, при которых все диагональные элементы матрицы В ненулевые, эквивалентно такому перенумерованию вершин меченого двудольного графа !1е, соответствующего матрице В, при котором-любые две вершины наборов 7т' и С с одинаковыми номерами являются смежными (связаны ребром). Максимальная длина ряда единиц расположенных по главной диагонали матрицы, называется максимальной трансверсалью (Далмейдж и Мендельсон, 1963).

Напомним, что для неособенной матрицы и-го порядка длина максимальной трансверсали равна и. Определение матрицы Р в формуле (3.6.2), со ставляющее вторую часть первого метода преобразования матрицы В к матрице В в форме ВТР, основано на следующей теореме. Теорема 3.6,8. Если все диагональные элементы матрицы В единицы и Вз +'=Вз" ьВз, (3.6.9) то существует такое йь что В' '+' = Вз ' =Р, (3.6.10) и е,'Рее = !тогда и только тогда, когда существует на правленный путь от 1-й вершины к )сй вершине графа ь)о (помеченный направленный граф, соответствующий матрице В). Доказательство.

Так как В ®1 = В, то из теоремы 3.4.9 следует, что е',В'в~=1 тогда и только тогда когда существует направленный путь, длина которого меньше или равна т, между е'-й и )чй вершинами графа (ео. Если т — максимальная длина направленного пути между любыми двумя вершинами графа 1!о, то ч ~ и и, очевидно, для всех 2" ) ч матрица В'" не изменяется. Поэтому существует йь удовлетворяющее условию (3.6.10), и, следовательно, е',Ре =1 тогда и только тогда, когда существует направленный путь от 1-й вершины к 1-й вершине. Это завершает доказатель ство теоремы. а.б.

Треугольная блочная форма Если в теореме 3.6.8 вместо матрицы В начать с матрацы В, полученной из матрицы В с помощью алгоритма 3.6.4, а затем вычислить матрицу Р или в соответствии с формулами (3.6.9) и (3.6.10), нлн методом Камстока, описанным после доказательства теоремы 3.5.1, 'то е',Ре =е'Рее=1 означает, что 1-я и )чя вершины лежат на одном и том же направленном цикле. Так как вершины графа ьгрь лежащие на одном н том же направленном цикле, принадлежат одному и тому же диагональному блоку матрицы В, то можно использовать матрицу Р для определения матрицы В по полученной матрице В следующим образом (Харари (1962)). Определим все такие 1, что е',Ре =е'Ре, 1.

Тогда все строки и столбцы матрицы В с такими индексами принадлежат одному и тому же диагональному блоку магрицы В. Исключим (или промаркируем) все такие строки и столбцы в матрице Р. Следующая неисключенная (или немаркированная) строка н соответствующий столбец могут теперь быть использованы точно таким же способом, как и первая строка и первый столбец для определения строк и столбцов другого диагонального блока и так 'далее. Таким путем всем строкам и столбцам матрицы В могут быть поставлены в соответствие диагональные блоки. Заметим, что если' Р = Р', то матрица В может быть преобразована с помощью перестановок к форме ВПГ (это другой возможный путь решения, хотя н более медленный, чем изложенный в параграфе 3.5). Для того чтобы упорядочить диагональные блоки так, чтобы матрица В имела форму ВТР, поступаем следующим образом. Каждому диагональному блоку ставим в соответствие строку и столбец, причем каждый элемент этой строки получается логическим суммированием элементов исходной матрицы Р, стоящих на пересечении строк, принадлежащих данному та Гм 3.