Не могли бы вы итеративно использовать алгоритм Барнса-Хата с несколькими центральными квадрантами?

Question

Не могли бы вы итеративно использовать алгоритм Барнса-Хата с несколькими центральными квадрантами?

Физика
многотелый
алгоритмы
симуляции
ньютоновская гравитация
вычислительная физика

Волшебная урна с осьминогом

Мне было интересно, можете ли вы использовать симуляцию Barnes-Hut помимо того, для чего она изначально предназначалась. Для многих алгоритмов Барнса-Хата силы учитываются только для одного квадранта, центроида или звездного тела. Затем алгоритм разветвляется оттуда, рекурсивно затрагивая области влияния и квадранты. Например:

Похоже, что приведенный выше алгоритм Барнса-Хата был основан на центральном теле из анимации.

Мой вопрос:

Приведет ли итеративное выполнение Барнса-Хата ко всем телам, рассматривая каждое тело по очереди как центр тяжести, к точному представлению задачи n тел, где рассматривается сумма сил гравитации всех тел? Или я неправильно понимаю, что такое алгоритм Барнса-Хата?

Если я неправильно понимаю алгоритм, может ли кто-нибудь объяснить, как именно работает этот алгоритм? Для тех, кто в какой-то степени понимает программирование, может ли кто-нибудь взглянуть на этот проект и сказать мне, не упускаю ли я здесь что-то важное? Это реализация алгоритма Barnes-Hut на Java GitHub , но я повторил его во всех телах (что может быть невероятно глупо). Также... да, я знаю, что время работает не так. Примечание. Кредит принадлежит оригинальному профессору, как указано на GitHub.

Кроме того, для тех, кто не разбирается в технологиях, можете ли вы посмотреть на этот GIF и увидеть что-то изначально неправильное? Красный меньше массы, белый больше массы; желтые - две или более столкнувшихся масс. Как только появляется третья желтая точка (объединенная масса), все становится интереснее. Я не могу сказать, интересно ли это хорошо, или интересно... плохо.

Волшебная урна с осьминогом

Вот 1000 частиц за 1000 шагов: i.imgur.com/SwPbG4j.mp4

Кайл Канос

Если вы перебираете все тела, разве вы не выполняете стандартный закон обратных квадратов для всех тел? В таком случае, вы только что отменили цель метода BH??

Волшебная урна с осьминогом

@KyleKanos, не будет ли закон обратных квадратов выполняться из другой исходной точки отсчета? Я могу быть абсолютно не прав во всех отношениях.

Кайл Канос

Весь смысл BH заключается в том, чтобы уменьшить рабочую нагрузку, необходимую для решения

a_{i} \sim \sum_{j} 1 / | r_{i} - r_{j} |^{2}

$a_i\sim\sum_j 1/\vert r_i-r_j\vert^2$ рассматривая кучу частиц как кластер, чтобы дальнейшие объекты из кластера ощущали только эффекты центра масс. Если вы захотите перебрать большее количество частиц, то вы разрушите весь смысл аппроксимации ЧД.

Кайл Канос

То есть ЧД решает ускорение

O (n \log n)

$\mathcal{O}(n\log n)$ , поэтому увеличивая

n

$n$ (это то, что вы хотите сделать) сделает его медленнее . Если вы сделаете BH на всех частицах, то вы вернетесь к

O (n^{2})

$\mathcal{O}(n^2)$ алгоритм, которого BH был разработан, чтобы избежать.

Волшебная урна с осьминогом

@KyleKanos Я понимаю, что временная сложность буквально отменена, мой главный вопрос заключается в том, будет ли результирующая физика точной или нет для проблемы с n телами. Не слишком обеспокоен временной сложностью. Важной частью алгоритма, помимо временной сложности, насколько я понял, была способность обобщать взаимодействия на больших и малых расстояниях в большой модели. Кроме того, я думаю, что это было бы O(n^2log(n))также хорошо, верно? O(n)х O(nlog(n))?

Волшебная урна с осьминогом

@KyleKanos Я в основном спрашиваю, потому что для кластерных алгоритмов уменьшения карты или многопоточных приложений верхняя граница n может действовать так, O(nlog(n))потому что задачи для каждого тела могут выполняться параллельно. Конечно, у этого есть верхний предел того, насколько высоко nможет подняться в зависимости от архитектуры. Меня просто считали, верна ли физика и логика взаимодействия частиц с учетом итерационного метода.

Кайл Канос

Да, результирующая физика будет точной, потому что вы все еще делаете сумму сил. Это было бы невероятно медленнее и не стоило бы усилий, даже при распараллеливании.

Волшебная урна с осьминогом

@KyleKanos даже немного не меняет никаких взаимодействий? Кажется, что результаты со временем становятся гораздо менее стабильными из-за того, как вычисляется ускорение для каждого тела с точки зрения их положения. Вы говорите, что мне, вероятно, лучше использовать решатель ОДУ для больших значений Nи решить настоящие проблемы с n телами - с точки зрения временной сложности и точности? Было бы упущением, если бы я не спросил вас об альтернативных алгоритмах, о которых вы знаете, вы, кажется, достаточно хорошо информированы, и это первый физический алгоритм, с которым я честно столкнулся в каком-либо качестве. Спасибо, что уделили время :).

Ответы (1)

Не могли бы вы итеративно использовать алгоритм Барнса-Хата с несколькими центральными квадрантами?

Вот 1000 частиц за 1000 шагов: i.imgur.com/SwPbG4j.mp4
Если вы перебираете все тела, разве вы не выполняете стандартный закон обратных квадратов для всех тел? В таком случае, вы только что отменили цель метода BH??
@KyleKanos, не будет ли закон обратных квадратов выполняться из другой исходной точки отсчета? Я могу быть абсолютно не прав во всех отношениях.
Весь смысл BH заключается в том, чтобы уменьшить рабочую нагрузку, необходимую для решения $a_i\sim\sum_j 1/\vert r_i-r_j\vert^2$ рассматривая кучу частиц как кластер, чтобы дальнейшие объекты из кластера ощущали только эффекты центра масс. Если вы захотите перебрать большее количество частиц, то вы разрушите весь смысл аппроксимации ЧД.
То есть ЧД решает ускорение $\mathcal{O}(n\log n)$ , поэтому увеличивая $n$ (это то, что вы хотите сделать) сделает его медленнее . Если вы сделаете BH на всех частицах, то вы вернетесь к $\mathcal{O}(n^2)$ алгоритм, которого BH был разработан, чтобы избежать.
@KyleKanos Я понимаю, что временная сложность буквально отменена, мой главный вопрос заключается в том, будет ли результирующая физика точной или нет для проблемы с n телами. Не слишком обеспокоен временной сложностью. Важной частью алгоритма, помимо временной сложности, насколько я понял, была способность обобщать взаимодействия на больших и малых расстояниях в большой модели. Кроме того, я думаю, что это было бы O(n^2log(n))также хорошо, верно? O(n)х O(nlog(n))?
@KyleKanos Я в основном спрашиваю, потому что для кластерных алгоритмов уменьшения карты или многопоточных приложений верхняя граница n может действовать так, O(nlog(n))потому что задачи для каждого тела могут выполняться параллельно. Конечно, у этого есть верхний предел того, насколько высоко nможет подняться в зависимости от архитектуры. Меня просто считали, верна ли физика и логика взаимодействия частиц с учетом итерационного метода.
Да, результирующая физика будет точной, потому что вы все еще делаете сумму сил. Это было бы невероятно медленнее и не стоило бы усилий, даже при распараллеливании.
@KyleKanos даже немного не меняет никаких взаимодействий? Кажется, что результаты со временем становятся гораздо менее стабильными из-за того, как вычисляется ускорение для каждого тела с точки зрения их положения. Вы говорите, что мне, вероятно, лучше использовать решатель ОДУ для больших значений Nи решить настоящие проблемы с n телами - с точки зрения временной сложности и точности? Было бы упущением, если бы я не спросил вас об альтернативных алгоритмах, о которых вы знаете, вы, кажется, достаточно хорошо информированы, и это первый физический алгоритм, с которым я честно столкнулся в каком-либо качестве. Спасибо, что уделили время :).

Кайл Канос · Answer 1

Достаточно хорошо известно, что на достаточно больших расстояниях сила между скоплением объектов и другим объектом по существу эквивалентна силе между центром масс скопления и другим объектом:

Ф_{я} \sim \sum_{Дж} \frac{м_{я} м_{Дж}}{| р_{я} - р_{Дж} |^{2}} ≃ \frac{м_{я} м_{малыш}}{| р_{я} - р_{ком} |^{2}}

$F_i\sim\sum_j\frac{m_im_j}{\vert r_i-r_j\vert^2}\simeq \frac{m_im_\text{tot}}{\vert r_i-r_\text{com}\vert^2}$ где

m_{tot} = \sum_{j} m_{j}

$m_\text{tot}=\sum_jm_j$ и

r_{com}

$r_\text{com}$ является центром масс

j

$j$ частицы.

Алгоритм Барнса-Хата применяет это к $n$ симуляции тел путем разбиения области на кластеры разумного размера и, таким образом, уменьшения количества эффективных тел для повторения, а не суммирования $n$ частицы $n-1$ раз. Из того, что я вижу/рассказываю, $n$ Моделирование -тела с использованием алгоритма BH достаточно точно, хотя есть алгоритмы и лучше с точки зрения скорости (например, метод быстрого мультиполя или другие гибридные схемы).

Приведет ли итеративное выполнение Барнса-Хата ко всем телам, рассматривая каждое тело по очереди как центр тяжести, к точному представлению задачи n тел, где рассматривается сумма сил гравитации всех тел? Или я неправильно понимаю, что такое алгоритм Барнса-Хата?

Ваше предложение, по сути, хочет вернуться к суммированию $n$ частицы $n-1$ раз, что было бы равносильно полному отказу от использования BH. Это будет точно, хотя, вероятно, не намного точнее, чем BH, и, безусловно, будет очень медленным.

Поэтому, задаваясь вопросом, можно ли итеративно применить BH ко всем телам, я подозреваю, что вы неправильно понимаете алгоритм BH. Весь смысл этого в том, чтобы уменьшить рабочую нагрузку, необходимую для нахождения сил, действующих на частицы на каждом временном шаге. Вы действительно не хотите увеличивать количество кластеров, вы хотите, чтобы это было сведено к минимуму, потому что выполнение $\mathcal{O}\left(n^2\right)$ обновлять каждый шаг времени очень, очень медленно.

Не могли бы вы итеративно использовать алгоритм Барнса-Хата с несколькими центральными квадрантами?

Волшебная урна с осьминогом

Волшебная урна с осьминогом

Кайл Канос

Волшебная урна с осьминогом

Кайл Канос

Кайл Канос

Волшебная урна с осьминогом

Волшебная урна с осьминогом

Кайл Канос

Волшебная урна с осьминогом

Ответы (1)

Кайл Канос

Взаимное взаимодействие NNN-частиц в декартовой плоскости.

Могу ли я перемотать гравитацию?

Расчет двумерного орбитального пути с бесконечной степенью детализации (интеграция без Эйлера)

Почему объекты в моделировании гравитации испытывают внезапные большие ускорения?

Симуляция посадочного модуля Philae отключена примерно в 3 раза

Как найти положения масс nnn в механике Ньютона?

Как идентифицировать двойные звезды в моделировании NNN-тела?

Данные о положении и скорости Солнечной системы

Методы обработки близких подходов в моделировании NNN-тела

Стабильный диск для моделирования NNN-тела