FireStats error : FireStats: Unknown commit strategy

smoothing length

You are currently browsing articles tagged smoothing length.

Definimos a los kernels como funciones del tipo:

$latex W_{ab}=W(boldsymbol{r}_a – boldsymbol{r}_b,h)$,

donde $latex a$ es la partícula en la que está centrada la función y $latex b$ es una partícula dentro del soporte compacto de la función kernel, controlado éste último por $latex h$, la smoothing length (longitud de suavizado).

En este post básicamente pretendo aclarar lo que significa $latex nabla_a W_{ab}$ cuando, por ejemplo, tenemos definido el kernel como:

$latex W(q) = alpha_D exp (-q^2)$ con $latex 0 leq q leq 2$.

Para empezar, $latex alpha_D$ es una constante de dimensionalidad, por lo que la fórmula está escrita de manera compacta y sirve para cualquier dimensión. Además, tenemos que $latex q = frac{r}{h}$, siendo $latex r$ la distancia ente las partículas, por lo que:

$latex r = |boldsymbol{r}_a – boldsymbol{r}_b| =^{(3D)} sqrt{(x_a-x_b)^2 + (y_a-y_b)^2 + (z_a-z_b)^2}$.

Si fijamos la posición de la partícula $latex a$, la función que nos da la distancia de esta a cualquier punto dentro del soporte compacto es:

$latex r_a (boldsymbol{r}) = |boldsymbol{r}_a-boldsymbol{r}| =^{(3D)} sqrt{(x_a-x)^2 + (y_a-y)^2 + (z_a-z)^2}$,

siendo $latex q_a$ lo mismo añadiendo el factor $latex h$.

Por lo tanto, en este caso tenemos, en tres dimensiones y donde $latex b$ es una partícula en una posición arbitraria $latex (x,y,z)$:

$latex nabla_a W_{ab}(q) =^{(3D)} (partial_x W_{ab}(q_a), partial_y W_{ab}(q_a), partial_z W_{ab}(q_a)) =$

$latex = alpha_D exp(-q^2) (-2q) (partial_x (q_a), partial_y (q_a), partial_z (q_a)) = alpha_D exp(-q^2) (-2q) nabla_a q_a$

donde:

$latex nabla_a q_a = frac{-1}{h r_a} (x_a-x,y_a-y,z_a-z)$.

De la misma manera, si tenemos:

$latex W(q) = alpha_D begin{cases} 1-frac{3}{2} q^2 + frac{3}{4} q^3, 0 leq q < 1\ frac{1}{4} (2-q)^3, 1 leq q < 2 \ 0, q geq 2 end{cases}$

entonces:

$latex nabla_a W_{ab}(q) = alpha_D begin{cases} (-3q + frac{9}{4}q^2) nabla_a q_a, 0 leq q < 1 \ -frac{3}{4} (2-q)^2 nabla_a q_a, 1 leq q < 2 \ 0, q geq 2 end{cases}$

Así pues:

$latex nabla W(q) = frac{d}{dq} W(q) nabla q$.

 

Tags: , , , ,

En el método SPH necesitamos conocer cual es su conjunto de vecinos de una partícula $latex a$. Este viene determinado por la smoothing length $latex h$, uno de los parámetros de las funciones kernel.

Supongamos que tenemos $latex N$ partículas. Si $latex N$ es lo suficientemente pequeño, lo único que tenemos que hacer es, para cada partícula, recorrer el resto de partículas calculando su distancia a nuestra partícula y tener en consideración solo aquellas que esten a distancia menor que $latex h$ (all-pair search). La complejidad del algorítmo es $latex O(N^2)$.

Sin embargo, cuando el número de partículas crece, y que lo ha de hacer pues en eso se basa la potencia del método, esta manera de trabajar es mejorable.

A continuación veremos algunas opciones, pero la idea general es que necesitamos tener una descomposición espacial de nuestro escenario que nos permita encontrar de manera eficiente el vecindario de cada una de nuestras partículas y que tendremos que mantener actualizada a medida que evoluciona el sistema.

Otra opción es la linked-list. Se trata de superponer una malla con un tamaño de celda $latex 2h$, de manera que, dada una partícula, solo tendremos que buscar las partículas que se encuentran en las celdas adyacentes. En C++ tenemos las clases list y vector. La primera por nombre y la segunda porque la clase vector puede crecer dinámicamente. Solo podremos utilizarlas si la $latex h$ es constante para todas las partículas. La complejidad, con un número suficientemente pequeño de partículas por celda, es $latex O(N)$.

Finalmente, podemos trabajar con árboles. Los árboles permiten complejidades genéricas en búsquedas de $latex O(N log N)$ y permiten trabajar con $latex h$ diferentes para cada partícula. En astrofísica, por ejemplo, podríamos tener un arbol binario de búsqueda, pues tenemos que simular objetos autogravitantes y necesitamos resolver un problema de n-cuerpos, que parece ser que es lo que mas tiempo de CPU consume. Para hacer esto de manera eficiente necesitamos un BST. Se trata de utilizar este mismo para realizar las búsquedas. La clase map de C++ se implementa con un arbol binario balanceado (AVL).

Existen otras estructuras de datos que permiten hacer descomposiones espaciales que podria ser interesante analizar (UB-tree, Octrees, BST, kd-tree, R-tree).

Tags: , , , , , , ,

FireStats icon Powered by FireStats