Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

что, как указано выше, реализуется посредством вычитания из i-й (i ф 1) строки nt раз 1-й строки.

не более чем через log2Z) циклов (цикл — шаги с первого по пятый) Ьи будет делить bi;-, i ф 1, / ф 1, или Ьи будет уменьшено до 1. Найдем верхнюю границу числа операций, необходимых для этой процедуры. Используем следующие символы для обозначения операций:

s: сравнение двух чисел, с: проверка делимости,

t:многократное вычитание одного числа из другого,

р: изменение положении двух чисел.

получим матрицу, в которой Ъи делит Ьц, i =И= 1, j ф 1, и является единственным ненулевым элементом в первой строке и первом столбце. Таким образом, чтобы привести матрицу к нормальной форме Смита, необходимо не более

( 1)

операций.

Если мы рассмотрим достаточно большое т и подсчитаем старшие члены, то получим

log2 D {m3s/3 + 3m2p -J- m3c/3 + 2m3i/3}.

Если группа имеет ранг г, то после того, как г диагональных элементов получены, в оставшейся (матрице раз­

Сейчас мы предложим новую процедуру приведения матрицы к нормальной форме Смита. Она очень похожа на стандартную, за тем исключением, что мы сначала диагонализируем матрицу, а затем проверяем, делит ли Ън элемент bi+1, *+i. Эта процедура состоит из следующих шагов.

Ш а г 1. Переставим столбцы и строки так, чтобы bli был наименьшим по абсолютной величине среди всех ненулевых элементов в первой строке и первом столбце матрицы. Перейдем к шагу 2.

(i = 1, . . т — 1). Если Ьп не делит Ьн , то переходим к шагу 5 стандартной процедуры, чтобы получить новое Ъц меньшей вели­ чины. Поскольку матрица диагонализирована, мы имеем дело с матрицей размерности 2 x 2

1Ъп 0 \

\ 0 пЪп -ь q) '

Если к этой матрице мы применяем шаги со второго по четвер­ тый стандартной процедуры, то либо будем иметь диагонализированную матрицу с Ъи, делящим bih либо будем иметь элемент, меньший q и занимающий положение (1,1). Таким образом, не бо­

лее, чем через log2 D [тс + 4 (t + р)] операций, мы получим Ъп , которое делит

Ъц (г = 2, . . ., т).

Подсчитав число операций, получим

После т циклов (шагов с 1-го по 4-й) матрица диагонализируется. Включая операции на шаге 6, имеем

т (m + 1) s-(- [2т (т-\- 1) + 4то log2 D\ р -f-

-t-j|m (m +l) + ym (m + l)log2Z>Jc +

Если рассмотрим достаточно большое т и подсчитаем только старшие члены, то получим

m2s + [2ттг2 -(- 4т log2 D] р + \^т? + у иг2 log2 D J с -j-

Если применим нашу процедуру к {В_1}/{1}, и если группа