18528

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

Доклад

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

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

Русский

2013-07-08

79.5 KB

55 чел.

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

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

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

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

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

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

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

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

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

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

 


 

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

52847. Нові технології. Написання електронних листів 75 KB
  Look at the words on the screen and guess what part of speech they are and what theme they concern. Use, upgrade, zoom, erase, paste, plug, unzip, view, scroll, print, touch. You are right. They are all verbs and they deal with a computer, new technologies, as well as new means of communications So, today we are going to speak about new technologies and e-mails as the form of the new kind of writing.
52849. Запліднення. Ембріональний розвиток людини. Регуляція народжуваності 86.5 KB
  Регуляція народжуваності 9 клас Завдання уроку: навчальні: − активізувати основні проблеми теми; − дати поняття про онтогенез та його етапи; − засвоїти знання щодо процесу запліднення ембріогенезу сучасні методи контрацепції; розвивальні: − розвиток операції логічного мислення; − удосконалення уміння працювати...
52850. Емоції. Емоційні реакції та стани 1.79 MB
  Мета: освітня: розглянути поняття про емоції які особливості вищої н. людини з'ясувати значення емоцій у житті людини виявити різницю між поняттями €œемоційна реакція €œемоційний стан†і €œемоційні відносини; розвивальна: продовжити формування навичок роботи з книгою аналізу порівняння узагальнення самооцінки; виховна: продовжити формування уміння слухати і чути співрозмовника учити колективному співробітництву. Ушинський Сьогодні на уроці потрібно розглянути поняття про емоції як особливості вищої...
52851. Розвиток емоційного інтелекту школярів на уроках української літератури 52.5 KB
  Емоційний інтелект опинився у центрі уваги вчених в останні десять років. Проте як не парадоксально це звучить останнім часом було відкрито що в розвитку гармонійної особистості людини емоційна компетентність емоційний інтелект відіграє важливішу роль ніж академічна. Емоційний центр мозку безпосередньо повязаний із системою довготривалої памяті.
52852. eMule. Полное описание 231.5 KB
  Своей целью я поставил написать наиболее полное руководство по программе eMule при этом не вдаваясь в технические подробности с одной стороны и с другой стороны объясняя не только назначение отдельных кнопочек но и рассказывая про принципы работы как самого eMule так и функционирования сети в частности. Почему именно eMule а не чтото другое Здесь есть целый ряд причин. Самое главное: eMule это наиболее функциональный P2Pклиент к тому же его использует подавляющее большинство пользователей. Вот статистика собранная моим Мулом за 18...
52853. Збереження електроенергії у побуті 49 KB
  Мета: Поширити уявлення дітей про способи добування електроенергії. В домі дід мороз живе І продукти зберігає А щоб свіжими були Зіпсуватись не могли Їх у холоді тримає Холодильник Коментарі вчителя щодо збереження електроенергії. Своєчасно розморожувати щоб менше споживав електроенергії.
52854. Енергозбереження - працюємо разом 115.5 KB
  Мета: Навчати оцінювати запаси енергетичних ресурсів формувати переконаність у можливості раціонального використання природних ресурсів; навчати оцінювати побутові втрати енергії; підвести до висновку про можливість раціонального використання енергії; переконати учнів у необхідності пошуків засобів збереження енергії. Наші споживання в електроенергії змінюються в часі : доба тиждень рік. Доба Наші споживання в енергії змінюються на протязі доби частково від того в яких умовах ми живемо і частково від нашої роботи мал.1 З малюнок 1...
52855. Енергозбереження – почнемо з себе 83.5 KB
  Розширення індивідуального екологічного простору розвиток емпатії до природних об'єктів; Форма заняття: заняття студії Заняття розраховане на учнів 910 класу Обладнання: таблиці з зображенням будови атмосфери компютер підключений до мережі Інтернет свічка лампа розжарювання лампа енергозберігаюча лампа 20 21 Вт; лампа розжарювання 100 Вт; настільна лампа зі стандартним цоколем; кімнатний термометр; годинник кольорові стікери з зображенням пір року. Мета етапу сфокусувати увагу учнів на проблемі й викликати інтерес до...