Разреженность матрицы

Учет разреженности матриц — направление экономичной организации операций над разреженными матрицами. Матрицу называют разреженной, если в ней преобладают нулевые элементы. Отказ от хранения нулевых элементов и реализация алгоритмов, в которых игнорируются арифметические действия над нулевыми элементами, могут дать значительную экономию 7 и Я . [c.225]

Методы разреженных матриц. Если выполнять вычисления, пользуясь (5.4), для всех элементов матрицы коэффициентов, то экономичность метода Гаусса характеризуется кубической зависимостью затрат машинного времени Т от порядка системы уравнений п. Это приводит к ограничению области целесообразного применения метода Гаусса значениями п в несколько десятков. Однако во многих практических задачах п имеет порядок сотен или тысяч. Применение метода Гаусса к таким задачам оказывается эффективным, если учитывать свойство разреженности матрицы коэффициентов в системе решаемых уравнений (5.3). [c.230]

Следует различать исходную и итоговую разреженность матрицы. Исходная разреженность определяется числом ненулевых элементов, имеющихся в матрице до начала выполнения исключений неизвестных по методу Гаусса, Такие нулевые элементы называют первичными. Однако в процессе вычислений по (5.4) некоторые коэффициенты Uij, бывшие нулевыми, могут стать ненулевыми. Такие коэффициенты называют вторичными ненулевыми элементами. Итоговая разреженность определяется суммарным числом первичных и вторичных ненулевых элементов, и эффективность учета разреженности матрицы тем выше, чем больше итоговая разреженность. [c.230]

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

Алгоритмы метода прогонки в отличие от более общих алгоритмов учета разреженности матриц с нерегулярной структурой характеризуются большей простотой программной реализации. [c.232]

Можно ли применять метод прогонки к решению системы уравнений (4.52) Одинаковы или нет исходная и итоговая разреженности матрицы Якоби в этой системе [c.260]

Дело в том, что матрица коэффициентов системы линейных алгебраических уравнений, к которой приводит МКЭ,— сильно разреженная матрица ленточной структуры. Ненулевые элементы такой матрицы располагаются параллельно главной диагонали (рис. 1.4). Целое число/., представляющее собой наибольшую разность между номерами ненулевых элементов в строке, называется шириной полосы. Чем меньше ширина полосы, тем меньший объем ОП требуется для хранения матрицы при реализации МКЭ в САПР и тем меньше затраты машинного времени на решение результирующей системы уравнений. Ширина полосы зависит, в свою очередь, от числа степеней свободы узлов и способа нумерации последних. [c.18]

Примечание. Основные особенности этого шага — большая ра )мерность и сильная разреженность матрицы коэффициентов системы. В связи с этим для реализации МКЭ в САПР разработаны специальные способы хранения матрицы жесткости, позволяющие уменьшить необходимый для этого объем ОП. Для нахождения узловых значений функций применяются методы преобразования и решения системы, направленные на снижение затрат машинного времени. [c.39]

Матрицы, содержащие нулевые элементы, называются разреженными матрицами. Матрицы инциденций являются сильно разреженными, причем разреженность возрастает с увеличением их размера. [c.111]

Представление компонентных уравнений в форме (3.6) удобно для формирования матрицы Якоби. Матрица Якоби, получаемая при использовании табличного метода, сильно разреженная. Чем меньше число ненулевых элементов в матрице, тем выше экономичность модели, поэтому следует стремиться получить максимальную разреженность матрицы. [c.124]

Примечание. Одно- и двухмерные массивы позволяют непосредственно отобразить в ЭВМ векторы и матрицы. Однако представление больших разреженных матриц в виде двухмерных массивов влечет за собой неоправданные потери памяти и ма- [c.9]

Рис. 1.6. Разреженная матрица (а) и ее представление в виде списка (б).

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

Примечание. Пример же более высокого быстродействия скомпилированных процедур с прямым доступом к данным приведен выше (прямой ход алгоритма Гаусса при решении системы линейных алгебраических уравнений с сильно разреженной матрицей коэффициентов). [c.136]

Метод сеток позволяет свести решение систем уравнений в частных производных к решению систем алгебраических уравнений, как правило линейных, с достаточно разреженными матрицами. При этом построение решения в методе сеток осуществляют в три этапа. [c.74]

В большинстве задач система алгебраических уравнений, возникающих при аппроксимации дифференциальных уравнений разностными, имеет очень большой порядок (как правило, iV lOO), но обладает разреженной матрицей. В случае нелинейных систем итерационные процедуры, как правило, сводят к линейным системам. [c.74]

Здесь в правую часть помимо T j входит и вектор Tj 2- Поэтому для применения трехслойной схемы необходимо предварительно на первом интервале времени воспользоваться одной из двухслойных схем. Применение трехслойной схемы на каждом из последующих интервалов времени заставляет 1 раз обращать недиагональную, но сильно разреженную матрицу — С - [c.47]

Рис. 1.25. Пример хранения разреженных матриц

Вся информация о матрице хранится в пяти одномерных массивах Ш, MS, MV, АТ, MN. Массив IM служит для организации хранения нескольких разреженных матриц. Индекс массива IM (номер элемента массива) соответствует номеру матрицы. Элементами этого массива являются указатели (индексы массива MS) на расположение информации о данной матрице в массиве MS. В массиве MS на каждую матрицу отводится число элементов, равное числу столбцов, если матрица хранится по столбцам (или числу строк, если хранение — по строкам). Элементами этого массива являются указатели на номер записи, в которой хранится информация о первом ненулевом элементе данного столбца (строки). Запись представляет собой три элемента из массивов MV, АТ, MN с одинаковым индексом К — номером записи MV (К), АТ (К), MN (К). Для элемента матрицы a j запись имеет вид (С, йц, а), где i — номер строки а — номер записи следующего ненулевого элемента данного столбца (если а = О, то элемент является последним для данного столбца). [c.46]

Для реализации методов строительной механики, учитывая специфический способ хранения матриц, необходимо реализовать следующие процедуры ввод матрицы в список удаление матрицы из списка транспонирование матрицы умножение двух матриц решение системы линейных алгебраических уравнений с разреженной матрицей. [c.47]

Теоретически точное решение получается за п или менее шагов, в зависимости от способа выбора и начального приближения. Практически (за счет ошибок округления) иногда требуется и больше, чем п шагов, поэтому вопрос об окончании процесса является не тривиальным. Для сокраш,ения числа итераций, необходимых для получения точного решения, может быть применено масштабирование, т. е. элементы столбцов и строк матрицы и соответственно правая часть преобразуются так, чтобы они были величинами одного порядка. Метод сопряженных градиентов с разреженной матрицей реализуется процедурой MSG. Обращение [c.50]

Высокая скорость расчета достигается за счет оптимальных алгоритмов и высокого качества основных программ. Программа решения системы уравнений написана на Ассемблере и максимально использует разреженность матрицы жесткости. Часто используемая программа перемножения матриц составлена на Ассемблере. При решении системы используется магнитная лента и там где возможно, используется совмещение обмена с вычислениями. При решении предусмотрены контрольные точки, что позволяет большую задачу решать поэтапно. [c.198]

При выполнении обратной подстановки обработка также ведется по столбцам, что позволяет использовать разреженность матрицы, т. е. вести вычисления с использованием массива функций N. Это дает повышение эффективности при большом количестве правых частей. [c.207]

Предложенные в данной работе итерационные методы позволяют хранить полностью заполненные матрицы жесткости каждого конечного элемента. Следовательно, применение известных методов и приемов работы с разреженными матрицами в данном случае нецелесообразно. Эти методы в отличие от многих других позволяют легко реализовать практически все необходимые варианты граничных условий. [c.43]

Преимущество этих методов состоит в простоте алгоритма, недостаток — в увеличении числа арифметических операций по крайней мере в 2 раза по сравнению с методами, при которых используются разреженные матрицы. Однако при работе с разреженными матрицами появляются дополнительные операции, связанные с организацией процесса обработки ненулевых элементов матрицы системы, а также усложняется структура программы. [c.43]

В рассматриваемом варианте МГЭ матрица коэффициентов А будет являться весьма разреженной матрицей общего вида. Решение системы уравнений с такой матрицей может быть осуществлено с помощью метода исключения Гаусса. Одной из особенностей матрицы является наличие [c.33]

МГЭ приводит к образованию хорошо обусловленных и сильно разреженных матриц коэффициентов А общего вида (не симметричных и не положительно определенных). [c.387]

Алгоритм вычисления матрицы Якоби в методе узловых потенциалов. Вычисление матрицы Якоби как матричного произведения AYA без учета разреженности матриц А и Y нерационально, так как приводит к излишне большим затратам машинных времени и памяти. Например, в схеме средней сложности, включающей р = 51 и а = 80, матрица А имеет размер 50X80, а матрица Y—размер 80 x 80, т. е. только эти две матрицы для хранения всех их элементов требуют около 10 000 ячеек памяти. В то же время статистические исследования показывают, что ненулевыми в этих матрицах оказываются лишь около 240 элементов. Поэтому на практике используют алгоритмы формирования матрицы Якоби, учитывающие сильную разреженность матриц А и Y. [c.178]

Разреженной называют ту матрицу, в которой преобладают элементы, равные нулю. Разреженность S оценивается отношением числа нулевых элементов к общему числу элементов матрицы. Анализ показывает, что в математических моделях большинства поректируемых объектов число ненулевых элементов пропорционально первой степени п. Поэтому если учитывать разреженность матрицы, то Тм можно сделать линейной функцией п и суш,ественно расширить пределы эффективного применения метода Гаусса. Учет разреженности при этом заключается в том, что арифметические действия по (5.4) не производят, если выполняется хотя бы одно из условий aik=0 или а = 0. [c.230]

Метод прогонки. Примерами сильно разреженных матриц являются матрицы Якоби в системах конечных уравнений, получаемых по методам конечных разностей или конечных элементов из дифференциальных уравнений в частных производных. Если алгебраизация дифференциального уравнения производится на основе регулярной сетки, то разреженная матрица Якоби оказывается ленточной, т. е. матрицей, у которой ненулевые элементы располагаются только на k главных диагоналях. Специфические особенности структуры ленточных матриц можно использовать для упрощения алгоритмов учета разреженности. [c.231]

Для метода Гаусса Я=1, и если не учитывать разреженность матрицы коэффициентов А, то 7 2(rtV3 + 2n). Неучет разреженности ограничивает целесообразность применения метода Гаусса решением задач только невысокой размерности. При п>50 учет разреженности становится необходимым. Для метода Гаусса при учете разреженности и оптимальном упорядочении строк и столбцов матрицы А в задачах проектирования технических объектов имеем [c.233]

Для решения систем ЛАУ итерационными методами с учетом разреженности матрицы коэффициентов имеем Я>1, а y—2Qn, где Q = 1—S—насыщенность матрицы. Так как Q = Kln, где К — среднее арифметическое для числа ненулевых элементов в одной строке матрицы А то у= 2К. Так, для моделей переключательных электрон ных схем получаем по результатам статистических иссле дований у ж 7,8, т. е. одна итерация выполняется быстрее чем по методу Гаусса. Однако из-за того, что И 1, ите рационные методы по показателю Г практически всегда проигрывают методу Гаусса. [c.233]

Размещение 271, 325 Разреженность матрицы 225 Ранжирование 252 Раскраска графа 210 Расплывчатое множество 196 Расстояние 206 Ребро графа 198 Регнстровый подуровень 195 Редактор связей 369 Режим интерактивный 35 [c.396]

Все универсальные программные комплексы, реализующие МКЭ, построены по модульному принципу. Модули, как правило, представляют собой отдельные программы, напнсанные на языке высокого уровня, например на языке ФОРТРАН. Непосредственно между собой модули не взаимодействуют, а объединяются в каждом конкретном случае в нужной последовательности с помощью монитора. Состав основных модулей является типичным для большинства программ и отражает существо основных этапов МКЭ (см. 1.2). Так, все универсальные программные комплексы имеют в своем составе модули, реализующие операции над матрицами, а также модули, реализующие работу с разреженными матрицами. Боль- [c.54]

Для решения этой системы, как правило, используется интерационный метод Ньютона—Рафсона, основанньг на сочетании неявных методов интегрирования с методами обработки разреженных матриц. Это позволило разработать простые и эффективные алгоритмы форми ювания математических моделей электронных схем ни основании метода узловых потенциалов. [c.162]

Модуль ОРТ обеспечивает минимизацию числа новых ненулевых элементов при решении системы линешп.к алгебраических уравнений в методе разреженных матриц, используемом з ПАРМ. [c.163]

К достоинствам рассмотренных итерационных методов следует отнести простоту их программной реализации и отсутствие принципиальной необходимости хранения в памяти ЭВМ всех коэффициентов матрицы. Действительно, при вычислении очередного приближения ц / согласно (1.22) нужны только отличные от нуля коэффициенты i-й строки А , bi, которые в принципе могут каждый раз вычисляться заново по исходным данным решаемой задачи. Это обстоятельство обусловливает широкое применение итерационных методов для систем с сильно разреженными матрицами большой размерности, в которых большинство элементов нулевые. Причем это делается как для матриц неленточной структуры, у которых ненулевые коэффициенты разбросаны по всему полю, так и для некоторых ленточных [c.14]

Такая организация пакета позволяет оптимально его спроектировать и реализовать. Основное внимание уделено разработке первой базовой части программного обеспечения. Пакет составлен на языке PL/1 в системе ДОС/ЕС. Так как матрицы [А], [5] и другие имеют очень много нулей (являются разреженными), то важным является вопрос об их хранении. Если их хранить в виде массивов, то существенно снизятся количественные возможности и возрастет время счета. Поэтому в пакете матрицы хранятся как разреженные, но при этом не удается воспользоваться стандартными программами, реализующими операции над матрицами, В пакете имеется набор операций над разреженными матрицами. Для решения системы алгебраических уравнений принят итерационный метод, который удобен при решении с матрицей разреженной структуры. В матрицах, используемых для решения задач строительной механики, число ненулевых элементов невелико, nosTOMy удобно хранить в памяти только ненулевые элементы вместе с необходимой информацией об их расположении, т. е. [c.45]

Матрица А имеет клеточную (блочную) структуру, которая затем нарушается после операции Л =Ло+С и перестановки строк. Использование метода Гаусса без выбора ведушцх элементов не приводит к накоплению опшбок при операциях исключениях. Связано это с большой разреженностью матрицы Л, в результате чего в каждой строке число ненулевых элементов невелико и, следовательно, мало число операций исключения. [c.387]

Матрица А этого уравнения обладает многими замечательными свойствами. Она является весьма разреженной матрицей общего вида, ее система фундаментальных ортонормированных функций обеспечивает хорошую устойчивость численного процесса решения краевой задачи, в определителе отсутствуют точки разрыва 2-го рода, формируется без привлечения матричных операций. Эти преимущества позволяют эффективно определять спектр собственных значений — корни уравнения (7.62). Точность спектра зависит, естественно, от точности исходной модели, где, напомним, используется только один член ряда (7.2). Уравнение (7.62) позволяет определять критические силы как статическим (при со=0), так и дцнамическим методами. При определении собственных значений пластин нужно учитывать, что из уравнения (7.62) можно получить спектры частот и критических сил при фиксированном числе полуволн в направлении оси ОХ (например, для коэффициентов А, В, С таблицы 7.1 одна полуволна в направлении оси ОХ и множество полуволн в направлении оси ОУ). Вычисляя коэффициенты А, В, С при второй частоте колебаний балки, из уравнения (7.62) можно получить спектры пластины для двух полуволн в поперечном и множества полуволн в продольном направлениях и т.д. Точность решения задач устойчивости и дцнамики прямоугольных пластин по МГЭ определим из примеров. [c.436]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...