18528

Способы хранения разреженных матриц

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-07-08

79.5 KB

56 чел.

Способы хранения разреженных матриц

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

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

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

Рассмотрим некоторые способы упакованного хранения разреженных матриц.

Первый способ.

Все ненулевые элементы  записываются построчно, а одномерном массиве А. Формируется два указательных массива LJ и LI. В массив LJ записываются номера столбцов ненулевые элементов  в том же порядке, в каком элементы  записаны в массиве А. В массив LI записываются относительные адреса в массиве А первых ненулевых элементов каждой стоки. Длина массивов А и LJ равна общему количеству ненулевых элементов матрицы, длина массива LI равна N. Для матрицы

 

массивы А, LJ и LI имеют вид

LJ =  1   2   1   2   4   3   4   2   3   4  5  4   5

                                           LI =  1   3   6   8   12 .

Второй способ.

Использование однородного координатного базиса при формировании уравнений схемы приводит к тому, что матрица А оказывается структурно-симметричной, т.е. если , то и . В этом случае удобно применять следующую схему хранения.

Диагональные элементы  записываются в массив AD, ненулевые элементы  (j>i) – по строкам в массив AU, а ненулевые элементы (i>j) – по столбцам в массив AL.

Организуются два указательных массива LJ и LI. В массив LJ записываются номера столбцов (строк) элементов из массива AU (AL), а в массив LI – относительные адреса первых в строке (столбце) ненулевых элементов из массива AU (AL).  Для матрицы

                                                           

                                                           

                                                            LJ = 2 4 4 5

                                                            LI = 1 2 3 4

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

Третий способ.

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

Поставим в соответствие каждому ненулевому элементу  два числа: номер столбца j и относительный адрес k в массиве А следующего ненулевого элемента i-й строки. Если элемент  - последний в строке, то k = 0. Порядок расположения в памяти записей (, j, k) несуществен. Обозначим LJ и KM массивы, в которых записываются числа j и k соответственно. Тогда для матрицы

заполнение массивов имеет следующий вид:

Если необходимо ввести новый ненулевой элемент, например , достаточно к массивам A, LJ и KM добавить запись , а в 8–й ячейке массива KM заменить 0 на 14. кроме удобства введения ННЭ, этот способ не имеет других преимуществ перед выше рассмотренными. Наоборот, применение связных списков увеличивает затраты памяти и несколько усложняет поиск элементов.

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

С точки зрения быстродействия эффективность программы будем характеризовать величиной   где и  - время выполнения основных и вспомогательных операций.

Экономичность алгоритма с точки зрения затрат оперативной памяти будем оценивать величиной  где  - количество ненулевых элементов в матрице с учетом появления ННЭ;  - количество ячеек, необходимых для хранения указательных массивов и команд программы решения.

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

 


 

А также другие работы, которые могут Вас заинтересовать

81825. Базисные ценности современной цивилизации. Ценность научной рациональности 33.22 KB
  Ценности не сводятся только к моральноэтическим императивам. Ценности способствуют усилению мотивации поступков и действий человека они связаны с глубинными переживаниями значимости своей деятельности и поэтому ценностные установки накладывают свой отпечаток на процесс научного творчества. Важно подчеркнуть что ценности могут играть как позитивную так и негативную роль.
81826. Многообразие форм знания. Научное и вненаучное знание 36.77 KB
  Появление научного знания не отменило и не упразднило не сделало бесполезными другие формы знания. Шестова о том что повидимому существуют и всегда существовали ненаучные приемы отыскания истины которые и приводили если не к самому познанию то к его преддверию но мы так опорочили их современными методологиями что не смеем и думать о них серьезно Каждой форме общественного сознания: науке философии мифологии политике религии и т. соответствуют специфические формы знания.
81827. Особенности научного познания 32.52 KB
  Если этого нет то нет и науки ибо само понятие научности предполагает открытие заходов углубление в сущность изучаемых явлений. Это основной признак науки главная ее особенность. Нацеленность науки на изучение не только объектов преобразуемых в сегодняшней практике но и тех которые могут стать предметом практического освоения в будущем является важной отличительной чертой научного познания.
81828. Особенности транспортного обслуживания города 24.19 KB
  Различают города районного областного краевого и республиканского подчинения. Городской и пригородный транспорт представляет собой транспортную систему которая объединяет различные виды транспорта осуществляющие перевозку населения и грузов на территории города и ближайшей пригородной зоны а также выполняющие работы по благоустройству города. В транспортную систему города входит также велосипед для которого в цивилизованных странах выделяется отдельная специализированная велосипедная дорожка.
81829. Методы расчета пропускной способности на различных видах транспорта 33.61 KB
  Методы определения пропускной способности пресечений и линий слияния автомобильных потоков Пересечения автомобильных дорог являются одним из участков на которых сосредотачиваются дорожнотранспортные происшествия значительно уменьшается пропускная способность наблюдается снижение скорости а зачастую и полная остановка движения автомобильного транспорта заторы. Большинство узлов в одном уровне имеют меньшую пропускную способность чем подходящие к нему дороги вследствие наличия на узле опасных точек задержки автомобилей перед...
81830. Технико-эксплуатационные характеристики судов 27.65 KB
  Технико-эксплуатационные характеристики судов (ТЭХ) - это степень пригодности судов к транспортировке определенных видов грузов, т.е. конструктивные особенности и грузовые характеристики судна, отвечающие транспортным характеристикам и свойствам грузов
81831. Транспортная схема города 28.55 KB
  Комплексная транспортная схема сеть это линии городского маршрутизированного пассажирского транспорта по которым организовано движение массового общественного транспорта. Применение различных видов транспорта в транспортной сети определяется экологией безопасностью провозными возможностями наименьшими затратами времени сообщения а также комфортабельностью и регулярностью перевозок. Основные зоны города места тяготения нуждающиеся во взаимной транспортной связи это жилые кварталы общегородской центр места массового отдыха и...
81832. Скорость и сроки доставки грузов 21.8 KB
  Сроки доставки грузов а также порожних вагонов принадлежащих грузоотправителю грузополучателю или арендованных ими исчисляются на железнодорожной станции отправления исходя из расстояния по которому рассчитывается провозная плата с учетом железнодорожных направлений по которым осуществляются перевозки грузов. Неполные сутки при исчислении сроков доставки грузов считаются за полные. Перечень железнодорожных направлений по которым осуществляются перевозки грузов большой скоростью публикуется в Сборнике правил перевозок и тарифов на...
81833. Формы взаимодействия и конкуренции различных видов транспорта 26.94 KB
  Однако специфика каждого из видов транспорта их технические и технологические особенности заранее предопределяют области их использования на транспортном рынке что несколько ограничивает возможность конкуренции и способствует взаимодействию видов транспорта. Более эффективно и выгодно для потребителей взаимодействие автомобильного транспорта с железнодорожным в начальных и конечных пунктах его протяженных маршрутов. Учитывая недостаточную развитость автодорожной сети в России и технического сервиса конкуренция между этими видами транспорта...