18528

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

Доклад

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

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

Русский

2013-07-08

79.5 KB

47 чел.

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

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

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

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

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

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

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

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

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

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

 


 

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

46315. Особенности проектирования приспособлений для станков-автоматов, агрегатных станков и автоматических линий, состоящих из этих станков 58 KB
  Особенности проектирования приспособлений для станковавтоматов агрегатных станков и автоматических линий состоящих из этих станков При полной автоматизации цикла обработки необходима автоматизация приспособления. Требования к автоматическим приспособлениям: особое внимание должно быть обращено на удаление стружки.1 приведена схема пневматического приспособления для сверления отверстия в цилиндрических заготовках с подачей их из магазина. На автоматических линиях применяют два типа приспособлений: стационарные и приспособления – спутники.
46316. Особенности проектирования приспособлений для станков с ЧПУ, обрабатывающих центров и гибких производственных систем 128 KB
  Особенности проектирования приспособлений для станков с ЧПУ обрабатывающих центров и гибких производственных систем К станочным приспособлениям применяемых на станках с ЧПУ предъявляются следующие требования: а высокая точность и жесткость обеспечивающая требуемую точность обработки и максимальное использование мощности станка; б полное базирование как заготовки так и приспособления относительно начала координат станка; в возможность подхода инструмента ко всем обрабатываемым поверхностям; г возможность смены заготовки вне рабочей...
46317. Прочность деталей приспособлений 84.5 KB
  Прочность деталей приспособлений Прочность одно из основных требований предъявляемых к деталям и приспособлениям в целом. Прочность деталей может рассматриваться по коэффициентам запаса или по номинальным допускаемым напряжениям. С помощью расчета деталей элементов приспособлений на прочность можно решать две задачи: а проверку на прочность уже существующих деталей с определенными размерами сечений путем сравнения фактических напряжений моментов сил с допускаемыми проверочный расчет; б определение размеров сечений деталей ...
46318. Экономическая эффективность приспособлений 85.5 KB
  Процессы проектирования станочных приспособлений представляют собой одну из разновидностей информационных процессов, имеющих место в машиностроительном производстве. Они в разной степени проявляются при разработке универсальных, универсально-переналаживаемых и специальных приспособлений
46319. Разработка схемы базирования заготовки. Выбор установочных элементов 199.5 KB
  Анализ исходных данных и формулирование служебного назначения приспособления В качестве исходных данных конструктор приспособления должен иметь: чертеж заготовки и детали с техническими требованиями их приемки; операционные чертежи на предшествующую и выполняемую операции; операционные карты технологического процесса обработки данной детали. Служебное назначение приспособления – это максимально уточненная и четко сформулированная задача для решения которой оно предназначено. Классификация технологической оснастки По целевому назначению...
46320. Расчет точности базирования заготовок деталей 94 KB
  Погрешность базирования при установке вала на призму Рис. Схема для определения погрешностей базирования при установки вала уста на призму. При обработке вала в призме могут быть могут быть следующие измерительные базы для размера h. Измерительные базы при обработке вала в призме.
46321. Зажимные элементы приспособлений 224.5 KB
  При обработке партии таких деталей требуется получить высокую концентричность наружных и внутренних поверхностей и заданную перпендикулярность торцов к оси детали. При зажиме обрабатываемой детали на оправке осевая сила Q на штоке механизированного привода вызывает между торцами шайбы 4 уступом оправки и обрабатываемой деталью 3 момент от силы трения больший чем момент Мрез от силы резания Рz. Где: коэффициент запаса; Рz вертикальная составляющая сила резания Н кгс; D наружный диаметр поверхности обрабатываемой детали мм; D1 ...
46322. Разработка компоновки приспособления 117.5 KB
  Разработка компоновки приспособления Разработку общего вида приспособления начинают с нанесения на лист контуров заготовки. В зависимости от сложности приспособления вычерчивают несколько проекций заготовки. Разработку общего вида ведут методом последовательного нанесения отдельных элементов приспособления вокруг контуров заготовки. Более этого вычерчивают корпус приспособления который объединяет все перечисленные выше элементы.
46323. Составление расчетной схемы и исходного управления для расчета зажимного усилия Рз 202 KB
  Составление расчетной схемы и исходного управления для расчета зажимного усилия Рз Закрепление заготовки производится с помощью зажимных устройств различных конструкций. Принцип действия и конструкцию зажимного устройства конструктор выбирает исходя из конкретных условий выполнения операций: типа производства величин сил резания действующих на заготовку при выполнении операций конструктивных особенностей заготовки типа станка. Выбор коэффициента трения f заготовки с опорными и зажимными элементами. Выбор коэффициента трения заготовки с...