Re: FFT Multiplication on Disk?

On Sep 20, 9:17 am, c...@xxxxxxxx (Richard Harter) wrote:
On Wed, 19 Sep 2007 23:37:04 -0700, mike3 <mike4...@xxxxxxxxx>
wrote:



On Sep 19, 5:55 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
mike3 <mike4...@xxxxxxxxx> writes:
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?

Here's one paper on the topic:http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/8931/28260/0126...
--
"J'avais trouv'e ma religion :
rien ne me parut plus important qu'un livre.
La biblioth`eque, j'y voyais un temple."
--Jean-Paul Sartre

That looks like it's going to cost me a good sum of MONEY
to get that paper. I don't have lots of that nice green stuff on
hand given my current financial situation, unfortunately.

A simple alternative that you can roll on your own is to
recursively partition the transposition. Here is the idea:
Suppose we have a matrix that looks like this:

A B
M = C D

where M is 2Nx2N and A, B, C, and D are all NxN. Transpose each
component separately and then swap A and B. If you do things
soothly the number of cache misses drops sharply.

Richard Harter, c...@xxxxxxxxxxxx://home.tiac.net/~cri,http://www.varinoma.com
But the rhetoric of holistic harmony can generate into a kind of
dotty, Prince Charles-style mysticism. -- Richard Dawkins

The problem though is that it is very non-sequential. Is
this as close to sequential as one can get it, or is there
better? I want to minimize the amount of disk operations,
especially seeks, as much as possible. It's the _disk_
part that's the real chokepoint here.

.

Relevant Pages

  • Re: FFT Multiplication on Disk?
    ... transpositions of a square matrix. ... efficient algorithm to do those? ... The third ingredient in spartan pasta sause is corn syrup. ...
    (comp.programming)
  • Re: FFT Multiplication on Disk?
    ... transpositions of a square matrix. ... efficient algorithm to do those? ... I asked you earlier about authentic tasks with your trees and ...
    (comp.programming)
  • Re: FFT Multiplication on Disk?
    ... transpositions of a square matrix. ... efficient algorithm to do those? ... Richard Harter, cri@xxxxxxxx ...
    (comp.programming)
  • Re: FFT Multiplication on Disk?
    ... transpositions of a square matrix. ... efficient algorithm to do those? ... "J'avais trouv'e ma religion: ...
    (comp.programming)