6CAD-CAE-22 Хранение матриц (1014141), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

4

6

5

3

2

1

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

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

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

Использование связных списков с непосредственной алресацией при упаковке.

Сначала вспомним основные понятия, причем безотносительно к непосредственной адресации.

Итак, массив – это простейшая структура данных. Примеры — А (I), В (I, J) и т. д. В массиве могут храниться просто числа.

Другая возмож­ность: массив содержит указатели на элементы более сложной природы, хранящиеся в действительности где-то в другом месте. Все элементы массива доступны непосредственно за время, не зависящее от его размера. Однако следует иметь в виду, что ма­шинная память одномерна, а потому за использование двойных или кратных индексов приходится расплачиваться. Нужно за­метить также, что в машинах с виртуальной памятью массив может находиться на периферийном запоминающем устройстве и не быть легко доступным.

позиция	1	2	3	4	5	6	7	8
A(I)		b		d	a		c
NEXT(I)		7		0	2		4
IP	5
Признак конца	0

Линейный связный список — это последовательность ячеек, связанных в том или ином порядке. Каждая ячейка содержит элемент списка и указатель, сообщающий положение следующей ячейки. Например, предположим, что мы хотим хранить числа а, b, с и d в указанном порядке в массиве А (I). Схема хранения может выглядеть так (символом х отмечены несущественные для нас значения):

В массиве А (I) хранятся элементы списка, а в NEXT (I)— указатели позиций следующих элементов. Необходим еще ука­затель входа IP, показывающий расположение первого элемента. В данном случае он равен 5. В позиции 5 находим первый элемент А (5) — a, a NEXT (5) = 2 сообщает, что следующий элемент нужно искать в позиции 2, Этим путем можно просмотреть весь список. В последнюю ячейку должен быть помещен признак конца, указывающий окончание списка; в нашем примере таким признаком служит 0.

Характеристики

Список файлов лекций