/* FMM.java * * You may use and distribute under the terms of either the GNU Lesser * General Public License, either version 2 of the license or, * at your choice, any later version. Alternatively, you may use and * distribute under the terms of the XPL. * * See the LICENSE.lgpl and LICENSE.xpl files for the specific terms of * the licenses. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the README * file for more details. * */ /* * Written by Kimmo Wideroos */ /* an implementation of fast multipole method * * references: * * 1.) * "A fast algorithm for particle simulations," * by L. Greengard and V. Rokhlin, * Journal of Computational Physics 72 (1987), 325-348 * * 2.) * "A Parallel Hashed Oct-Tree N-Body Algorithm," * by Michael S. Warren and John K. Salmon * Supercomputing '93, pages 12 - 21. * IEEE Computer Society, Los Alamitos, 1993 */ package org.gzigzag.map; import java.util.*; import org.gzigzag.test.TestFMM; public class FMM { // n! = fact[n] static public float fact[] = new float[100]; static { fact[0] = 1; for(int i=1; i<100; i++) fact[i] = fact[i-1] * i; } // binomial coefficient public static float bincof(int l, int k) { return fact[l] / (fact[k] * fact[l-k]); } public interface FMMStructure { FMMCell[] get(int level); FMMCell[] getInteractionList(FMMCell fc); FMMCell[] getNeigbourhood(FMMCell fc); FMMCell[] getChildren(FMMCell fc); FMMParticle[] getAllParticles(); FMMParticle[] getParticles(FMMCell fc); FMMParticle getParticle(float x, float y); int nLevel(); int nTerms(); void empty(); FMMParticle makeParticle(float x, float y, int[] q); void add(FMMParticle fp); void add(float x, float y, int[] q); void add(float x, float y, int q); } private static float EPSILON = (float)0.000000001; private static Complex ZERO = new Complex((float)0.0); FMMStructure fmms; private int p; private int n; private int qind = 0; private float weight = (float)1.0; private boolean augm = false; public FMM(FMMStructure fmms) { this.fmms = fmms; this.p = fmms.nTerms(); this.n = fmms.nLevel(); } // power serie of 'z' (^0...^n-1) public static Complex[] zpow(Complex z, int n) { // z0[k] = pow(child_center, k) Complex[] z0 = new Complex[n]; z0[0] = new Complex((float)1.0); z0[1] = new Complex(z); for(int i=2; i=0; l--) { fcs = fmms.get(l); for(ibox=0; ibox=0; l--) { fcs = fmms.get(l); for(ibox=0; ibox