LEC-25 (Материалы к лекциям), страница 3

loc (i, j, ... ,  ) (location - размещение),

определенной на множестве индексов. Для любой комбинации индексов i, j, ... ,  элемента исходного множества адресная функция дает адрес этого элемента в записи массива. Разные структуры исходного множества требуют различных адресных функций. Рассмотрим ряд частных примеров.

1. Массив прямоугольной структуры с лексикографическим упорядочением.

Адресная функция в этом случае является функцией индексов

loc (i, j, ... ,  )= loc (1, 1, ... , 1 )+ С_о+ С_{1 i} + С_{2 j} + ... + С_{t } , (1)

где C₀ , C₁ , ... , C _t - коэффициенты линейной формы, представляющей

адресную функцию;

t - размерность (т.е. число индексов массива).

Обозначим через n₁ , n₂ , ..., n_t , размер исходного массива, соответственно по индексам i , j , ... ,  .Можно показать, что :

С _t = 1

С _t-1 = n_t

С _{t -2}= n_t n_t-1

........................

С ₂= n_t ...... n₃

С ₁ = n_t...... n₃ n₂

C₀ = - (C₁ + C₂ + ... + C_t )

В loc (1, 1, ... , 1 ) хранится адрес начала записи массива в ЗУ.

Постоянное смещение C₀ возникает вследствие того, что индексы i, j, ... ,  начинаются не с нуля, а с единицы. Объем памяти, необходимый для записи массива описываемой структуры

l₁ = n₁ n₂ n₃ ...... n_t

Например, при t = 3 будет:

loc (i, j,k )= loc (1, 1,1 )+ С_о+ С_{1 i} +С_{2 j} + ... + С_3k

Пусть i = n₁ = 5 j = n₂ = 3 k = n₃= 7

C₃ =1 C₂ =7 C₁ = n₃ n₂ = 21

C₀ = - (C₁ + C₂ + C₃ ) = - (21 + 7 + 1) = - 29

loc (1, 1,2 )= - 29 + 211 + 71 + 12 = 1

loc (1, 1,3 )= - 29 + 211 + 71 + 13 = 2

loc (1, 1,7 )= - 29 + 211 + 71 + 17 = 6

loc (1, 2,1 )= - 29 + 211 + 72 + 11 = 7

2. Симметричные матрицы

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

Эти матрицы жесткости симметричны, т.е. a_{i j} = a _ji и в силу этого достаточно запоминания только элементов a_{i j} , для которых j  i .

Если порядок соответствующей матрицы равен n, то число таких элементов

l₂ =

3. Симметричные ленточные матрицы

Матрицы жесткости подструктур при надлежащей нумерации узловых неизвестных приобретают ленточную структуру. Не равными нулю оказываются элементы, расположенные на ( h-1 ) линиях, параллельных главной диагонали ( h - ширина ленты)

a _ji = 0 ( j  i + h-1, j  i - h+1 )

В этом случае с учетом симметрии матриц достаточно ограничиться запоминанием только элементов главной диагонали и ( h-1) наддиагоналей.

Часто для упрощения адресной функции таких матриц не учитывают сокращения длины строки при i > n - h +1 ( i - h+1 < j < i + h-1).

При этом адресная функция принимает вид

loc (i , j)= loc (1,1) - h + i ( h - 1) + j

Подобное представление целесообразно при малых h, так как с ростом этой величины потери памяти на дополнение строк матрицы стремительно возрастают. В этом случае число хранимых элементов матрицы

l₃ = n h

В качестве примера можно предложить адресную функцию более совершенного вида, используемую в комплексе КАСКАД-2.

Количество хранимых элементов в этом случае

;

Эта адресная функция приводит к появлению лишних ячеек, что демонстрируется ниже в последнем примере.

Для записи ленточных верхних треугольных матриц можно использовать этот же метод. Такие матрицы появляются, например, в алгоритме МКЭ в результате выполнения прямого хода методом исключения Гаусса в системе уравнений равновесия подструктуры с симметричной ленточной матрицей.

Иллюстрация приведенных методов хранения матриц:

j

1

2

3

4

5

6

1 i l4 = n h - a11	a12	a13				l3 = n h
1 a21	a22	a23	a24
1 a31	a32	a33	a34	a35
4			a44	a45	a46	a11 a12 a13 a22 a23... a55 a56 a66
0 или симметрично 5 0 0 упрощенная адресная функция				a55	a56
6 0					a66

Для сокращения записи матрицы и ускорения ее обработки следует стремиться к минимизации ширины ленты. Однако часто, особенно в конструкциях с вырезами, затруднительно получить малую по сравнению с порядком системы ширину ленты.

В заключение следует упомянуть еще об одном методе уплотнения записи больших матриц, основанном на различном представлении в ЭВМ чисел с фиксированным положением десятичной точки и чисел, представленных в виде мантиссы и порядка. При обычном развороте матрицы с учетом ее структуры (симметричная, ленточная и т.д.) каждая группа подряд идущих нулевых элементов заменяется целым числом, равным количеству таких элементов.

Поскольку это целое число имеет соответствующее представление в памяти, оно может быть автоматически выделено в процессе обработки матрицы, и ее структура будет восстановлена. Объем хранимой информации при таком методе не превышает объема исходной матрицы, при значительном количестве групп нулевых элементов может быть получена большая экономия памяти. Такая форма записи целесообразна для матриц жесткости подструктур, особенно нижних уровней.