You are currently browsing the tag archive for the ‘smoothing length’ tag.

Definimos a los kernels como funciones del tipo:

W_{ab}=W(\boldsymbol{r}_a - \boldsymbol{r}_b,h),

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

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

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

Para empezar, \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 q = \frac{r}{h}, siendo r la distancia ente las partículas, por lo que:

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 a, la función que nos da la distancia de esta a cualquier punto dentro del soporte compacto es:

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

siendo q_a lo mismo añadiendo el factor h.

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

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

= \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:

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

De la misma manera, si tenemos:

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:

\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:

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

 

Anuncios

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

Supongamos que tenemos N partículas. Si 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 h (all-pair search). La complejidad del algorítmo es 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 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 h es constante para todas las partículas. La complejidad, con un número suficientemente pequeño de partículas por celda, es O(N).

Finalmente, podemos trabajar con árboles. Los árboles permiten complejidades genéricas en búsquedas de O(N \log N) y permiten trabajar con 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).

junio 2018
L M X J V S D
« Ago    
 123
45678910
11121314151617
18192021222324
252627282930  
Anuncios