Two-dimensional fast transforms applied to memory limited disk operating computers

Area of Science:

• Computer Science
• Algorithm Analysis

Background:

• Two-dimensional transform algorithms require substantial memory, limiting their use on small machines.
• Large datasets (N^2) exceed the core memory capacity of many devices.

Purpose of the Study:

• To develop a practical two-dimensional transform algorithm for resource-constrained environments.
• To reduce the computational and data access overhead of existing methods.

Main Methods:

• The study expands upon fast one-dimensional transform algorithms.
• Data is stored in N disk records, enabling sequential one-dimensional computations.

Main Results:

• The proposed method reduces disk accesses from N(N + 3) to 2N log2N.
• The one-dimensional procedure is activated only N times, compared to 2N previously.

Conclusions:

• The enhanced algorithm offers a practical solution for implementing two-dimensional transforms on small machines.
• Significant improvements in disk access efficiency are demonstrated.