Dear GRASS Developers

I'm Stefano De Paoli PhD student from the University of Trento (Italy).

In 2004 I've started a research on the copyright issues of GRASS,

which will end up in my doctoral thesis. This should sound new for

many of you. Nonetheless the people working on GRASS in Trento

and some other people in the GRASS community know me quite well.

Especially Markus has helped and sustained my research since its

beginning.

Markus has suggested me to post this email to the list.

Maybe the mail is a bit long, but I hope you could enjoy read it. I

also apologize for my english.....

Recently my attention has been focused on the elimination of the

Numerical Recipes (NR) algorithms from GRASS code,

http://grass.itc.it/pipermail/grass5/1999-December/012698.html

In particular my attention has been focused on the Fast Fourier

Transform (FFT) algorithm.

The story is the following:

Several GRASS modules uses the FFT ( e.g. i.fft() - i.ifft() )

The NR-FFT implementation was fully integrated into the GRASS libraries.

The NR-FFT was deprecated due to incompatibility with the GPL.

Then it was decided to use a library called FFTW (under GPL). The FFTW

of course introduced a dependency, but this is not the issue. The

decision to use FFTW introduced the following choices:

requires either that existing applications are re-written to use the FFTW interface, > or that we add code to convert between the existing and FFTW interfaces (which > might introduce inefficiency; I don't know the semantics of the existing interface, > so I can't tell).

from a mail by Glynn Clements

http://grass.itc.it/pipermail/grass5/2001-August/003067.html

The latter choice was implemented and basically it works in this way -

but I may be mistaken, just sociologist :-), please correct me in

case:

i.fft() --> interface (fft.c) --> FFTW

FFTW--> interface (fft.c) --> i.fft()

The very issue is that i.fft() has mantained the old data structure

(that comes from NR FTT): two separated arrays for the real and

immaginary parts of the Fourier Transform.

FFTW uses instead an unique array of complex numbers (interleaved real

and imaginary).

So the transformation from the two data structures requires a double

allocation of memory which is done by the fft.c interface.

Not to mention that the NR-FFT implementation (and still the i.fft() )

requires the two arrays (real and imaginary) to be power of two. So if

your input raster map is 200x400 you have to process it at 256x512,

and so on.

The FFTW has not such constrain and the array of complex numbers

hasn't to be power of two.

So a second problem is then that you have to allocate more memory than

the one required by the FFTW library (is that correct?)

According the above description:

This is rather inefficient to say the least.

[...]

The net result of this is that code which uses fft() is wasting a lot

of memory. In the worst case, it can use almost 8 times as much memory

as is actually necessary. Padding each dimension to the next power of

2 can result in a near-fourfold increase, while storing two copies

(the separate real/imaginary arrays plus the interleaved array)

doubles it again.

from a mail by Glynn Clements

http://grass.itc.it/pipermail/grass5/2005-May/018172.html

see also http://grass.itc.it/pipermail/grass5/2004-June/014714.html

for a further description of the problem.

Now my questions.

Given this problem I started to wonder whether this example fit with

the issue that Free Software is primarly about so called "freedom" and

not about efficency. As many many Open Source advocates usually say.

Which means that an inefficient solution has been introduced in GRASS

in order to maintain the integrity of the GPL license.

I had a mail exchange with Markus about this issue, and I suggested to

him that the substitution of the Numerical Recipes FFT implementation

in GRASS ended up with a not efficient solution.

Probably Markus won't accept my conclusion :-))

and maybe so do other developers

Of course one solution may be to rewrite the i.fft() so that it can

access the FFTW directly without using the fft.c interface. But given

the fact that this has not yet been done, the inefficiency still

remains.

What do you think GRASS developers?

Is this an example of the fact that Free Software is primarly about

freedom than about efficiency?

Would you agree with my conclusion?

Stefano