Матрица разреженная

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

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

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

Итоговая разреженность 5 т матрицы зависит от ее исходной разреженности и от порядка, в каком расположены уравнения и неизвестные (строки и столбцы матрицы). Существует некоторый оптимальный порядок, при котором 5ит максимальна. Процедура упорядочения строк и столбцов матрицы с целью максимизации 5ит имеет [c.230]

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

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

На эффективность применения метода оказывают влияние не только особенности самого метода, но и в не меньшей мере особенности решаемой задачи и используемой ЭВМ. Среди наиболее существенных особенностей задач, называемых ниже факторами, отметим размерность п (порядок системы уравнений), число обусловленности Ц и разреженность S матрицы Якоби, а среди особенностей ЭВМ — быстродействие Б, определенное для класса научно-технических задач, емкость оперативной памяти и разрядность машинного слова. Разработчик ППП должен ориентироваться на некоторые диапазоны значений этих факторов, характерные для моделей проектируемых объектов в соответствующей предметной области. Эти диапазоны должны быть либо указаны в техническом задании на разработку ППП, либо спрогнозированы самим разработчиком на основе исследования статистических данных [c.232]

Подсчитайте разреженность для матрицы табл. 4.3. [c.260]

Можно ли применять метод прогонки к решению системы уравнений (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]

Свойства системы разностных уравнений и методы ее решения. Теперь рассмотрим ряд важных свойств, которыми обладает глобальная матрица. Во-первых, можно доказать, что она является симметричной. Во-вторых, глобальная матрица для задач большой размерности М является сильно разреженной, т. е. большинство ее элементов — нулевые. Наконец, путем введения разумной нумерации узлов ее можно сделать ленточной. [c.144]

Остановимся на двух последних свойствах матрицы. Очевидно, что коэффициент G j в т-й строке глобальной матрицы отличен от нуля, только когда узлы с номерами m и / являются вершинами ка-кого-то общего для них элемента. В этом случае в строке индексной матрицы, соответствующей этому общему элементу, будут содержаться номера т и /. Указанное обстоятельство и объясняет разреженность глобальной матрицы, поскольку, например, для треугольных элементов при значительном числе треугольников N большинство возможных пар узлов m и fe не являются вершинами общего треугольника и, следовательно, соответствующий элемент глобальной матрицы = 0. [c.144]

Матрицы S, D, Во для моделей с ациклическим графом являются существенно разреженными, а структура их определяется структурой 0-узлового графа, под которым понимается подграф рассматриваемой модели, образованный безынерционными узлами и связывающими их соединениями. Систему уравнений (12.1) можно разрешить относительно вектор-функции <р и ее второй [c.193]

Схемы (2.54) и (2.55) являются интерполяционными и не дают явного выражения для Tj , поскольку элементы матриц и и вектора зависят от искомых значений температур узловых точек в конце рассматриваемого интервала времени. Поэтому, строго говоря, использование этих схем связано с проведением итераций на каждом интервале времени, включающих обращение недиагональной матрицы j - A At или , j-i- t статочно высокого порядка М (хотя и сильно разреженной), что требует значительных вычислительных ресурсов ЭВМ. Эти схемы устойчивы при любых значениях Af , причем результаты расчетов по схеме (2.54) сохраняют физический смысл, а результаты расчета по схеме (2.55) при больших значениях At, могут [c.46]

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

Снова выделим в области V, занятой неоднородным анизотропным телом произвольной формы, М узловых точек Р у, т = 1 М и выберем и так, чтобы (Р ) = и Р ) = 6, , что соответствует конечно-элементной аппроксимации искомого распределения температуры. В таком случае функции X t) и ф ( ) в (2.56) и (2.57) приобретают смысл изменяющихся во времени t узловых значений температуры (t), составляющих вектор Т. Тогда после подстановки (2.56), (2.57) в (2.47) получим систему в общем случае нелинейных обыкновенных дифференциальных уравнений вида (2.51), но теперь матрица теплоемкостей С = [С (Г)]м X м будет диагональной, причем степень разреженности симметричных матриц С и А будет зависеть от [c.48]

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

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

Алгоритм вычисления матрицы Якоби в методе узловых потенциалов. Вычисление матрицы Якоби как матричного произведения 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]

Экономичность метода решения систем АУ определяется также затратами оперативной памяти. При неучете разреженности только на хранение матрицы Якоби нужно п ячеек памяти. Поэтому если для одного слова используется 8 байт, то при п=100 для хранения требуется 80 кбайт, а при п = 500 — уже 2 Мбайт. Итак, подтверждается вывод о необходимости учета разреженности при решении задач с п>п р, где Ппр зависит от характеристик используемой ЭВМ и, как правило, составляет несколько десятков. В задачах анализа распределенных моделей, в которых п может превышать 10 , экономичность метода по затратам машинной памяти становится одной из важнейших характеристик. В таких случаях применяют либо релаксационные методы, либо метод Ньютона с использованием на каждой итерации метода Гаусса, но в рамках рассматриваемого ниже диакоптического подхода. [c.234]

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

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

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

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

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

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

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

Теоретические основы САПР (1987) -- [ c.230 ]

Основы автоматизированного проектирования (2002) -- [ c.106 ]

Теплоэнергетика и теплотехника Общие вопросы Книга1 (2000) -- [ c.125 ]

Основы теории и проектирования САПР (1990) -- [ c.34 ]

Метод конечных элементов Основы (1984) -- [ c.76 ]

Введение в метод конечных элементов (1981) -- [ c.139 , c.232 , c.250 ]

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

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