Méthode efficace pour la convolution comme évaluation de la somme - algorithme, fft, géométrie computationnelle, convolution, expressions mathématiques

Problème Soit N points tridimensionnels qui sont {$ p_1, p_2, .., p_n $} où $ p_i = (x_i, y_i, z_i) $. Je dois trouver la valeur de la formule

pour certains entiers constants donnés P, Q, R, S. tous les nombres sont compris entre 1 et M (= 100).

J'ai besoin d'une méthode efficace pour le calcul de cette formule

Veuillez donner une idée de la façon de réduire la complexité mieux que $ O (n ^ 2) $

Réponses:

En supposant que toutes les coordonnées soient comprises entre 1 et 100, vous pouvez le faire via:

1. Calculez l'histogramme 3D de tous les points O (100 * 100 * 100) opérations.

2. Utilisez la FFT pour calculer la convolution des histogrammes le long de chacun des 3 axes

Cela se traduira par un histogramme 3D de vecteurs 3D. Vous pouvez ensuite parcourir cet histogramme pour calculer la valeur souhaitée.

Le point principal est que le calcul d'une convolution del'histogramme des valeurs calcule l'histogramme des différences par paire de ces valeurs. Cela peut également être utilisé pour calculer un histogramme de sommes de valeurs d'une manière similaire.

Votre problème ressemble à un problème de potentiel de particules (le type que vous avez en électrodynamique par exemple), où vous devez trouver un "potentiel" à l'emplacement (x_j, y_j) en additionnant toutes les contributions élémentaires i-th particules.

L'algorithme rapide spécifique à cette classe deproblèmes est la méthode multipolaire rapide. Recherchez ce mot-clé, mais je dois vous avertir qu'il n'est en aucun cas simple à comprendre ou à mettre en œuvre. Une solide formation en mathématiques est nécessaire.