Metodo efficiente per la valutazione della somma della convoluzione - algoritmo, fft, geometria computazionale, convoluzione, espressioni matematiche

Problema Dati N punti a 3 dimensioni che sono {$ p_1, p_2, .., p_n $} dove $ p_i = (x_i, y_i, z_i) $. Devo trovare il valore della formula

per alcuni dati interi costanti P, Q, R, S. tutti i numeri sono compresi tra 1 e M (= 100).

Ho bisogno di un metodo efficiente per il calcolo di questa formula

Si prega di dare qualche idea su come ridurre la complessità meglio di $ O (n ^ 2) $

risposte:

Supponendo che tutte le coordinate siano comprese tra 1 e 100, puoi farlo tramite:

1. Calcola l'istogramma 3d di tutte le operazioni di punti O (100 * 100 * 100).

2. Usa FFT per calcolare la convoluzione degli istogrammi lungo ciascuno dei 3 assi

Ciò si tradurrà in un istogramma 3d di vettori 3d. È quindi possibile scorrere su questo istogramma per calcolare il valore desiderato.

Il punto principale è il calcolo di una convoluzione dil'istogramma dei valori calcola l'istogramma delle differenze a coppie di tali valori. Questo può anche essere usato per calcolare un istogramma di somme di valori in modo simile.

Il tuo problema sembra un potenziale problema di particelle (il tipo che hai in elettrodinamica, per esempio), dove devi trovare un "potenziale" nel luogo (x_j, y_j) sommando tutti i contributi elementari dal i-th particelle.

L'algoritmo veloce specifico per questa classe diproblemi è il metodo Multipole veloce. Cerca questa parola chiave, ma devo avvertirti che non è affatto semplice da capire o implementare. È necessario un forte background matematico.