WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПММ Кафедра вычислительной математики МЕТОДЫ РЕШЕНИЯ СИСТЕМ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ СПОСОБЫ ХРАНЕНИЯ И ПРЕДСТАВЛЕНИЯ РАЗРЕЖЕННЫХ МАТРИЦ, ОПЕРАЦИИ НАД НИМИ Методические указания к спецкурсу для студентов 3 курса дневного и вечернего отделений факультета ПММ Составители:

И.А.Блатов Т.Н.Глушакова М.Е.Эксаревская Воронеж – 2002 - 2 - СОДЕРЖАНИЕ §1. Введение …………………………………………………………………….. 3 §2. Способы хранения и представления разреженных матриц ……….……... 3 §3. Операции над разреженными матрицами …………………………...……. 9 §4. Метод Гаусса для разреженных матриц …………………………………. 24 Литература …………………………………………………………………. 33 - 3 - §1. Введение Строгого определения разреженной матрицы нет, но есть “нестрогие” определения, некоторые из которых мы здесь приведем.

О п р е д е л е н и е 1.1. Разреженная матрица ( РМ ) – это матрица, у которой “много” элементов равно нулю.

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

РМ возникают при решении многих прикладных задач. Назовем некоторые из них:

1) дискретизация уравнений математической физики – разностные схемы и метод конечных элементов;

2) задачи линейного программирования (теория оптимизации);

3) задачи теории электрических цепей.

Основная задача курса – научиться строить эффективные алгоритмы решения систем линейных алгебраических уравнений (СЛАУ) AU = f ( A – РМ), т.е. пытаться оптимизировать процесс решения с точки зрения затрат машинной памяти и времени.

Возможности решения этой задачи связаны с игнорированием нулей матрицы A за счет того, что:

1) арифметитические операции с нулями не производятся;

2) нули не обязательно хранить в машинной памяти.

§2. Способы хранения и представления разреженных матриц Все способы хранения РМ заключаются в том, чтобы хранить только ненулевые элементы матрицы или, может быть, небольшое количество нулей вместе с ними.

2.1. Разреженный строчный формат (РСФ) Это наиболее широко используемая форма хранения РМ. Пусть есть прямоугольная n m матрица ={aA }. Для ее представления в РСФ ij нужно три одномерных массива:

1) AN – массив ненулевых элементов матрицы A;

2) JA – массив соответствующих столбцовых индексов ненулевых элемен- тов матрицы A;

3) IA – так называемый “массив указателей ” – целочисленный массив, i -я компонента которого указывает, c какой позиции массивов AN и JA начинается описание i -й строки матрицы A. Здесь предусмотрена дополнительная компонента, которая является последней и указывает номер первой свободной позиции в массивах AN и JA.

- 4 - Таким образом, описание i -й строки матрицы A хранится в позициях с I A(i) до [I A(i +1) -1] массивов AN и JA за исключением равенства I I A(i +1) = I A(i), означающего, что i -я строка пуста. Следовательно, элементы записываются в массив по порядкуследования строк. Если A имеет m строк, то массив I A содержит (m +1) позицию.

Данный способ представления называют полным, т.к. представлена вся матрица A.

В зависимости от того, как записываются в каждой строке столбцовые индексы в массиве JA (по порядку возрастания или нет), различают упорядоченное или неупорядоченное представление соответственно.

Неупорядоченные представления нужны для алгоритмических удобств:

результаты большинства матричных операций получаются неупорядоченными, и упорядочение их требует дополнительных затрат машинного времени, в то время как большинство алгоритмов для РМ не требует, чтобы представления были упорядоченными.

З а м е ч а н и е. Всюду в дальнейшем мы будем иметь дело с вещественными матрицами.

Задача 1. Написать для матрицы A упорядоченное представление в РСФ.

N столбцов : 21 3 4 5 6 11 0 2 0 04 5 0 0.

A = 00 0 0 3 6 00 0 0 0 N позиций: 21 3 4 5 6 7 AN : 1 1 2 4 5 3 JA : 1 2 4 1 3 5 I A : 1 4 6 8 З а м е ч а н и е. В первой позиции массива I A всегда стоит 1.

Задача 2. По массивам AN, JA, IA восстановить матрицу A (с точностью до нулевых столбцов справа).

AN : 1 2 3 4 5 8 JA : 6 7 1 2 3 4 I A : 1 3 5 6 - 5 - Разобьем массивы AN, JA по строкам:

N позиции: 1 2 3 4 5 6 AN : 1 2 3 4 5 8 JA 6: 7 1 2 3 4 Таким образом, в матрице A 4 строки и 7 столбцов, причем в 1-ой строке в 6 столбце стоит 1, в 7-м столбце – 2 и т.д.

N столбцов : 21 3 4 5 6 000 0 0 1 43 0 0 0 0 A = 00 5 0 0 0 000 8 9 0 Задача 3. Написать для матрицы из задачи 1 полное, но неупорядоченное представление.

2.2. Разреженный столбцовый формат (РСтФ) Здесь элементы хранятся не по строчкам, как в РСФ, а по столбцам.

Столбцовые представления могут также рассматриваться и как строчные представления транспонированных матриц. Таким образом, в массиве JAT указывается строчный индекс соответствующего элемента, а элементы I AT указывают, с какой позиции начинается описание очередного столбца матрицы A.

Задача 4. Написать для матрицы A из задачи 1 упорядоченное столбцовое представление.

a) N позиций: 21 3 4 5 6 7 ANT : 41 1 5 2 3 JAT : 21 1 2 1 3 I AT : 31 4 5 6 7 Задача 5. Транспонировать матрицу A из задачи 1 и написать для нее упорядоченный РСФ, сравнить результат с результатом задачи 5.

Задача 6. Записать матрицу A в неупорядоченном РСтФ.

100 3 0 00 5 0 A = 000 0 000 0 00.

000 0 1070 0 - 6 - 2.3. Строчный разреженный формат хранения симметричных матриц n Для симметричной матрицы = {aA } = aaij ji )( достаточно ij ji =1, хранить лишь ее диагональ и верхний (нижний) треугольник. При этом можно указать два способа хранения:



1) строчное представление диагонали и верхнего (нижнего) треугольника (РСФБД);

2) выделение диагональных элементов матрицы A в отдельный массив AD, а разреженным форматом представляется только верхний (нижний) треугольник матрицы A (причем в этом представлении диагональ считается нулевой) (РСФД).

Задача 7. Записать симметричную матрицу 02 0 10 0 A = 00 3 11 0 a) в РСФБД;

б) в РСФД.

a) AN : 12 1 1 3 3 б) AN : JA : 41 2 4 3 4 JA : 4 I A : 31 5 6 7 IA : 1 2 3 3 AD : 2 1 3 2.4. Диагональная схема хранения (ДСХ) ленточных матриц n О п р е д е л е н и е 2.1. Квадратная матрица ={aA } называется ij ji =1, (2m +1)–диагональной или ленточной, если aij = 0 для всех i, j таких, что | i - j |> m. Число (2m +1) – это ширина ленты, m – полуширина.

Если m<< n, то такую матрицу следует рассматривать как разреженную.

Для хранения (2m +1)–диагональной несимметричной матрицы выделяется двумерный массив AD (n (m +1)), а для симметричной – (n (m +1)). Столбцами этого массива являются ненулевые диагонали матрицы A, которые хранятся, начинаяс самой левой диагонали (самый левый столбец) и кончаясамой правой (самый правый столбец) следующим образом:

- 7 - сначала в столбец записывается главная диагональ, нижние кодиагонали – в остальных концах слева со сдвигом на одну позицию вниз при каждом смещение влево, а верхние кодиагонали – в правой части массива со сдвигом на одну позицию вверх при каждом смещении вправо. Схематично это можно изобразить так:

У симметричных матриц, как правило, записывают нижний треугольник.

Задача 8. Для квадратной матрицы A 1) найти полуширину ленты m;

2) указать размеры матрицы AD;

3) построить ДСХ.

001 0 0 0 820 6 0 0 0 0101 80 3 0 0 0 0 20 0 a) A = 90 0 4 10 0 0 ; б) A = 01 0 0 2.

00 0 10 5 11 12 00 0 3 00 0 0 9 6 0 00 00 0 0 0 0 а) 1) m = 2; б) 1) m = 2;

2) AD(75); 2) AD(53) ;

01 820 6 80 3 0 0 3) AD = 09 4 10 0 3) AD = 01.

;

100 5 11 12 00 90 6 0 00 Задача 9. Указать взаимно - однозначное соответствие между положением элемента в матрице A и его положением в массиве AD.

- 8 - 2.5. Профильная схема хранения (ПСХ) ленточных матриц Эта схема предназначена для хранения симметричных ленточных матриц, когда внутри ленты находится слишком много нулей, и предыдущая схема становится нецелесообразной. Здесь хранится только нижняя полулента.

Введем числа = - ji i)(, где i – номер строки, ij )( – i min min минимальный столбцовый индекс первого ненулевого элемента в i -й строке матрицы A, т.е. первый ненулевой элемент i -й строки находится на i позиций левее правой диагонали.

n О п р е д е л е н и е 2.2. Профилем матрицы = {aA } называется ij ji =1, n сумма : pr A)( profile(A) ==.

i i i= О п р е д е л е н и е 2.3. Оболочкой матрицы A называется совокупность элементов { 0: < iaij - j }.

i Все элементы оболочки и диагональные элементы, упорядоченные по строкам, хранятся в одномерном массиве AN, причем диагональный элемент данной строки помещается в ее конец.

dim AN = pr(A) + n.

В целочисленном массиве DA указываются номера диагональных элементов в массиве AN.

Таким образом, при i > 1 элементы i -й строки находятся в позициях от [DA(i -1) +1] до DA(i). Единственный элемент a11 первой строки хранится в AN(1).

Задача 10. Для матрицы A = 00 10 0 2000 1) подсчитать профиль, найти размерность массива AN ;

2) построить ПСХ.

N позиции: 1 2 3 4 5 6 7 AN : 10 13 17 1 0 18 2 DA : 1 2 3 6 - 9 - )1 = 0, = 0, = 0, = 2, = 1, 21 3 4 pr A)( 3, dim AN == 3 + 5 = 8.

Задача 11. По массивам AN и DA восстановить матрицу A:

AN : 9 8 7 6 5 4 3 2 DA : 1 3 5 6 7 § 3. Операции над РМ. Алгебра РМ Оперировать с РМ труднее, т.к. они заданы в упакованной форме. Мы будем работать с матрицами, которые заданы в РСФ (РСтФ). Поэтому любой алгоритм разбивается на два этапа.

1. Символический – определяется структура разреженности результата, который хотим получить, а также позиции элементов исходных РМ, с которыми нужно проводить арифметические действия, т.е. идет работа с векторами IA, JA; здесь же определяется объем оперативной памяти, необходимый для хранения промежуточных результатов и выходной информации.

2. Численный – непосредственно выполняются численные операции. В результате получаем число, матрицу или вектор.

3.1. Списки 3.1.1. Хранение списков, целых списков, кольцевых целых списков О п р е д е л е н и е 3.1. Списком называется совокупность ячеек (позиций), связанных в том или ином порядке. Каждая ячейка содержит элемент списка и номер ячейки, в которой хранится следующий элемент списка.

Внутри каждого списка, по предположению, повторений нет.

В общем случае схема хранения списка состоит из трех массивов:

1) массив позиций N ;

2) массив элементов A;

3) массив NEXT – указатель позиций следующих элементов, и добавляется указатель начала списка IP.

Задача 12. Написать схему хранения чисел a, b, c, d в указанном порядке, если они хранятся в массиве A следующим образом:

N : 1 2 3 4 5 6 A : b d a c Ответ: NEXT : 7 2 4 ; IP = 5.

Задача 13. В каком порядке должны храниться числа a, b, c, d, e, f, если схема хранения выглядит следующим образом:





N : 1 2 3 4 5 - 10 - A : a b c d e f NEXT : 6 5 3 2 IP = Ответ: d, c, e, b, f, a.

О п р е д е л е н и е 3.2. Если элементы списка являются целыми числами, то такой список называется целым.

Пусть есть некоторый целый список A, элементы которого могут принимать значения {,1 2,..., n }.

О п р е д е л е н и е 3.3. Число n – максимальное значение элементов в списке – называется размахом списка.

Пусть m – число элементов списка. Если m << n, то список называется разреженным целым списком (РЦС). Примерами таких списков могут служить массивы JA, I A. Целый список можно хранить с помощью одномерного массива длины n (скажем, JA) и указателя начала входа IP.

Задача 14. Записать целый список 3, 8, 4, 2 в компактной форме.

N позиций : 1 2 3 4 5 6 7 JA : 3 8 2 IP = 3.

Число, хранимое в каждой позиции JA, дает одновременно значение элемента списка и адрес следующего элемента; таким образом, массив NEXT уже не нужен.

Список называется кольцевым, если в его последнюю позицию поместить указатель на начальную позицию. У кольцевого списка нет ни начала, ни конца, но он требует хранимого отдельно указателя входа, который указывает на любую занятую позицию. Благодаря этому можно хранить несколько непересекающихся списков (кольцевых или нет) в одномерном массиве длины n, равной максимальному размаху списков, с использованием указателя входа IP.

Задача 15. Для непересекающихся списков AA,, A3 написать схему хранения в одном массиве.

A1 2:, 8, 6, 3; A2 5:, 4, 0; A3 7:, 1, N позиций: 1 2 3 4 5 6 7 8 9 JA : 10 8 2 9 4 3 1 6 5 IP : 2 5 3.1.2. Cлияние РЦС Пусть заданы РЦС AA,,..., An. Результатом их слияния является - 11 - список B, который содержит все элементы списков iA = 1(,...,n ) без i повторений (внутри каждого списка повторений нет).

Задача 16. Слить три списка А, B, С в один список М, где А 2:, 7, 3, 5; B : 3, 11, 5; С : 7, 2.

Список А записываем в М полностью, затем добавляем те элементы B, которых в А нет, потом элементы С, которых нет в А и B. Таким образом, получим следующий список М 2:, 7, 3, 5, 11.

Просматривать каждый раз список М, чтобы внести новый элемент, нерационально. Поэтому вводится массив переключателей Y и переключатель p. Обычно p =1.

Число позиций массива переключателей должно быть равно максимальному размаху сливаемых списков (в данной задаче 11). В начальный момент во все позиции Y засылаем нули. Далее просматриваем первый из сливаемых списков, и если очередной просматриваемый элемент равен i, то в i -ю позицию массива переключателей засылается значение переключателя (то есть 1). При просмотре каждого текущего элемента следующего списка (пусть он равен j ) мы обращаемся к массиву переключателей и добавляем элемент j в список M только в том случае, когда соответствующая позиция ”не включена”, т.е. в позиции переключателя стоит ноль. Таким образом мы просматриваем все списки.

Для данной задачи массив переключателей будет следующим:

N позиции: 21 3 4 5 6 7 8 9 10 Y : 00 0 000000 00 в начальный момент 10 1 0 1 0 1 0 0 00 после просмотра A 10 1 0 1 0 1 0 0 0 1 после просмотра B 10 1 0 1 0 1 0 0 0 1 после просмотра C 3.1.3. Метод переменного переключателя (ПП) При обработке РМ приходится сливать несколько групп списков. В целях экономии памяти используется только один массив переключателей (ЦМП), число позиций которого равно порядку матрицы (или числу строк, или числу столбцов).

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

Сначала p =1. Затем после каждого слияния группы списков p увеличивается на единицу (т.е. p = p + 1), что избавляет от необходимости засылки нулей во все позиции ПП.

- 12 - Задача 17. Слить три списка А, B, С в М1 и два списка D, E в М2, используя ПП p.

A 11:, 12, B 4:, 5, 11 ; 6:, 7, 8, 9 MD : 11, 12, 13, 4, 5, 7, 8 ( p =1);

C 7:, 8, E 7:, 8, 4 М2 : 6, 7, 8, 9, 1, 2 ( p = 2).

N позиции: 1 2 3 4 5 6 7 8 9 10 11 12 Y: 00 0 01 01 2 00 00 0 01 01 22 1 122 3.2. Сложение разреженных векторов (РВ) 3.2.1. Метод расширенного вещественного накопителя (РВН) На входе даны векторы А, B в РСФ, на выходе должны получить вектор C = А+ B в том же формате.

Алгоритм 1. Символический этап: определяются позиции ненулевых элементов С путем слияния списков JА, JB в JС.

2. Численный этап 10. Вводится РВН X, число позиций которого равно размаху списка JС. Во все позиции вектора X с номерами из JC засылаем нули.

20. Просматриваем JА и AN и прибавляем к содержимому позиций вектора X содержимое соответствующих позиций AN. Затем прибав- ляем BN к X.

30. Выбираем из X нужные числа, чтобы сформировать CN, с помощью JС : CN (i) = X ( JC(i) ) и записываем их в соответствующие столбцы.

Задача 18. Сложить векторы А, B методом РВН.

AN 0: 2. 0.3 0 4. - 0.7 BN 0: 6. 0 7. 0 5.

;.

JA 10: 3 7 4 JB 5: 4 1. Сливаем списки JА, JB в JС : 10 3 7 4 5.

2. Вводим РВН X :

N позиции: 1 2 3 4 5 6 7 8 9 X : 0 0 0 0 0 в начальный момент 0.3 - 0.7 0.4 0.2 прибавили AN 7.0 0 6. 0 5. прибавили BN 0.3 0 0.6 0.4 0.CN : 0.7 0.3 0.4 0 0.- 13 - З а м е ч а н и е. Если мы не хотим, чтобы в CN были записаны нули, нужно “выбросить” нулевой элемент и соответствующий ему столбец. Тогда для данной задачи вектор C будет следующим:

CN : 0.7 0.3 0.4 0..

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.