5.3. Статические и динамические схемы хранения.

Алгоритм для разреженных матриц может порождать новые ненулевые элемент, множество которых называется заполнением матрицы. Прежде чем начнется выполнение такого алгоритма, нужно убедиться в том, что в памяти есть место для новых элементов.

Структура данных, заготовленная до начала численной обработки , называется статической структурой . Ее формирование требует знания числа ненулевых элементов и их положения в матрице еще до того , как они будут вычислены. Такие алгоритмы как сложение матриц, Гауссово исключение , когда последовательность главных элементов известна заранее , позволяют это сделать (для положительно определенных матриц). При этом алгоритм распадается на две части: символическую, когда происходит определение портре­та новой матрицы, и численную часть, где выполняются реальные вы­числения по уже известному портрету и исходным данным. Результат символического этапа - статическая структура данных; результат численного этапа - значения ненулевых элементов, размещенных в ячейках памяти, которые были заготовлены на символическом этапе.

Следует заметить, что названные выше алгоритмы для некоторых специальных матриц не требуют символического этапа, так как новые ННЭ не появляются. К таким матрицам относятся, например, ленточ­ные, для которых мы будем рассматривать гауссово исключение в со­ответствующем разделе.

К сожалению, статические структуры могут применяться не во всех случаях. Например, метод Гаусса с выбором главного элемента для матриц общего вида. Чтобы не допустить сильного роста ошибок, главные элементы выбираются в ходе исключения сообразно с их чис­ленными значениями. При этом осуществляется перестановка строк и столбцов, которые влияют на расположение получающегося заполнения. Следствием является непредсказуемость портрета результирующей мат­рицы, а решение о том, где и как разместить каждый новый элемент, должно приниматься, когда этот элемент уже вычислен и готов к запи­си в память. Такая процедура называется динамическим распределением памяти и порождает динамическую структуру данных. Существуют специальные приемы реализации такой структуры [8,9]. Мы, однако, будем рассматривать лишь алгоритмы,, приводящие к статической струк­туре. Это связано с тем, что любую матрицу можно привести к симмет­ричной положительно определенной путем умножения на транспонирован­ную и далее иметь дело со статической структурой данных , а это ал­горитмически проще .

5.4. Метод переменного переключателя

Метод применяется для слияния разреженных целых списков, ко­торыми являются столбцовые индексы ННЭ разреженной матрицы. Опера­ция повторяется многократно при выполнении практически любых дей­ствий с разреженными матрицами. Суть метода состоит в следующем.

Пусть даны три списка:

Результирующий список (скажем, М) имеет вид:

список М : 2, 7, 8, 5, II

Слияние есть операция ИЛИ с включением: целое число, принадлежит результирующему списку тогда и только тогда, когда оно принадлежит хотя бы одному из заданных списков; при этом повторения не допускаются. Очевидно, что первый список может быть включен в ре­зультирущий сразу полностью. Затем выясняется вписано ли очеред­ное число второго списка в результирующий. Если вписано, то спи­сок М остается без изменений, если нет - очередное число вписы­вается в результирующий описок.

Чтобы эффективно определить, вписано ли данное число в ре­зультирующий список, используется массив переключателя IX. Сразу после того, как в рассматриваемый список М было добавлено число I , в позицию I массива IX записывается определенное число-пере­ключатель. Обратно, прежде чем добавить число K к списку M , мы проверяем, будет ли значение IX (К) равно переключателю и ,ес­ли оно не равно, число К заносится в список М . Вначале массив IX обнуляется: при этом N раз выполняется оператор IX (I) = О. В нашем случае последовательность действий далее будет такой (в качестве переключателя берем 1):

1)Максимальное число в трех списках равно 11, значит, длина массива IX равна 11,N = 11.

2)Массив IX обнуляется, т.е. 11 раз выполняется оператор IX (I) = О.

3)Список A полностью заносится в список М . После этого имеем:

4) Производим слияние списка М со списком B.

IX(3)=1? Да. Список М не меняется.

IX(11)=1? Нет. В список М заносится 11 и IX(11)=1

IX(5)=1? Да. Список М не меняется.

Состояние списка М : 2 , 7 , 3 , 5 , 11.

5. Производим слияние списка М со списком С .

:

IX(7)=1? Да. Список М не меняется.

IX(2)=1? Да. Список М не меняется

Результирующий список М : 2, 7, 3, 5, 11.

В технологии разреженных матриц слияния используются для построе­ния столбцовых индексов n строк матрицы А (мерности ). Для этого потребуется n различных слияний. Если перед каждым слиянием массив IX обнулять, то затраты машинного времени будут неоправданно высокими. Можно предложить следующий выход: перед каждым новым слиянием менять значение переключателя, начиная с 1. Тогда обнуление массива IX делается только один раз. Таким обра­зом, перед первым слиянием все позиции IX заняты нулями, перед вторым - 0 или 1, перед третьим 0,1 или 2 и так далее. Во время выполнения К -го слияния все числа меньше К , записанные в IX, воспринимаются как нули в приведенном примере и не мешают прове­дению К -го слияния. В связи с описанным здесь приемом, метод и получил название "метод переменного переключателя",

Очевидно, что метод используется на этапе символической об­работки.