Re: FFT Multiplication on Disk?

On Sep 19, 3:12 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Sep 19, 1:24 pm, mike3 <mike4...@xxxxxxxxx> wrote:



Hi.

I was playing around with a new hard drive-based Fast Fourier
Transform multiplication program. What it's supposed to do is take two
numbers stored on disk and then multiply them using only one full-
sized FFT, and it _does the FFT on disk_, since it is too large to
fit in RAM. (instead of using a Karatsuba divide-and-conquer approach
like I did with the pi program I've been discussing here.) I thought
it would be a good idea to use Bailey's "6-step" method, as that
requires 2 sqrt(N) transforms of sqrt(N) length, which easily fit in
RAM for the sizes of N I'm considering (hence one could actually do
several of them in RAM. (On a multicore processor one could easily
parallelize those, by the way.)) can actually do. However the problem
is that this involves three in-place matrix transpositions of a square
matrix. Does anyone know of an efficient algorithm to do those? That's
my big chokepoint insofar as the Matrix-based 6-Step Fft goes.

Instead of transposing the matrix, just iterate over the matrix in a
transposed manner with a function that permutes the indexes supplied.

That would take a large amount of disk seeking, which is very slow, as
it accesses the data in a highly non-sequential way.

.

Relevant Pages

  • Re: FFT Multiplication on Disk?
    ... Transform multiplication program. ... numbers stored on disk and then multiply them using only one full- ... RAM for the sizes of N I'm considering (hence one could actually do ... is that this involves three in-place matrix transpositions of a square ...
    (comp.programming)
  • FFT Multiplication on Disk?
    ... Transform multiplication program. ... numbers stored on disk and then multiply them using only one full- ... sized FFT, and it _does the FFT on disk_, since it is too large to ... RAM for the sizes of N I'm considering (hence one could actually do ...
    (comp.programming)
  • Baileys "two pass" FFT algorithm question
    ... I was working on an implementation of Bailey's "two pass" FFT ... Otherwise you need an EXPENSIVE (i.e. disk intensive ... Is there a version of the algorithm that would operate on a ...
    (comp.programming)