Fast summation on rectangular cuboids with arbitrary periodicity in the DMK framework

Resumen Técnico: Sumación Rápida en Cuboides Rectangulares con Periodicidad Arbitraria en el Marco de Trabajo DMK

Planteamiento del Problema
El artículo aborda la evaluación eficiente de potenciales periódicos definidos por la sumatoria:
$$u_{DP}(x_\beta) = \sum_{\alpha=1}^{N_s} \sum_{p \in P_{DP}} K(x_\beta - x_\alpha + p)\rho_\alpha$$
donde $K$ es un núcleo singular y de decaimiento lento (por ejemplo, núcleos electrostáticos o de flujo de Stokes), y $N_s$ fuentes y $N_t$ objetivos residen en un cuboide rectangular $\Omega = [0, L_1) \times [0, L_2) \times [0, L_3)$, y $P_{DP}$ representa las imágenes periódicas en $D$ direcciones ($D \in \{0, 1, 2, 3\}$).

La evaluación directa es $O(N^2)$. Aunque los métodos de sumación de Ewald y Particle-Mesh Ewald (PME) aceleran esto para dominios cúbicos triplemente periódicos, enfrentan desafíos con:

1. Periodicidad Reducida: La combinación de interacciones periódicas con comportamientos de espacio libre en direcciones no periódicas introduce integrales de Fourier singulares o con picos pronunciados.
2. Altas Relaciones de Aspecto: Los métodos estándar basados en FFT sobre mallas uniformes se vuelven ineficientes o requieren un exceso de puntos de malla para cuboides rectangulares con altas relaciones de aspecto.
3. Adaptabilidad: Los métodos basados en árboles (como FMM) manejan bien los puntos agrupados, pero tienen dificultades con la periodización eficiente en geometrías no cúbicas.

Metodología
Los autores extienden el marco de trabajo de División de Núcleos Multinivel en el Espacio Dual (DMK) a cuboides rectangulares con periodicidad arbitraria ($D=1, 2, 3$). El método se basa en una descomposición multinivel del núcleo $K(x) = K_M(x, \nu_0) + \sum K_{D\ell}(x) + K_R(x, \nu_0/2^L)$, separando la interacción en una parte de campo lejano suave y partes de campo cercano localizadas.

La extensión involucra tres componentes técnicos primarios:

1. Teselado Cúbico y Bosque de Octrees:

   • Para manejar las interacciones localizadas (núcleos de diferencia y residual), el dominio primario $\Omega$ se tesela con cubos de lado $L_{min}$ (la longitud periódica más corta).
   • Si $L_2$ o $L_3$ no son múltiplos enteros de $L_{min}$, el dominio se embebe en un dominio extendido más grande $\Omega_{ext}$ mediante el uso de padding.
   • Se construye un bosque de octrees, con un octree por cada tesela. La periodicidad se impone en las listas de vecinos de estos árboles para las direcciones exactamente teseladas.
   • Esto permite que las partes localizadas de la sumatoria se evalúen utilizando las pasadas ascendentes/descendentes estándar de DMK con modificaciones mínimas, tratando las imágenes periódicas como vecinos locales dentro de la estructura teselada.

2. Tratamiento en el Espacio de Fourier del Campo Lejano de Nivel Raíz:

   • La contribución suave del nivel raíz ($u_{far}$) se evalúa en el espacio de Fourier.
   • Triplemente Periódico ($D=3$): Se evalúa como una serie de Fourier discreta.
   • Periodicidad Reducida ($D=1, 2$): La sumatoria sobre números de onda discretos en las direcciones libres se reemplaza por la integración sobre números de onda continuos.
   • Núcleos Truncados: Para manejar las singularidades en $k=0$ y los picos agudos en números de onda pequeños en las direcciones libres, los autores emplean núcleos truncados. Estos modifican los símbolos de Fourier de los núcleos para que estén acotados en el origen, permitiendo el uso de la regla del trapecio para obtener precisión espectral sin requerir un exceso de puntos de malla. Esto unifica el tratamiento de todas las periodicidades.

3. Aceleración por FFT para Altas Relaciones de Aspecto:

   • Para cuboides con altas relaciones de aspecto (por ejemplo, $L_3 \gg L_1$), el número de teselas de nivel superior $M$ se vuelve grande, lo que hace que la evaluación directa de la suma de campo lejano sea $O(M^2)$.
   • Los autores aprovechan la estructura de producto tensorial de las mallas de fuentes y objetivos para acelerar la computación del factor de estructura y la evaluación final del potencial.
   • Al reformular las sumas como Transformadas Discretas de Fourier (DFT) de 1D o 2D sobre los índices de las teselas, la complejidad de la evaluación de campo lejano se reduce de $O(M^2)$ a $O(M \log M)$ utilizando FFT rápidas.

Contribuciones Clave

• Generalización de DMK: Extiende el marco de trabajo DMK de dominios cúbicos totalmente periódicos a cuboides rectangulares con periodicidad $D=1, 2, 3$.
• Estrategia de Periodización Unificada: Propone un método donde la periodicidad afecta solo al nivel raíz del campo lejano y al envoltorio de las interacciones de vecinos cercanos en el dominio teselado, dejando la estructura jerárquica del árbol mayormente intacta.
• Regularización de Núcleos Truncados: Introduce el uso de núcleos truncados para regularizar las integrales de Fourier singulares en las direcciones libres, permitiendo un esquema de discretización unificado para todos los tipos de periodicidad.
• Aceleración por Relación de Aspecto: Desarrolla una evaluación acelerada por FFT para la suma del nivel raíz en geometrías de alta relación de aspecto, mitigando la penalización de costo asociada con los dominios no cúbicos en los métodos basados en árboles.

Resultos
Experimentos numéricos demuestran que:

• La estrategia de periodización añade solo un pequeño costo adicional (overhead) al algoritmo DMK original de espacio libre.
• El costo computacional por fuente permanece casi independiente de la relación de aspecto cuando se mantiene constante la densidad de puntos.
• El método alcanza la precisión deseada para una amplia gama de relaciones de aspecto y periodicidades.
• El uso de núcleos truncados resuelve con éxito las singularidades en las integrales de Fourier para la periodicidad reducida, produciendo discretizaciones del trapecio de convergencia rápida.

Significancia
El artículo afirma proporcionar un marco robusto para aplicar el método DMK a problemas con periodicidad mixta en cuboides rectangulares. Al desacoplar la periodización de la lógica central del árbol y utilizar núcleos truncados, el método se extiende naturalmente a otros núcleos no oscilatorios donde existe una división de núcleo. Esto aborda una brecha específica en los métodos existentes basados en árboles, que a menudo pierden eficiencia o requieren soluciones lineales complejas cuando se aplican a dominios rectangulares de alta relación de aspecto con condiciones de contorno periódicas. El trabajo cierra la breancia entre la eficiencia de los métodos de Ewald basados en FFT para problemas periódicos y la adaptabilidad de los métodos basados en árboles para geometrías no cúbicas con puntos agrupados.