Puede la fuerza de gravedad de un cuerpo del sistema se calcula a través de la matriz de operaciones?

Question

Estoy trabajando en un proyecto de software en el trabajo en el que se calcula la "atracción gravitacional" entre los puntos 1, 2, o 3 dimensiones. Esta es una $O(n^2)$ tiempo de ejecución de la eficiencia problema, sin embargo, si me puede escribir como una secuencia de operaciones de matriz, entonces yo podría ser capaz de aprovechar la GPU para ejecutar mi simulación de lo que sería sustancialmente más rápido. Mi álgebra lineal chuletas de no mucho sin embargo. Es posible representar la masa y la posición como una matriz y calcular el neto de la fuerza de gravedad para cada elemento en la matriz como un vector?

Edit: El problema que estoy tratando de resolver esto es: Dado un vector de posición, masas, calcular el neto de la fuerza Gravitacional que cada misa experiencias de los demás elementos de la matriz. Puedo hacerlo fácilmente utilizando para bucles, pero si se puede hacer uso de matrices, a continuación, puedo aprovechar la GPU para un cálculo más rápido.

_{No-OP edit: dado masas $m_{1..n}$, las posiciones de $\underline{r}_{1..n}$. Calcular la matriz $F$, por lo que $F_{ij}=m_im_j\frac{\underline{r}_i-\underline{r}_j}{|\underline{r}_i-\underline{r}_j|^3}$. El objetivo es hacer esto con una "simple" vector/matriz de operaciones.}

Answer 1

El tamaño de la matriz se rellena con los valores de es $O(n^2)$. Por lo tanto, usted no tiene una opción para una algoritmical de optimización. Si se calculan de manera óptima, usted no puede ir por debajo de $O(n^2)$.

Pero usted tiene varias opciones para optimizaciones lineales, a saber:

• $F_{ij} = -F_{ji}$, en las Leyes de Newton (pero también las fórmulas que se muestran de la misma). Por supuesto, $F_{ii}=0$.
• La parte más compleja es calcular $\frac{\underline{r_i}-\underline{r_j}}{|\underline{r_i}-\underline{r_j}|^3}$, se calcula sólo una vez y luego se divide por $m_i$ o $m_j$ como usted desea. Nota en 2D caso de que la gravedad disminuye con la receta de la distancia y no con su plaza, esta fórmula será mucho más sencillo. Aunque no será nuestro Universo, podría ser útil para la visualización gráfica de las tareas.
• El denominador, $|\underline{r_i}-\underline{r_j}|^3$ será coordinar independiente, usted tiene que calcular sólo una vez para todos los cordinates. Sólo el nominador, $\underline{r_i}-\underline{r_j}$ depende de la realidad de coordenadas utilizado.

---

Si usted está decidido en matemáticas y como la mitad de la página largo de las fórmulas, también se puede hacer un paso más, derivar las fórmulas aún otra vez, para calcular el $\frac{da}{dt}$. Esto resulta mucho más complejas fórmulas, pero su simulación será mucho más resistente a la hora de error de cuantización. Esto podría ser particularmente útil si la precisión es importante.

---

Si la precisión no es tan importante para usted, usted puede también utilizar el Barnes-Hutt aproximación. Esto hace que su problema a través de algoritmos simplificados a $O(n\log n)$. Esencialmente, se crea un árbol de las estrellas de forma recursiva por reducir a la mitad el espacio donde están.

Esto es lo que también la fuerza de la simulación de la d3.js no:

https://www.youtube.com/watch?v=kASOnVvjeyo

Nota, aquí usted tendrá que contar con una gran cantidad de anomalías, lo peor es que las estrellas de la conmutación de la rama de árbol, resultado de una repentina de la discontinuidad en la fuerza de las direcciones.