Use FMM or FFT for low-discrepancy sample of atoms?

  • Context: Graduate 
  • Thread starter Thread starter 1a2
  • Start date Start date
  • Tags Tags
    Atoms Fft
Click For Summary
SUMMARY

The discussion centers on optimizing the calculation of atomic interactions in a Master's thesis project using algorithms like Fast Multipole Method (FMM), Fast Fourier Transform (FFT), or Multilevel FMM. The goal is to reduce computational complexity from O(M*N) to O(M+N) by leveraging low-discrepancy sampling techniques. The user expresses uncertainty about the applicability of FFT due to its typical use with equispaced points, while also questioning how FMM or Multilevel FMM would handle the distribution of atoms. Clarification on the specific interactions and their distribution is sought to guide the choice of algorithm.

PREREQUISITES
  • Understanding of low-discrepancy sampling techniques
  • Familiarity with Fast Multipole Method (FMM) and its applications
  • Knowledge of Fast Fourier Transform (FFT) and its limitations
  • Basic concepts of computational complexity in algorithms
NEXT STEPS
  • Research the implementation and advantages of Fast Multipole Method (FMM)
  • Explore the use cases and limitations of Fast Fourier Transform (FFT) in non-time series data
  • Investigate Multilevel FMM for optimizing large-scale atomic interactions
  • Study low-discrepancy sequences and their impact on computational efficiency
USEFUL FOR

Researchers, computational physicists, and graduate students working on atomic simulations or optimization of numerical methods in scientific computing.

1a2
Messages
20
Reaction score
0
To complete my Master's thesis, I am working on a problem that deals with an arrangement of initial atoms, and their positions are then changed according to a pseudo-random number generator with low discrepancy. My advisor told me that instead of computing the interactions between the atoms for each sample (which would take M*N), I could use an algorithm to make it faster (M+N). He told me to just google it

I'm not sure what algorithm can do this. I'm guessing either the FMM, FFT, or Multilevel FMM would be the algorithm. I thought FFT might work since its used for equispaced points, but we are not dealing with time/frequency here. And I don't see how FMM or Multilevel FMM deal with equispaced points.

Any ideas?
 
What do you want to calculate? "The interactions" is a very vague description.

How does their distribution look like?
 

Similar threads

Graduate Editing in Freq domain and applying inverse FFT
  • · Replies 6 ·
Replies
6
Views
2K
Python How can I integrate sinusoids in python code using FFT?
  • · Replies 3 ·
Replies
3
Views
3K
Power Spectral Density Confusion
  • · Replies 4 ·
Replies
4
Views
2K
How to use the window functions on a signal in MATLAB?
  • · Replies 2 ·
Replies
2
Views
3K
Fourier Transform - Completely Flustered About Recursive FFT
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Understanding Fourier Transforms
  • · Replies 1 ·
Replies
1
Views
2K
C# Missing samples recovery with FFT in C#
  • · Replies 2 ·
Replies
2
Views
3K
Trouble understanding fft norm axis sampling frequency etc
  • · Replies 2 ·
Replies
2
Views
3K
Fft and normalized vs real frequency question
  • · Replies 3 ·
Replies
3
Views
6K
Graduate Losing energy during Fast Fourier Transform
  • · Replies 2 ·
Replies
2
Views
2K