Добрый день.
В общем у меня такая математическая задача.
Есть некий массив частиц (от несколько тысяч.. сверху не ограничен), которые движутся прямолинейно с определенной скоростью, одинаковой для всех частиц. То есть их движение можно задать уравнением прямой линии. Мне необходимо просчитывать их соударения.
Система представляет собой квадрат, то есть все происходит на плоскости, и взаимодействия частиц со границами системы, а так же между собой, происходит согласно закону сохранения импульса.

До этого у меня алгоритм просчета взаимодействия был таков: пошагово сдвигал все частицы на некое расстояние, и делал проверку на взаимодействие между всеми (каждую сверял с каждой) частицами.

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

А теперь вопрос:
1. Насколько алгоритм, используемый матричные уравнения может быть быстрей для расчетов?
2. Если имеет смысл его реализовывать, то не могли бы вы подсказать, в какую сторону мне смотреть. А то матричная алгебра была давно, и я уже плохо что помню.

GD Star Rating
loading...

22 Responses to Математическая задача

  1. Peels:

    Навскидку:
    1) Быстрее не будет, ибо тебе все равно придется считать попарные соударения. Т.е. O(n^2) останется.
    Зато ты узнаешь *аналитически точно* когда, в каких точках, и в каком порядке эти соударения произойдут. Как человек, когда–то писавший бильярд, могу тебе сказать что твой подход «давай дискретно посимулируем и прикинем на глаз» заканчивается довольно большим количеством неприятных просчетов, недосчетов и других глюков, и, по крайней мере для бильярда, представляет из себя полный фейл.
    С другой стороны, если у тебя частиц очень много и ты готов пожертвовать точностью и некоторыми из соударений, дискретное симулирование может оказаться на порядок эффективнее. К примеру, если мильен частиц летят все чтобы столкнуться в области радиусом эпсилон, то при аналитическом подсчете ты должен будешь разбирать 1 000 000 000 000 различных столкновений, при чем для каждого из них придется пересчитывать положения для всех частиц, а при дискретном симулировании с шагом эпсилон ты засечешь это как одно единственное столкновение «всех со всеми». Как решить, куда они будут разлетаться отдельный вопрос, конечно.

    2) Забей на понятие «матричная алгебра» и по началу реализуй тупенький алгоритм такого типа:
    struct particle { vector position, speed; }
    function time_to_collision(particle1, particle2);
    function simulate(particles) {
    collisions = { (p1,p2,t) for (p1,p2) in particles * particles, t = time_to_collision(p1,p2) }
    find collision with the smallest t.
    resolve collision, increase time by t and move all particles.
    }
    Теперь если у тебя частиц очень много, можно думать дальше как эту штуку оптимить. Например, как минимум стоит хранить массив collisions в priority queue и после каждого столкновения пересчитывать там только те пары, которые затрагивают измененные частицы. Потом можно прифигачить какие–нибудь BSP–trees и не пересчитывать столкновения для тех, кто не столкнется, и т.п.
    Другими словами, я пока не вижу как тебе поможет именно «матричная» алгебра. Ну да, функция time_to_collision — это решение линейного уравнения, но оно без матриц замечательно решается.

    3) Это я все навскидку сказал, вполне возможно что где–то можно умно пихнуть матрицу и все станет очень клево.

  2. Agnek:

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

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

  3. Peels:

    Ну концептуально ты можешь конечно написать решение линейного уравнения для time_to_collision в матричной форме, но на практике ты все равно будешь считать без матриц — так проще и быстрее:

    *1 + t v1 = *2 + t v2
    откуда
    (v1–v2) t = (*2–*1)
    т.е.
    a) t = 0, если *1 = *2, v1=v2
    b) t = infty, если (*2–*1).* / (v1–v2).*!= (*2–*1).y / (v1–v2).y или хотя бы один из знаменателей нуль
    c) t = (*2–*1).* / (v1–v2).*, в остальных случаях.

    Это не матрица, но это довольно простые вычисления. Осталось выбрать самое маленькое и запускать следующий шаг.

  4. ReLyrik:

    «Быстрее не будет, ибо тебе все равно придется считать попарные соударения. Т.е. O(n^2) останется.»

    при пошаговом подходе нужно для каждой точки находить только ближайшую к ней, а не перебирать все пары. это делается за O(n log n) триангуляцией Делоне / диаграммой Вороного

  5. ReLyrik:

    точное решение:

    моменты времени — только моменты столкновений. в остальное время частицы свободно летят, нужно только их отрисовывать (если нужно — или вообще ничего не делать иначе)

    в каждый момент времени вычисляем для каждой точки возможности всех столкновений, находим ближайшее во времени
    находим ближайшее во времени столкновение во всей системе, заканчиваем итерацию

    чтобы на следующей итерации быстрее найти столкновение, сначала пересчитываем время ближайшего столкновения для всех точек, которые не сталкивались в данный момент (то есть продолжают лететь прямо), это линейно делается
    потом для только что столкнувшихся точек пересчитываем столкновения. правда, это может инициировать цепной пересчет столкновений для многих точек уже спокойно летевших по прямой навстречу судьбе, но мне кажется, что в хорошем случае большинство столкновений должно происходить только со стенками, а не с другими точками

  6. ReLyrik:

    zoster– здесь первая итерация — O(n^2), остальные — как повезёт, могут быть линейны или чуть сложнее
    если точки расположены очень плотно в квадрате, сложность будет очень высока, конечно (но уж точно не больше O(n^2), то есть пошагового перебора)

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

  7. ReLyrik:

    zoster– можно ввести фиктивные столкновения, тогда и от цепного пересчета избавиться

    можно много чего сделать. главное не делать с маленьким шажком, это антиматематично

  8. Peels:

    zoster– С маленьким шажком можно считать, если цель, к примеру, просто нарисовать красивенький взрыв–пыщь–пыщь в контексте какого–нибудь модного скринсейвера, UI или звуковизуализатора. Тогда аналитическая точность не нужна, а константное количество операций за секунду не повредит.

  9. ReLyrik:

    это, конечно, так
    но в посте написано «математическая задача»! )

  10. Agnek:

    zoster– большое спасибо за информацию.

  11. Agnek:

    Ну на практике это задача называется так: «Моделирование агрегации наночастиц металлов в водных растворах».
    То, что я привел, это всего–лишь алгоритм одной из моделей. Самой простой модели.

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

    Правда есть еще другие модели:
    Например, в одной из них, положение частиц меняется случайно после преодоления какого–то расстояния (что–то вроде длины свободного пробега).

  12. Agnek:

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

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

  13. AHMath:

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

    Тебе должно быть интересна не скорость сферического алгоритма в вакууме, а скорость «алгоритм+железо», причем именно для твоей задачи. Посмотри в сторону библиотек CUDA — они реализуют матричные операции напрямую в железе видео процессора, что гораздо быстрее ЦПУ.

  14. Agnek:

    ну про openCL я уже читаю.

  15. ReLyrik:

    так я же говорю, что нужно считать только в моменты столкновений (+ в моменты внезапной смены траектории)
    и более того в каждый момент не нужно пересчитывать состояние для всех точек (достаточно для изменивших маршрут, например, столкнувшихся)

    а что требуется от матриц, не очень понятно
    здесь же нужно минимизировать, а не какую–то линейную функцию вычислять
    нельзя определить, какое событие произойдет раньше, решив линейную систему уравнений, потому что сама постановка задачи предполагает неравенство

  16. ReLyrik:

    скорость частиц мало варьируется?
    потому что если скорости сильно отличаются, то близость теряет смысл. столкнуться может очень быстрая частица, прилетевшая хрен знает откуда

  17. Agnek:

    zoster– ну так скажем, что максимальная скорость сверху ограничена.
    Я об этом уже подумал. Думаю, что сделаю, чтобы эти подсистемы пересекались между собой на определенную ширину. То есть частица, находящаяся в этом «пограничном» слое, будет принадлежать двум подсистемам одновременно. Но тогда придется ввести опять некий максимальный шаг. То есть опять вернуться к не очень хорошему алгоритму.
    В общем, ты меня подтолкнул к такой мысли, что единственный способ организации параллельных вычислений организация проверки взаимодействия между каждой частицы с каждой в несколько потоков.

  18. SpMonkey:

    вы простите меня безграмотного может я невнимательно прочитал, но почему не применимы какие–нибудь аналитические методы решения данной задачи через какие нибудь уравнения Больцмана, или Боголюбова, Фокера–Планка или как там…

  19. Agnek:

    потому что смысл решение данной задачи — получение формы конечного агрегата, значения его фрактальной размерности, порога перколяции и так далее. В теории агрегации существуют так называемые стохастические кластер–кластер модели агрегации, которые я и пытаюсь реализовать.

  20. SpMonkey:

    прости меня в очередной раз если буду глупости говорить 🙂
    Я теперь примерно понимаю что ты пытаешься сделать. Но меня не покидает ощущение, что применение аналитических методов в процессе симуляции процессов агрегации (вроде бы ты этим занимаешься) может позволить тебе повысить эффективность алгоритма сократив количество точек для перебора на каждой итерации. Но возможно я не прав.

  21. SpMonkey:

    более того, можно варьировать размер шага (временного) для пересчёта. Брать например минимальное время которое требуется ближайшей частице для достижения кластера? Хотя я запутался, что происходит с частицами в момент соударения между собой? Агрегируются (или как это правильно назвать)?

  22. SpMonkey:

    перечитал ещё раз условие. С одной стороны ты написал «взаимодействуют между собой и стенками абсолютно упруго».. с другой стороны ниже написал про «агрегацию».
    Кажется полимер какой–то моделируешь? Я не могу понять физику самого процесса (я не специалист, мне просто интересно) 🙂

Добавить комментарий