Andreiwse

Поиск соседних ячеек в неструктурированой сетке

Здравствуйте!
 

Пользуюсь сеткой в формате .NEU - габитовский формат. Данный формат как и другие мне известные имеет следующую структуру:

Матрица точек
номер точки1 - координаты точки1 
.

.
номер точкиN - координаты точкиN
 

 

Матрица ячеек 
номер ячейки1 - номера точек из которых состоит ячейка1

.

.
номер ячейкиМ - номера точек из которых состоит ячейкаМ
где N- кол-во точек, M - кол-во ячеек.  

Мне нужна следующая информация: для каждой ячейки знать номера ячеек с которыми она контактирует. Для этого я сравниваю каждую ячейку со всеми остальными ячейками, то есть каждую строку матрицы ячеек со всей матрицой ячеек. Получается два цикла один вложенный в другой в общем M^2 сравнений, расчет занимает очень много времени. 

Вопрос1  Есть ли способы ускорение расчета нужной мне информации?
Вопрос2  Есть ли форматы сеток в которых эта информация есть в явном виде?

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах


Мне нужна следующая информация: для каждой ячейки знать номера ячеек с которыми она контактирует

Для чего?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую. :flush:

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Делаете свой решатель? Тогда лучше искать информацию на иноязычных ресурсах.

Да, я делаю свой решатель. 

За ссылку спасибо, в есть кое что полезное. 

 

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую. :flush:

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен.

Не стоит Ваше время на реализацию поиска соседей используя данный формат. 

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

 

 

 

 

"И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен" - а где лучше об этом спросить, просто область моей задачи из газодинамики, вот я спросил сюда. 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В каких сеточных форматах есть именно то, что мне нужно в готовом виде

Попробуйте представить, как должен выглядеть формат данных, удовлетворяющий Вашим требованиям и Вы сами себе ответите на вопрос.

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Изменено пользователем piden

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Попробуйте представить, как должен выглядеть формат данных, удовлетворяющий Вашим требованиям и Вы сами себе ответите на вопрос.

Формат который мне нужен, я сам получаю из формата .NEU,  - то есть у меня есть понимание что мне  нужно. Но это мне не помогает. 

Если ВЫ знаете другие форматы, пишите в лоб как есть,  :smile:

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Изменено пользователем piden

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Да, я попробовал все форматы из Poinwise, я ничего не нашел.

Мне нужно что бы для тетраэдральной сетки была следующая матрица:

1   23 44 67 89

2   34  7  99 55

3  12  14 33 45

.

.

Где первая колонка это номера ячеек, четыре остальные колонки это номера соседних ячеек для данной ячейки. Например, ячейка 1 контактирует с ячейками 23 44 67 89. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

Контакт в моем случае это фейсом, и поэтому для каждой тетраидальной ячейки может быть только 4 соседа, если эта ячейка не является граничной. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком. :no:

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик :smile:

0_cd92e_eadc8efb_orig.png

Изменено пользователем Blurp

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком. :no:

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик :smile:

0_cd92e_eadc8efb_orig.png[

Есть ограничения, я могу пользоваться только своим кодом.

благодарю Вас за попытку помочь.  

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Есть ограничения, я могу пользоваться только своим кодом.

Понимаю.

Ответно благодарю вас за то, что заставили пошевелить мозгами. Хоть задачу не решил, но залез в такие дебри....вплоть до попыток прикрутить для решения MySQL сервер, либо файловую БД SQLite :biggrin: Но, увы, в SQL запросах не силен  :no_1:

А так, на всякий случай, если заинтересуетесь, то SQLite халявна. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

В принципе и TetGen фриварный. И, по идее, функцию поиска соседей оттуда можно утянуть.
А так, нашел еще тут в PDFке одной упоминание про какой-то генератор Pyramid и что якобы он информацию о соседях пишет в аутпут-файло, но более про этот генератор ничего не раскопал. :no:
 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Попробуйте представить, как должен выглядеть формат данных, удовлетворяющий Вашим требованиям и Вы сами себе ответите на вопрос.

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

Потому что судя по всему человек делает это первый раз в жизни  :smile: Это нормально. По этим всем граблям нужно пройти лично  :biggrin:

Изменено пользователем HFL
1 пользователю понравилось это

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

Потому что судя по всему человек делает это первый раз в жизни  :smile: Это нормально. По этим всем граблям нужно пройти лично  :biggrin:

Если я правильно понял. И у Вас и у меня по сути реализован конвертор формата из стандартного (unv, neu) в свой формат. Я тоже это делаю один раз для одной сетки. 

У меня без паралелеливания 400 тыс ячеек считает за 4 часа. А у Вас во сколько раз паралеливание дало выигрыш?

 

Изменено пользователем Andreiwse

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Если я правильно понял. И у Вас и у меня по сути реализован конвертор формата из стандартного (unv, neu) в свой формат. Я тоже это делаю один раз для одной сетки. 

У меня без паралелеливания 400 тыс ячеек считает за 4 часа. А у Вас во сколько раз паралеливание дало выигрыш?

 

По сути выигрыш равен числу параллельных потоков (в разах). То есть при распараллеливании у вас сложность будет не O(N^2) а O((N^2/n)) ... на самом деле выигрыш у нас еще больше из за алгоритмических ухищрений, связанных с порядком хранения структур (но это внутренняя кухня, которая работает только в частном случае)

 

То есть при использовании GPU это тысячи раз, при использовании MPI от десятков до сотен раз.

 

Ниже пример с куском выхлопа решалки.

7 внешних сеток, общий объем расчетной области ~24 млн. КО, при инициализации использовалось 160 ядер

 

Init HyperFLOW3D Solver time=965.836sec.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

GPU, multithreading....

Только хардкор! :biggrin:

0_cd9d3_72b0d9a4_orig.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Хардкоры ? Их есть у меня  :biggrin:

 

Сетка чуть больше 5млн. 

Время инициализации ~ 15 сек

 

3Tflop/s в даблах они такие  :rolleyes:

post-34943-0-41268800-1446831807.png

3 пользователям понравилось это

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Против Кеплер лома нет приема.
:flush::smile:

Но тему копать интересно тем не менее.
Пока ускорился аж в 10 раз. :biggrin: Целых 20 ячеек/сек для геометрии из 4-го поста. driving.gif
Не представляю, что будет при задаче размерностью 100K, наверное все загнется к едрене фене. Но приятно ощутить себя чуточку программистом :smile:

0_cd9e2_c1025b78_orig.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В 02.11.2015 в 20:20, Andreiwse сказал:

400 тыс ячеек считает за 4 часа

105 мин :wallbash:

0_dd2d1_e1e65ee3_M.png0_dd2d2_78f0965b_M.png

1 пользователю понравилось это

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте аккаунт или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать аккаунт

Зарегистрируйтесь для получения аккаунта. Это просто!


Зарегистрировать аккаунт

Войти

Уже зарегистрированы? Войдите здесь.


Войти сейчас

  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу



  • Реклама

  • Сообщения

    • Вячеслав к
      Здравствуйте! подскажите пожалуйста! 1. У меня есть два вида изделий одно является просто деталью, а второе его исполнение (проводим дополнительную мех. обработку, устанавливаем метизы) и это изделие становится сборочной единицей. Могу ли я на одном сборочном чертеже показать сразу два изделия:  и сборочную единицу и его исполнение просто деталь. Проблема в том что номенклатура таких изделий очень большая, нужно свести к минимуму бумагу, но смысл один два вида изделий. И второе: могу ли я расположить спецификацию на втором листе сборочного чертежа формата А3 (хотя вроде бы спецификацию можно вставлять только в чертеж А4). Извините если вопросы глупые)).
    • Goshha
      нет, двойная обгонная муфта не работает - согласования не происходит.
    • karachun
      Эксперимент будет проще и надежнее, возможно есть теория подобной обработки, и там полуэмпирически можно оценить эффективность разных абразивов и режимов работы виброустановки. Можно же связать виброскорость установки со средней скоростью гранул, и кин. энергию гранул со скоростью обработки.
    • karachun
      Не очень понял, что для такой геометрии можно все варианты считать в ламинарной постановке?  
    • Bot
      Dassault Systemes запускает отраслевое решение Reinvent the Sky для аэрокосмической и оборонной отрасли Стартапы и небольшие OEM-производители в сфере воздушных перевозок, такие как Joby Aviation, смогут вдвое сократить время разработки прототипов легких летательных аппаратов и беспилотников Платформа 3DEXPERIENCE предлагает новые облачные возможности для создания прорывных решений в области воздушных перевозок Авиакосмический салон в Фарнборо ФАРНБОРО, Великобритания, 23 июля 2018 года — Компания Dassault Systemes (Euronext Paris: #13065, DSY.PA) на Международном авиакосмическом салоне в Фарнборо (Farnborough International Airshow) объявила о запуске нового отраслевого решения Reinvent the Sky для аэрокосмической и оборонной отрасли. Построенное на базе платформы 3DEXPERIENCE компании Dassault Systemes, отраслевое решение Reinvent the Sky ускоряет разработку легких самолетов и беспилотных летательных аппаратов, начиная с работы над [...] View the full article
    • vad0000
      B CYBELEC DNC600S установлены 3 платы: материнская, клавиатура и экран.   Я бы для начала попробовал подсоединить компьютер к ЧПУ, и запустить программу flash.  
    • karachun
      Можно смоделировать через VOF жидкость и саму бочку, как жидкость с вязкостью, стремящейся к бесконечности, или это только для пластики? И тогда можно будет получить отрицательные давления в жидкости.
    • KAVKAZMEN
      Задача поставлена - значит выполнима. Предполагаю следующий алгоритм работы: 1. Проработка (поиск, заимствование, разработка) мат. части, описывающей движение частиц в вибробункере. 2. Ограничения или допущения в мат.части каким-то образом должны быть описаны в WB т.е. гу и ну.   здесь работы пока мне хватит разбираться.   Если я не правильно стратегически мыслю, прошу поправить.
    • piden
      ... а чтобы с достаточным приближением смоделировать сплошную среду через SPH, необходимо использовать хотя бы 1e18 партиклов...
    • kolo666
      Нет такого анализа, спектр в формате PSD/Гц прикладывается в анализе на случайное воздействие, а здесь просто ускорение на Гц. Если найдешь такой анализ, где можно приложить такое ускорение, то все очень обрадуются)  Это спектры ответа, они даже выглядят все практически один в один.  Абсолютно одинаково считаются, за исключением того, что для оборудования нужно еще получить спектр ответа на нужной высоте выполнив Response Spectrum, ну или взять из нормативов.   P.S. Мы недавно методу писали для гос. учреждения одного, я наелся уже этими спектрами, там тоже долго понять не могли что мы им там понаписали. Скорее всего просто кивнули, положили в ящик, и продолжили в статике 0.4g прикладывать.