Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 79
Текст из файла (страница 79)
(5) 203) 20Л. ХАРАКТЕРЫ И НЕРАВЕНСТВА 3 20.4, 3 20.5). Грани приведены нилве: т4 тв ТЗ Т4 тв тв Грань 1 1 О 1 О 1 Грань 2 2 1 3 2 1 3 Грань 3 1 2 3 2 1 3 Грань 4 1 2 3 1 2 3 (7) Из первой строки (6) видно, что х, соответствует ув, хв соответствует ую а хт соответствует 74. Таким образом, характер а4 задает неравенства (ло граням (7)): по грани $: $хв + 1хв '; Ох, )~ 1; по грани 2: Зхв .р 1хв + 2х, ) 3; по грани 3: Зх,+1хв+2х,)3; по грани 4: Зхв + 2хв +.
1хт ) 3. (8) Характер $а не поро;кдает пи одного неравенства, поскольку правой частью является О. Из $в мы видим, что ха соответствует ую а хв соответствует ув. Таким обрааои, из (7) получаем неравенства: 4хв + Фхв )~ 4; Зх, + Зх, ) 3; Зх,+Зх,)З; Зх +3. )3. (9) Заметим, что в процессе получения неравенств нет необходимости знать, какой элемент группы какому базисному столбцу соответствует. Мы используем $4 непосредственно. Исключая дублирующие неравенства из (8) и (9), получаем Зх,+Зх, >~ 3, Зхв+ хв+ 2хт)3, Зхз+ 2хв+ х,) 3, (10) Зхз+ 5хв+ 4хт ~ >3, Зхз + Зхв ) 3. 29 т. хт Если бы мы воспользовались циклическим целочисленным алгоритмом, то получили бы следующее множество неравепств, более слабое, чем (10): ПРИЛОЖЕНИЕ А НОРМАЛЬНАЯ ФОРМА СМИТА (ХУ (1121) В этом приложении рассматривается преобразование полностью целочисленной квадратной матрицы в нормальную форму Смита О зз где е, делит ееы (1 = 1,..., т — 1).
Мы рассматриваем приведение матрицы к нормальной форме Смита как задачу нахождения нового множества базисных и единичных векторов. (Поскольку все вычисления производятся по модулю В, будем предполагать, что элементы матрицы принимают значения, заключенные между О и  — 1.) Пусть Ьо Ьз,..., Ьм — множество базисных векторов в.Лм, где Тогда Ьт= ~ (осе;, 1=1 где е, — вектор-столбец, у которого г'-я компонента равна 1, а остальные компоненты — нули.
Выберем новое множество базисных векторов Ь,', Ь;,..., Ь~„и новое множество единичных векторов е;, такое, что Ь)=е;е; 'для 1=1, ..., т, О О з1 О ..., Ь„',= О Кроме того, е, делит еги (1 = 1, ..., т). т. е. каждое Ь; равно е;, умноженному па скаляр в вовои коорди- натной системе: НОРМАЛЬНАЯ ФОРМА СМИТА 451 Для данкой матрицы [Ьм) требуемое преобразование достигается: (1) перестановкой столбцов или строк; (2) сложением (или вычитанием) одного столбца с (или из) другим столбцом или одной строки с (или из) другой строкой.
Операции со столбцами формируют новый базис Ъ;, 1 = 1,..., пв, с помощью целочисленных комбинаций векторов старого базиса Ъя а операции со строками формируют новые единичные векторы е; с помощью целочисленной комбинации векторов ея Опишем сначала стандартную процедуру приведения полностью целочисленной квадратной матрицы к нормальной форме Смита. Ш а г 1.
Перестановкой столбцов и строк добьемся, чтобы Ь,в был наименьшим по абсолютной величине среди ненулевых элементов матрицы. Перейдем к шагу 2. Ш а г 2. Если Ь~| делит Ь„, 1 = 2, ..., пв, перейдем к шагу 3. Если Ь,в не делит Ьм для некоторого у=й, то Ь,» =- иь„+ д, где и — целое число и 0( д( Ь||. Полок|им Ъд = Ъд — пЪ| и Ъ;. = Ъ; для у ~ й. Эту операцию осуществляем, вычитая и раз 1-й столбец из к-го столбца. В результате получим Ь;д = д, где д ( Ь!|.
Перейдев| к шагу 1. Ш а г 3. Если Ь|| делит Ья(| = 2,..., пв), перейдем к шагу 4. Если Ьи не делит Ьп для некоторого |= Ь, то Ьд, = пбв +|в, где и — целое число и 0 ( д ( Ьп. Положим е,' = е| + пед и е|| = е; для | чь 1. Эту операцию осуществляем, вычитая и раз 1-ю строку из Ь-й строки. Чтобы убедиться в этом, рассмотрим вектор-столбец Ъ)| Ъ, = Ь!;е, -Ь Ьыев +... -( Ьд;е„+ ...
+ Ь теде или Ъ, = Ь|; (с', — пед) + |ч;ев'+ ... + Ьд;ед + ° .. (- Ь~ге', или Ъ | — Ьв|е', + Ьмев -'г... -! - (Ьд| — иЬ! г) ед +... + ЬФ|е~. Перейдем к шагу 1. Шаг 4. Поскольку положительное Ь|, делит Ь„(1=2, ...,т) и Ьп (|=2,..., т), предположим, что Ь„=п,ЬИ, а Ьв|=и,ЬМ. Положим Ъ;=-Ъ,— и;Ъ|, Ъ;=Ъ, (т. е. вычтем из )сто столбца пт раз 1-й столбец), е', =е,-',— и,е,+ п,с,+...-; п,„е,„; е';=с|, |М1, пниложкник А что, как указано выше, реалиауется посредством вычитания из ~-й (1 Ф 1) строки п; раз 1-й строки.
Это преобразование даст новудо матрицу, представленную таблицей А. Таблица Л Перейдем к шагу 5. Ш а г 5. Если Ьы делит Ь;;, ~ Ф 1, ! Ф1, применим пдаги с первого по четвертый к матрице размерности (т — 1) х (т — 1) из табл. А. Если Ь,д пе делит Ь;,, то полок;им Ьм — — пЬдд + д, где О «д ( Ьк, тогда следующая последовательпость операций переместит о на позицию (1,1).
Проиллюстрируем эту последовательность операций на матрице размерности 2 х 2: ( О д„.' д) ( д„д„д-д) ( д„д ) ( — д„ь„)' В результате мы получим новое Ьп — — д, имеющее меньшее значение, и можем возвратиться к шагу 1. Так как (Р— 1) — наиболыпее целое число в матрице, то не более чем через!ода Р циклон (цккл — шаги с первого по пятый) Ьи будет делить дсь 1 Ф 1, 1 Ф 1, или Ьд, будет уменьшено до 1. Найдем верхндою границу числа операций, необходимых для этой процедуры.
Используем следующие символы для обозначения операций: г; сравнение двух чисел, с: проверка делимости, 1: многократное вычитание одного числа из другого, р: изменение положений двух чисел. Тогда для (т;< т)-матркцы необходимо тза '- 2тр операций иа шаге 1, т(с+б-5 р) па шаге 2, т(с+с-(-р) на шаге 3, 2т(т — 1)д на шаге 4 и (т — 1)'с-(-2т(~+р) на шаге 5. Поскольку (Р— 1) — наибольшее целое число в матрице, то после не более чем )ой, Р циклов (шагов с первого по пятый) мы нОРИАльнАН ФОРИА смитА получим матрицу, в которой ди делит Ьм, 1 Ф 1, у Ф 1, и является единственным ненулевым элементом в первой строке и первом столбце.
Таким обрааом, чтобы привести матрицу к нормальной форме Смита, необходимо не более + ~ т(т+1) (2т+1) л + з операций. Если мы рассмотрим достаточно болыпое т и подсчитаем старшие члены, то получим 1оиз Р (тэг)З -( Зтэр+ т'с)3+ 2т"()3). Если группа (В г)/(1) имеет ранг г, то после того, как г диагональных элементов получены, в оставшейся матрице размерности (т — г) х (т — г) все элементы будут равны О. Это происходит в случае, если мы пытаемся привести матрицу В ' к нормальной форме Смита.
(Мы используем числители элементов матрицы В 1.) Ксли рассмотрим г, малые по сравнению с т, то получим 1ояз Р(т та+бтгр .',. тгс+ 2тэг). (2) Сейчас мы предложим новую процедуру приведения матрицы к нормальной форме Смита. Она очень похожа на стандартную, за тем исключением, что мы сначала диагоналиаируем матрицу, а затем пРовеРЯем, Делит ли Ьм элемент Ьгьь РРО Эта ЛРоЦеДУРа состоит из следующих шагов. Ш а г 1. Переставим столбцы и строки так, чтобы Ь,1 был наименьшим по абсол~отпой величине среди всех ненулевых элементов в первой строке н первом столбце матрицы.
Перейдем к шагу 2. Ш а г 2. Такой же, как в стандартной процедуре. Ш а г 3. Такой же, как в стандартной процедуре. Ш а г 4. Такой же, как в стандартной процедуре. Ш а г 5. Будем повторятыпаги с 1-го по 4-й до тех пор, пока матрица не станет диагональной. Перейдем к шагу 6. Ш а г 6. Коли Ьы делит Ьм (1 = 2,..., т), то проверяем, делит ли Ь„элемент Ьы() =- 3,..., т)....
Этот процесс повто- РЯетсЯ До тех поР, пока не Установим, что Ьн Делит Ььы, Ры пгилоншние А (1 = 1,..., и — 1). Если Ьп не делит Ьп, то переходим к шагу 5 стандартной процедуры, чтобы получить новое Ьп меньшей величины. Поскольку матрица диагонализирована, мы имеем дело с матрицей раэмерности 2 х 2 Ьм (( = 2,..., и). Подсчитав число операций, получим 2та+ 2тр т(с+с+ р) т(с+1+ р) 2т(т — 1) 8 на шаге 1, на шаге 2, яа шаге 3, па шаге 4. После и циклов (шагов с 1-го по 4-й) матрица диагонализируется.
Включая операции на шаге 6, имеем т(и+1) с+ [2т(т+1)+4т1одг1)] р+ + [ т (и + 1) + 2 и (т + 1 ) 1овг 1)~ с + ~ т(сг+1) (Зт+1) +4 1~д~ 13~~1, (В) Если рассмотрим достаточно большое т и подсчитаем только старшие члены, то получим ига+ [2иг-[-4т 1оагП] р+ ~т~+ — т 1одг О~ с-]- + [2тз)3 — ' 4т 1одг 1)] 1. (4) Если применим пашу процедуру к (В гД1), и если группа имеет ранг г (т)г >) 1), то общее число операций равно 2тга+ (4тг+ 4г 1одг В) р+ (2тг + тг 1одг В) с + -]- (2тгг+*1одг В) Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
