You are currently browsing the tag archive for the ‘kernel’ 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.

 

Construimos una malla de 100\times 100 puntos de nuestros kernels en 2D. La primera animación contiene el kernel Gaussiano en el primer frame, el cúbico en el segundo, el cuártico en el tercero y el quíntico en el último:

En la siguiente animación mostramos los puntos de la primera derivada de los kernels:

Finalmente, la animación con puntos de las segundas derivadas de los kernels de nuestra aplicación:

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).

Existen diferentes posibilidades a la hora de definir una función kernel:

  1. Gaussiana [Gingold & Monaghan, 1977]:W(r,h) = \alpha_D \cdot e^{-q^2} con 0 \leq q \leq 2 donde q=\frac{r}{h}, r es la distancia entre dos partículas determinadas y \alpha_D, el factor dimensional, que es \frac{1}{\pi h^2} en dos dimensiones y \frac{1}{\pi^{\frac{3}{2}} h^3} en tres.
  2. Cuadrática [Gingold & Monaghan, 1977]: \alpha_D (\frac{3}{16} q^2 - \frac{3}{4} q + \frac{3}{4}) con 0 \leq q \leq 2 y donde \alpha_D es \frac{2}{\pi h^2} en 2D y \frac{5}{4 \pi h^3} en 3D.
  3. B-spline cúbico [Monaghan & Lattancio, 1985]W(r,h) = \alpha_D \begin{cases} 1 - \frac{3}{2} q^2 + \frac{3}{4} q^3 ,& \mbox{if } 0 \leq q \leq 1 \\ \frac{1}{4}(2-q)^3 ,& \mbox{if } 1 < q \leq 2 \\ 0 ,& \mbox{if } q > 2\end{cases} con \alpha_D = \frac{10}{7 \pi h^2} en dos dimensiones y \frac{1}{\pi h^3} en 3 dimensiones.
  4. Quíntica: W(r,h) = \alpha_D (1-\frac{q}{2}^4)(2q + 1) con 0 \leq q \leq 2 y \alpha_D = \frac{7}{4 \pi h^2} en 2D y \frac{7}{8 \pi h^3} en 3D.

Pensando en posibles implementaciones, parece lógico utilizar una classe abstracta Kernel de la que heredaran las anteriores implementando sus métodos, de manera que, las posibles clases que llamen a la misma puedan hacerlo siempre de la misma manera independientement de cual estemos utilizando.

En el artíclo [Gingold & Monaghan, 1977] se introducen

La función kernel, W(\vec{r}-\vec{r'},h), es una función que permite interpolar los valores de cualquier propiedad del fluido en función del valor de las partículas del entorno. Su papel es similar al de los diferentes esquemas de diferencias en el ámbito de las Diferencias Finitas o las funciones de forma en los Elementos Finitos.

Existen diferentes funciones kernel: Gaussiana, cuadrática, spline cúbico, quíntica, etc.

La función kernel debe cumplir:

  1. Positiva: W(r-r',h) \geq 0 dentro del dominio.
  2. Soporte compacto: W(r-r',h) = 0 fuera del dominio.
  3. Normalizada: \int W(r-r',h) dr' = 1.
  4. Comportamiento de función delta: \lim_{h \rightarrow 0} W(r-r',h) dr' = \delta(r-r').
  5. Monotona decreciente.

Para derivar, tomamos la derivada analítica de la suma aproximada. De esta manera, como la derivada de la función kernel es conocida, no necesitamos diferencias finitas y el conjunto de ecuaciones PDE pasa a ser ODE.

\nabla f(\vec{r}) = \sum_b \frac{m_b}{\rho_b} f_b W(\vec{r}-\vec{r'},h)

En el artículo  [Gingold & Monaghan, 1977] se presenta por primera vez el método Smoothed Particle Hydrodynamics. Los autores, originalmente, buscaban un método que permitiera tratar problemas en astrofísica asimétricos (sin simetría esférica, sin simetría axial, etc.) . En estos casos, los métodos de diferencias finitas no se adaptan bien, pues requieren elevar el número de puntos en la malla para seguir con la precisión deseada su evolución, lo cual complica enormemente la evolución de las integrales múltiples.

Lo que pensaron es utilizar la descripción Lagrangiana del flujo del fluido que centra su atención en los elementos del fluido. En la discretización, estos elementos se mueven siguiendo las leyes de Newton con fuerzas debidas a los gradientes de presión y a otras fuerzas de cuerpo como la gravedad, rotación o magnéticas. ¿Qué método utilizar para determinar las fuerzas que actuan en un momento determinado sobre un elemento de fluido?

Para empezar, para elementos de fluido de igual masa, el número de elementos por unidad de volumen debe ser proporcional a la densidad. Además, sin ningún tipo especial de simetría, la posicion de los elementos será aleatoria de acuerdo con la densidad. Para recuperar la densidad de la distribución conocida de los elementos es equivalente a recuperar una distribución de probabilidad a partir de una muestra. Existen dos métodos para conseguir esto que funcionan bien con problemas de fluidos: el smoothing kernel method y  la técnica del spline delta. Ambos métodos se pueden pensar como la aproximación de una integral por el procedimiento de Monte Carlo.

agosto 2017
L M X J V S D
« Jul    
 123456
78910111213
14151617181920
21222324252627
28293031