Related Experiment Videos
Discrete Fourier transform in arbitrary dimensions by a generalized Beevers-Lipson algorithm
1Laboratory of Crystallography, University of Bayreuth, Germany. smash@uni-bayreuth.de
Summary
A new algorithm generalizes the Beevers-Lipson procedure for evaluating Fourier maps in n-dimensional space. This method offers a single, dimension-independent computer code with computational complexity scaling as N log(N).
Area of Science:
- Crystallography
- Computational Science
- Data Analysis
Background:
- The Beevers-Lipson procedure provides an economical method for evaluating Fourier maps in 2D and 3D.
- Direct generalization to n-dimensional space requires dimension-specific code and complex nested loops.
- This limitation hinders efficient analysis of complex crystallographic data.
Purpose of the Study:
- To develop a generalized algorithm for n-dimensional Fourier map evaluation.
- To create a single, adaptable computer code for arbitrary dimensions.
- To improve the efficiency of crystallographic data analysis.
Main Methods:
- Generalization of the Beevers-Lipson procedure to n-dimensional space.
- Development of a dimension-variable algorithm.
- Analysis of computational complexity scaling.
Main Results:
- A novel algorithm for n-dimensional Fourier transforms is proposed.
- The algorithm uses a single piece of computer code for any dimension.
- Computational complexity is N log(N), independent of transform dimension.
Conclusions:
- The proposed algorithm offers a significant advancement for evaluating Fourier maps in higher dimensions.
- It provides a unified and efficient computational approach.
- Applications include quasicrystal analysis and the maximum-entropy method for aperiodic crystals.