18528

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

Доклад

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

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

Русский

2013-07-08

79.5 KB

50 чел.

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

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

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

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

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

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

Все ненулевые элементы  записываются построчно, а одномерном массиве А. Формируется два указательных массива 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 можно использовать одну ячейку. В таком случае можно также дополнить список адресами следующих ненулевых элементов столбца. Это уменьшит количество вспомогательных операций при решении системы.

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

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

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

 


 

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

43690. Совершенствование способов управления инвестиционными рисками компании на основе их всестороннего анализа и оценки ЗАО «Плитспичпром» 182.87 KB
  Теоретические аспекты оценки и управления инвестиционными рисками организации Методы оценки и управления инвестиционными рисками Разработка методов совершенствования системы оценивания и управления инвестиционными рисками предприятия Оптимизация управления инвестиционными рисками предприятия
43691. Автоматизированная система управления деятельностью туристического агентства «Коми-тур» 8.92 MB
  Туристическое агентство «Коми-тур» оказывает услуги населению по подготовке и организации отдыха. Основные услуги – это услуги по подбору наиболее оптимальных для туриста туров (экскурсии, отдых на море, активный туризм, отдых с детьми, паломнический туризм), бронирование выбранного тура у туроператора, оформление документов, услуги по организации встречи и проводов туристов.
43692. Анализ индивидуальных трудовых споров и выявление проблем, возникающих при рассмотрении их в суде 174 KB
  Значительно возросло количество трудовых дел в судах. Появились новые очень сложные дела: о взыскании морального вреда, причиненного работнику незаконным увольнением, переводом на другую работу, невыплатой гарантированных законодательством выплат и льгот, отказом от заключения трудового договора и другие.
43693. Психологічні особливості соціального інтелекту та поведінки в конфлікті в юнацькому віці 197.84 KB
  Однакзведення інтелекту до миследіятельності вириває його з контексту соціалізації що припускає вироблення власних ціннісних орієнтацій свого стилю життя. У сучасній школіяка орієнтована на розвиток теоретичного інтелекту як відзначає М. Подальша розробка категорії соціального інтелекту визначається результатами досліджень Г. Холодної які виявили взаємозв'язок інтелекту людини і здатності реалістично оцінювати себе регулювати свою поведінку; дослідженнями К.
43694. Проектирование АСУ ОАО «ГСК «Югория» и разработка конкретных проектных решений по одной из подсистем АСУ 271.67 KB
  Процесс создания АСУ – это последовательное внедрение более совершенных, научно-обоснованных методов управления и средств вычислительной техники с целью увеличения эффективности производства и повышения производительности труда. Экономико-математические методы оптимального планирования и управления, средства автоматизированной обработки больших объемов информации становятся неотъемлемой частью структур управления, способом их функционирования.
43695. Разработка рекомендаций по совершенствованию конкурентоспособности ООО «НЗЖБИ имени Иванова Г.С.» на рынке 318.92 KB
  Организационно-экономическая характеристика предприятия Изучение конкурентоспособности предприятия представляет собой одну из важнейших составных частей рыночных исследований создающих основу для выработки стратегии и тактики деятельности на рынке выбора правильного пути повышения технического уровня и качеств. Именно по этой причине большую актуальность приобретают исследования в области конкурентоспособности предприятия поиск путей её повышения. разработать рекомендации по совершенствованию конкурентоспособности предприятия на...
43696. Таймер керування водяним насосом 233.02 KB
  Розрахунок ЗІП повинен проводитись по встановленим нормам.1 Логічний розрахунок JKтригера. Необхідно виконати розрахунок jk тригера.2Конструктивний розрахунок таймеру керування водяним насосом 5.
43697. Внутрисхемное программирование 288.79 KB
  Программатор, использующий интерфейс SPI, необходимо подключить к объекту, используя как можно меньшее количество проводов. Для подключения программатора микроконтроллеров AVR непосредственно к печатной плате используется шестипроводной интерфейс.
43698. Разработка методических рекомендаций и практических предложений по совершенствованию направлений деятельности коммерческих банков с ценными бумагами 208.69 KB
  Возникают совершенно новые оригинальные виды банковских операций и услуг связанных с новыми типами финансовых инструментов выраженных в форме различных ценных бумаг. Активное участие коммерческих банков на рынке ценных бумаг во многом меняет содержание их операций придает их деятельности более выраженный рыночный характер. С помощью операций с ценными бумагами коммерческие банки могут направлять инвестиции в производство в торговый оборот а также финансировать государственные расходы. Во многих регионах России особенно депрессивных...