Применение методов частиц в задачах с неструктурированными сетками
В работе предложен эффективный экономичный метод расчета сил взаимодействия между частицами, позволяющий значительно сокращать время расчетов, а также экономить оперативную память. На основе рассмотренного метода был разработан новый метод быстрого поиска частиц в ячейках неструктурированных сеток....
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83296 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Применение методов частиц в задачах с неструктурированными сетками / И.А. Бровченко // Мат. машини і системи. — 2010. — № 3. — С. 111-115. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860197158888669184 |
|---|---|
| author | Бровченко, И.А. |
| author_facet | Бровченко, И.А. |
| citation_txt | Применение методов частиц в задачах с неструктурированными сетками / И.А. Бровченко // Мат. машини і системи. — 2010. — № 3. — С. 111-115. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В работе предложен эффективный экономичный метод расчета сил взаимодействия между частицами, позволяющий значительно сокращать время расчетов, а также экономить оперативную память. На основе рассмотренного метода был разработан новый метод быстрого поиска частиц в ячейках неструктурированных сеток. Разработанный алгоритм может быть применен в любых лагранжевых моделях типа «частица-частица», «частица-сетка» и их вариациях.
В роботі запропонований ефективний економічний метод розрахунку сил взаємодії між частками, що дозволяє значно скорочувати час розрахунків, а також економити оперативну пам'ять. На основі розглянутого методу був розроблений новий метод швидкого пошуку часток у комірках неструктурованих сіток. Розроблений алгоритм може бути застосований у будь-яких лагранжевих моделях типу „частка-частка", „частка-сітка" та їх варіаціях.
In present paper an effective and time-conserving method of calculating the interaction forces between particles that significantly reduce the time of calculations and memory usage is proposed. On the basis of the method a new method for fast searching of particles in the cells of unstructured grids was developed. The developed algorithm can be applied to any Lagrangian model such as "particle-particle" and "particle-mesh" and their variations.
|
| first_indexed | 2025-12-07T18:08:31Z |
| format | Article |
| fulltext |
© Бровченко И.А., 2010 111
ISSN 1028-9763. Математичні машини і системи, 2010, № 3
УДК 004.9:504:519.6
И.А. БРОВЧЕНКО
ПРИМЕНЕНИЕ МЕТОДОВ ЧАСТИЦ В ЗАДАЧАХ С НЕСТРУКТУРИРОВАННЫМИ
СЕТКАМИ
Аbstract. In present paper an effective and time-conserving method of calculating the interaction forces between par-
ticles that significantly reduce the time of calculations and memory usage is proposed. On the basis of the method a
new method for fast searching of particles in the cells of unstructured grids was developed. The developed algorithm
can be applied to any Lagrangian model such as "particle-particle" and "particle-mesh" and their variations.
Key words: particle methods, unstructured grids.
Анотація. В роботі запропонований ефективний економічний метод розрахунку сил взаємодії між частка-
ми, що дозволяє значно скорочувати час розрахунків, а також економити оперативну пам’ять. На основі
розглянутого методу був розроблений новий метод швидкого пошуку часток у комірках неструктурованих
сіток. Розроблений алгоритм може бути застосований у будь-яких лагранжевих моделях типу „частка-
частка”, „частка-сітка” та їх варіаціях.
Ключові слова: методи часток, неструктуровані розрахункові сітки.
Аннотация. В работе предложен эффективный экономичный метод расчета сил взаимодействия между
частицами, позволяющий значительно сокращать время расчетов, а также экономить оперативную па-
мять. На основе рассмотренного метода был разработан новый метод быстрого поиска частиц в ячейках
неструктурированных сеток. Разработанный алгоритм может быть применен в любых лагранжевых мо-
делях типа «частица-частица», «частица-сетка» и их вариациях.
Ключевые слова: методы частиц, неструктурированные расчетные сетки.
1. Введение
Моделирование методами частиц становится все более популярным с развитием вычислительных
возможностей и параллельных технологий [1, 2]. Важным моментом как в теоретических, так и экс-
периментальных исследованиях является умение прослеживать движение большого числа частиц
в полях, создаваемых ими самими и под действием внешних сил. В настоящее время все более
привлекательными становятся гибридные модели (частицы плюс сеточные модели), особенно в
гидродинамических задачах, в которых необходимо рассматривать разномасштабные процессы.
Термин «модели частиц» является общим для класса вычислительных моделей, в которых дис-
кретное описание физических явлений включает использование взаимодействующих частиц. В
большинстве приложений этим частицам можно прямо сопоставить физические объекты. Каждая
частица может иметь набор атрибутов, таких как масса, заряд, положение, скорость. Состояние
физической системы определяется атрибутами конечного ансамбля частиц, а эволюция системы
определяется законами взаимодействия этих частиц. Особенность, которая делает модели частиц
привлекательными с вычислительной точки зрения, состоит в том, что ряд атрибутов частицы со-
храняется, и поэтому их не надо изменять, когда вычислительная модель развивается во времени.
Связь между частицами вычислительной модели и частицами физической системы в значительной
степени определяется соотношениями ограниченных вычислительных ресурсов и характерных
пространственных и временных масштабов физических систем. Данная работа посвящена разви-
тию эффективных и экономичных методов сортировки и поиска частиц в гибридных моделях, где
рассматриваются частицы и конечноразностные сетки. Такие задачи возникают при необходимо-
сти рассмотреть движение частиц в заданном гидродинамическом поле, характеристики которого
(поле скоростей, давление, возвышения свободной поверхности) заданы в узлах конечноразност-
ной сетки. В моделировании методом частиц можно выделить две основные задачи: вычисление
сил взаимодействия между частицами и интегрирование траекторий частиц.
ISSN 1028-9763. Математичні машини і системи, 2010, № 3 112
2. Расчет сил взаимодействия между частицами в модели «частица-частица»
Рассмотрим модель «частица-частица», где необходимо рассчитывать силы взаимодействия меж-
ду частицами. Во всех задачах, где возникают подобные силы (гравитационные, кулоновские, дав-
ление в жидкостях), для расчета сил взаимодействия на каждом временном шаге модели необхо-
дим расчет расстояний между частицами. В вычислительной гидродинамике широко используется
метод SPH [3, 4] (гидродинамика сглаженных частиц), в котором сплошная среда моделируется
методом взаимодействующих частиц. При общем количестве частиц N для рассчета расстояний
между всеми частицами потребуется 2N операций. В большинстве приложений силы взаимодей-
ствия являются короткодействующими и их можно не учитывать, начиная с некоторого расстояния,
которое будем называть эффективным радиусом взаимодействия fR . Но для того чтобы выяснить,
нужно ли учитывать какую-либо частицу, надо сначала определить расстояние до неё, что, в свою
очередь, дает количество операций порядка 2N . Возникает задача о сортировке частиц по коор-
динатам таким образом, чтобы вычислять расстояния только для некоторого подмножества nN
общего количества частиц N . Для этого для двумерной задачи, следуя [1], вводится цепочечная
сетка – решетка размерностью x yM M× , покрывающая расчетную область с размером ячейки,
равным fR . Тогда в силу, действующую на частицу, находящуюся в ячейке, будут оказывать нену-
левой вклад только те частицы, которые находятся либо в этой же ячейке, либо в девяти соседних.
Для определения, какие именно частицы находятся в соседних ячейках, нужно провести предвари-
тельную сортировку частиц. Предварительная адресная сортировка проводится согласно алгорит-
му, описанному в [1], следующим образом. Вначале нужно ввести два вспомогательных сортиро-
вочных массива: массив заголовков H размерностью x yM M× и цепочечный массив LL размер-
ностью N . Перед началом сортировки эти массивы следует обнулить и для каждой частицы i вы-
полнить действия:
1. Определить ячейку цепочечной сетки q , в которой находится частица.
2. Добавить частицу i в заголовок списка для ячейки q :
( ) ( ), ( )LL i H q H q i= = .
После проведенной сортировки номер первой частицы, находящейся в ячейке q , можно
определить как ( )i H q= , а все последующие частицы можно перебрать, используя соотношение
( )i LL i= до тех пор, пока полученный номер частицы не станет равным нулю. Таким образом
можно определить все частицы, находящиеся в ячейке q . После передвижения частиц (на сле-
дующем временном шаге) необходимо опять обнулить сортировочные массивы и повторить проце-
дуру сортировки. Если предположить, что частицы равномерно располагаются по всей расчетной
области, то полное число проверок приблизительно равно 29 / x yN M M , что даёт значительное
уменьшение числа операций при малых отношениях радиуса взаимодействия к линейным разме-
рам расчетной области.
ISSN 1028-9763. Математичні машини і системи, 2010, № 3 113
3. Быстрый поиск частиц в модели «частица-сетка»
Рассмотрим теперь задачу, в которой силы, действующие на частицы, заданы в узлах неподвижной
сетки, так называемая модель «частица-сетка». В этом случае необходима интерполяция данных
из узлов сетки в точки расположения частицы. Для того чтобы применить любой из методов интер-
поляции, сначала необходимо определить ближайшие к частице узлы сетки или ячейку сетки, в ко-
торой находится частица. В случае прямоугольных равномерных сеток расположение частицы на-
ходится в две операции:
( )[ ] 1/ +−= dxxxi o ,
( )[ ] 1/0 +−= dyyyj .
Здесь ( , )i j – номер ячейки прямоугольной сетки, ( ),x y – координаты частицы, ( )0 0,x y –
координаты левого нижнего угла прямоугольной сетки, ( ),dx dy – разрешение сетки. Здесь и далее
операция [ ] означает взятие целой части.
В случае неравномерных, криволинейных или неструктурированных сеток задача поиска
ячейки становится более сложной и проблема выбора оптимального алгоритма поиска – более
важной, так как искомый алгоритм должен применяться на каждом временном шаге модели. Рас-
смотрим общий случай сетки, состоящей из треугольных элементов. Так как любую сетку из эле-
ментов сложной формы можно преобразовать в сетку из треугольных элементов, то изложенный
ниже алгоритм пригоден для любых случаев. Введем обозначения: ei – номер треугольного эле-
мента, 1 2 3, ,i i i – номера узлов, составляющих этот элемент, ( ), , 1,3i ix y i = – координаты этих
узлов. Предполагаем, что узлы каждого треугольного элемента расположены по порядку против
часовой стрелки. Тогда критерием попадания частицы в данный элемент можно считать положи-
тельный знак векторного произведения:
( ) ( )1 1, , 0, 1,3i i i ix x y y x x y y i+ +− − × − − > ∀ = . (1)
Для того чтобы ускорить нахождение требуемого элемента, введем новую равномерную
прямоугольную сетку с размером ячейки, равным максимальному размеру всех элементов сетки из
треугольных элементов. Обозначим разрешение вспомогательной прямоугольной сетки
( ),DXS DYS и предварительно рассортируем все треугольные элементы по ячейкам этой сетки.
Для этого модифицируем алгоритм цепочечной сортировки, описанный в предыдущем разделе.
Изменение алгоритма необходимо, так как каждый треугольный элемент может находиться более
чем в одной ячейке цепочечной сетки. Максимально каждый треугольник может находиться одно-
временно в четырех ячейках цепочечной сетки. Определим для каждого треугольника максималь-
ные и минимальные координаты:
( )ie xx minmin = , ( )ie yy minmin = , 3,1=i ,
( )ie xx maxmax = , ( )iema yy max[ = , 3,1=i .
ISSN 1028-9763. Математичні машини і системи, 2010, № 3 114
Для сортировки треугольных элементов введем массив заголовков ( * ,4)H DXS DYS и це-
почечный массив ( , 4)eLL N . Для каждого из eN треугольников проведем следующие операции:
1. Определим номера ячеек , 1, 4jq j = , в которые могут попасть части треугольного эле-
мента ei :
[ ] [ ]( ) [ ] [ ]( )
[ ] [ ]( ) [ ] [ ]( )
1 min min 2 max min
3 max max 4 min max
/ 1, / 1 , / 1, / 1 ,
/ 1, / 1 , / 1, / 1 .
e e e e
e e e e
q x DXS y DYS q x DXS y DYS
q x DXS y DYS q x DXS y DYS
= + + = + +
= + + = + +
2. Для каждой ячейки jq :
( ) ( ), ,e jLL i j H q j= ,
( ),j eH q j i= .
Следует отметить, что описанная выше процедура предварительной сортировки проводит-
ся один раз перед основным временным циклом и больше не повторяется. Алгоритм поиска тре-
угольного элемента, в котором находится частица на каждом временном шаге, будет выглядеть
так:
1. Проверить элемент, в котором находилась частица на предыдущем временном шаге по
критерию (1).
2. Определить ячейку цепочечной сетки, в которой находится частица:
[ ] [ ]( )/ 1, / 1q x DXS y DYS= + + .
3. Перебрать все треугольные элементы, которые полностью или частично находятся в
ячейке q . Для этого проделать следующие действия в цикле 1,4j = :
– определить номер первого треугольника ( ),ei H q j= ;
– повторять, пока 0ei ≠ :
• в случае удовлетворения условия (1) для треугольника ei выйти из всех циклов;
• ( , )e ei LL i j= .
4. Запомнить номер треугольника ei для использования при поиске на следующем времен-
ном шаге.
После нахождения номера треугольного элемента можно использовать любой из известных
методов интерполирования, используя значение переменных в узлах составляющих элемента, а
также значения в узлах окружающих элементов.
4. Выводы
В работе предложен эффективный экономичный метод расчета сил взаимодействия между части-
цами, позволяющий значительно сокращать время расчетов, а также экономить оперативную па-
мять. На основе рассмотренного метода был разработан новый метод быстрого поиска частиц в
ISSN 1028-9763. Математичні машини і системи, 2010, № 3 115
ячейках неструктурированных сеток. Разработанный алгоритм может быть применен в любых ла-
гранжевых моделях типа «частица-частица» и «частица-сетка» и их вариациях. Главными особен-
ностями алгоритма являются быстрая скорость его работы и экономия оперативной памяти, что
достигается введением цепочечных массивов, которые не содержат большого количества нулевых
элементов. Описанный алгоритм с успехом использовался в численных лагранжевых моделях рас-
пространения поверхностных пленок нефти [5, 6], взвеси [7, 8], а также в задачах по расчету трех-
мерных траекторий пассивных трассеров.
CПИСОК ЛИТЕРАТУРЫ
1. Хокни Р. Численное моделирование методом частиц / Р. Хокни, Дж. Иствуд. – М.: Мир, 1987. – 638 с.
2. Зализняк В.Е. Основы вычислительной физики. Ч. 2: Введение в методы частиц: Регулярная и хаотическая
динамика / Зализняк В.Е. – Ижевск: Институт компьютерных исследований, 2006. – 156 с.
3. Monaghan J.J. An introduction to SPH / J.J. Monaghan // Comput. Phys. Commun. – 1988. – Vol. 48. – P. 89 – 96.
4. Каліон В.А. Використання методу гідромеханіки згладжених часток для розв’язання задач гідродинаміки до-
вкілля / В.А. Каліон, І.О. Бровченко, А.О. Кущан // Вісник Київського університету. – (Серія «Фізико-математичні
науки»). – 2007. – № 4. – С. 77 – 83.
5. Бровченко И.А. Численный лагранжевый метод моделирования распространения поверхностных пятен
нефти / И.А. Бровченко, В.С. Мадерич // Прикладная гидромеханика. – 2002. – Т. 4 (76), № 4. – С. 23 – 31.
6. Maderich V. Oil Dispersion by breaking waves and currents / V. Maderich, I. Brovchenko // Sea Technology. –
2005. – Vol. 46 (4). – Р. 17 – 22.
7. Бровченко И.А. Двумерная лагранжевая модель переноса многофракционных наносов в прибрежной зоне
моря / И.А. Бровченко, В.С. Мадерич // Прикладная гидромеханика. – 2006. – Т. 8 (81), № 2. – C. 9 – 17.
8. Бровченко И.А. Трехмерная лагранжевая модель переноса многофракционных наносов и ее применение к
описанию гравитационных течений / И.А. Бровченко, В.С. Мадерич // Прикладная гидромеханика. – 2008. –
Т. 11 (83), № 2. – С. 3 – 12.
Стаття надійшла до редакції 03.12.2009
|
| id | nasplib_isofts_kiev_ua-123456789-83296 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T18:08:31Z |
| publishDate | 2010 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Бровченко, И.А. 2015-06-18T07:46:18Z 2015-06-18T07:46:18Z 2010 Применение методов частиц в задачах с неструктурированными сетками / И.А. Бровченко // Мат. машини і системи. — 2010. — № 3. — С. 111-115. — Бібліогр.: 8 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83296 004.9:504:519.6 В работе предложен эффективный экономичный метод расчета сил взаимодействия между частицами, позволяющий значительно сокращать время расчетов, а также экономить оперативную память. На основе рассмотренного метода был разработан новый метод быстрого поиска частиц в ячейках неструктурированных сеток. Разработанный алгоритм может быть применен в любых лагранжевых моделях типа «частица-частица», «частица-сетка» и их вариациях. В роботі запропонований ефективний економічний метод розрахунку сил взаємодії між частками, що дозволяє значно скорочувати час розрахунків, а також економити оперативну пам'ять. На основі розглянутого методу був розроблений новий метод швидкого пошуку часток у комірках неструктурованих сіток. Розроблений алгоритм може бути застосований у будь-яких лагранжевих моделях типу „частка-частка", „частка-сітка" та їх варіаціях. In present paper an effective and time-conserving method of calculating the interaction forces between particles that significantly reduce the time of calculations and memory usage is proposed. On the basis of the method a new method for fast searching of particles in the cells of unstructured grids was developed. The developed algorithm can be applied to any Lagrangian model such as "particle-particle" and "particle-mesh" and their variations. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління великими системами Применение методов частиц в задачах с неструктурированными сетками Застосування методів часток в задачах з неструктурованими сітками Application of particle methods to the problems with unstructured grids Article published earlier |
| spellingShingle | Применение методов частиц в задачах с неструктурированными сетками Бровченко, И.А. Моделювання і управління великими системами |
| title | Применение методов частиц в задачах с неструктурированными сетками |
| title_alt | Застосування методів часток в задачах з неструктурованими сітками Application of particle methods to the problems with unstructured grids |
| title_full | Применение методов частиц в задачах с неструктурированными сетками |
| title_fullStr | Применение методов частиц в задачах с неструктурированными сетками |
| title_full_unstemmed | Применение методов частиц в задачах с неструктурированными сетками |
| title_short | Применение методов частиц в задачах с неструктурированными сетками |
| title_sort | применение методов частиц в задачах с неструктурированными сетками |
| topic | Моделювання і управління великими системами |
| topic_facet | Моделювання і управління великими системами |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83296 |
| work_keys_str_mv | AT brovčenkoia primeneniemetodovčasticvzadačahsnestrukturirovannymisetkami AT brovčenkoia zastosuvannâmetodívčastokvzadačahznestrukturovanimisítkami AT brovčenkoia applicationofparticlemethodstotheproblemswithunstructuredgrids |