Перенумерации алгоритм

Параметр верхней релаксации 241 Перенос начала координат 63 Перенумерации алгоритм 92 Перенумерация автоматическая ленточная 250 [c.299]

Изоморфные графы могут быть получены один из другого путем перенумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Если изоморфные преобразования проводятся с графом, заданным матрицей смежности, то они сводятся к перестановке местами соответствующих строк и столбцов. Известно, что в общем случае для определения изоморфизма графов необходимо сделать п сравнений или перестановок строк и столбцов матрицы, что для графов с л>30 не под силу даже современной ЭВМ. Поэтому необходимо применить тот или иной эвристический алгоритм поиска по дереву решений. [c.211]

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

Заключительный этап алгоритма — сортировка по знаку функции / (р) массивов координат и перенумерация вершин в результирующих наборах циклов особой трудности в программной реализации не представляет. [c.152]

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

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

В задачу генератора Г входит генерация объектных модулей процедур рабочей программы РП обращения к моделям элементов проектируемого объекта, расчета матрицы Якоби и вектора невязок, прямого и обратного хода алгоритма Гаусса, расчета данных для печати и др. Непосредственно генерации предшествует оптимальная перенумерация переменных математической модели объекта. Генерация объектных модулей производится в соответствии с деле-ннем проектируемого объекта на фрагменты. Такой подход необхо-ДИМ для реализации диакоптических методов анализа и способствует снижению требований к ОП, занимаемой компилятором, так как возникает возможность последовательной обработки фрагментов объекта с сохранением во внутренней БД только необходимого минимума информации о них. [c.143]

Существует несколько весьма удачных алгоритмов квази-оптймальной перенумерации вершин графа [3]. Так, в описываемой далее процедуре решения СЛАУ методом LDL -факторизации использован алгоритм минимальной степени, сущность которого заключается в том, что на очередном шаге перенумерации из всех вершин выбирается та, которая в данный момент имеет наименьшую степень. Этот алгоритм достаточно сложен, поскольку структура графа изменяется в процессе перенумерации вследствие появления новых ветвей. [c.39]

На рис. 4 приведена зависимость 1р = времени (в сек) построения сетки Дирихле на одну точку от количества точек N (расчеты проводились на ЕС-1052). Это время получено осреднением по 10 последовательным га агам. Номера кривых 1-4 соответствуют номерам методов построения индуктивные методы с поиском ближайгаей путем перебора (I), метода спуска (II), перенумерации (III) и алгоритм, основанный на локальных перестройках (IV). Временной гааг т выбирался из условия ВР 25%. Величина ВЗ здесь составляла 2-3%, а Р —до 5%. Были также проведены расчеты с существенно больгапм гаагом т, когда ВЗ и Р достигали, соответственно, 50% и 52%, а ВР — более 100%. Нри этом использовался метод V. Кривые 5, 6 относятся к значениям ВЗ 20% и 50% соответственно. [c.121]

В гл. 6 будет показано, что ширина ленты матрицы жесткости системы К зависит от способа нумерации узлов. Если программа решения системы уравнений не учитывает нулей внутри ленты, то время и стоимость решения будет зависеть от ширины ленты, В этой ситуации желательна такая нумерация узлов, при которой ширина ленты минимальна. Хотя для простых задач определить такую нумерацию легко, в случае сложной геометрии это может вызвать затруднения. К счастью, существуют программы, которые, используя в качестве исходных данных некоторую готовую нумерацию области, выполняют перенумерацию узлов так, чтобы минимизировать ширину ленты. Обычно такая программа, используемая перед основной конечноэлементной про-граммой, вместе с программой обратной перенумерации называется алгоритмом перенумерации, который может входить в общий процесс вычисления между первоначальным вводом исходных данных и окончательным выводом результатов решения. Таким образом, первоначальная нумерация используется при выводе результатов решения задачи. Дополнительная информация о программах перенумерации узлов имеется в работах [10- 13). [c.92]

Обычно симметричная ленточная матрица коэффициентов содержит миого нулей как вдоль краев ленты ), так н внутри ее. Редкость ненулевых членов в ленте может быть даже такой, что Число нулевых членов превышает чнс ю ненулевых. В большинстве прямых методов, в их простейшей форме, все элементы внутри ленты предполагаются неиулевыми соответственно устанавливаются требования, к памяти и объему вычислений. Однако программа может использовать некоторую проверку для предотвращения фактических вычислений с нулями. Эффективность таких бесхитростных подходов применительно к. некоторой конкретной задаче повышается, если разреженность уменьшить за счет-уменьшения ширины ленты матрицы коэффициентов. Как отмечалось ранее, ширина леиты зависит от способа нумерации узлов. Нумерация, обеспечивающая минимум ширины ленты, обычно очевидна только для простых задач. В случаях больших задач для уменьшения ширины ленты могут быть использованы подпрограммы автоматической перенумерации узлов (см. разд. 10.4.4). В таких случаях становится все более важным использовать разреженную природу матриц для уменьшения требуемых памяти и вычислений. В математическом плане алгоритмы для разреженных матриц должны учитывать очеиь важную идею, состоящую в том, что граф матрицы является ключом к ее структуре [2]. [c.232]

При использоваиии методов для разреженных матриц появляется трудность, состоящая в том, что некоторые элементы матрицы коэффициентов, первоначально считавшиеся нулями, становятся ненулевыми в процессе вычислений. Это называется заполнением. Желательно уменьшить его, насколько это возможно, так как каждый дополнительный ненулевой элемент вызывает впоследатвии дополиительнь1е вычисления. Один из алгоритмов, который во многих случаях значительно уменьшает заполнение, основан иа автоматической перенумерации узлов. Другой подход состоит в том, что в методе исключения Гаусса [22] ие сохраняются члены меньше заранее заданной величины. [c.233]

Большинство автоматических ленточных схем перенумера-ини допускает произвольную начальную нумерацию сеткн. Затем до решения матричного уравнения системы некоторый алгоритм меняет нумерацию узлов для уменьшения ширины ленты матрицы системы. Часто, после того как решение получено, перенумерацию узлов в первоначальное состояние обеспечивает яругой алгоритм. [c.250]

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

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