partitioned fft convolution


    Dec 24 2007 | 4:54 pm
    i've been working on a patch to do this for a couple of weeks now, and it's turning out to be more complicated than i expected - i've implemented it in C before, but with a signal processing structure rather than procedural code it's kind of awkward. the thing is, i'm very surprised no such patch or external already exists for this.. maybe it does, but i haven't been able to find one anywhere. i would have thought it would be a very common and useful effect.
    can anyone point me to something that already exists, or anything else that might be useful?

    • Dec 24 2007 | 7:48 pm
      gizmo~
    • Dec 24 2007 | 8:19 pm
      hmm, not sure how gizmo~ is relevant
    • Dec 24 2007 | 9:35 pm
      oops! wrong fft
      try this
      save this as aConvolve~:
      then use it like this:
    • Dec 25 2007 | 11:20 am
      On 24 Dec 2007, at 17:54, pete wrote:
      > . the thing is, i'm very surprised no such patch or external > already exists for this.. maybe it does, but i haven't been able to > find one anywhere. i would have thought it would be a very common > and useful effect. > > can anyone point me to something that already exists, or anything > else that might be useful?
      thomas resch, one of our students here at ESB in basel has done a partitioned convolution external for maxmsp as part of his diploma. first version was still a little buggy, but i think meanwhile he managed to improved the overall stability and has done a UB version (no windows i believe). you can find it at http://www.zippernoise.net/
      volker.
    • Dec 25 2007 | 11:51 am
      On 24 Dec 2007, at 22:36, don malone wrote:
      > oops! wrong fft > > try this > > save this as aConvolve~: > #P window setfont Times 10.; > #P window linecount 1; > #P comment 9 217 170 1310730 convolution of input 1 with input 2.; > #P window setfont "Fixedwidth Serif" 10.; > #P newex 64 116 27 1441802 *~; > #P newex 12 116 27 1441802 *~; ...
      this won't give you linear convolution, which i think pete is interested in. since you are ignoring the phases of the second signal i would rather call it 'cross synthesis'. this might even work better if some sort of spectral flattening would be imposed on one of the input spectrums. just my 2 'rappen' vb
    • Dec 25 2007 | 4:44 pm
    • Dec 27 2007 | 8:48 pm
      I think that although partitioned fft convolution is possible with max objects only, it is impractical in terms of CPU usage.
      I've been considering writing a C external for this for a month or so (I know there are one or two others already, but for various reasons I'd prefer to write my own). Anyway, this thread convinced me to try a max only version. However, the cost of simply doing the complex multiplication is higher with msp objects than vanilla c code - far higher again than the purpose written apple routines in the accelerate framework (sorry pc guys). However, I found the main problem is with simply moving the data around in buffers etc.... The cost of index~ objects is prohibitively expensive making it non-viable. I reckon most of your CPU would go on a medium length stereo impulse (10 secs or so), which on a 2.4 GHz machine is not what you want,,,,,
      So I didn't reach a final product - it wasn't worth it - plus although the processing itself is quite straightforward partitioning the impulse and doing the ffts on it is a bit of a pain (by no means impossible - but slightly unwieldy.
      So - I'd advise an external-based approach. If you can hack the limitation of machines with SSE instructions only then I'd advise vectorising the code - I think you could be looking at a speed increase of 2-4 times although I haven't tested that yet. For stereo you might like to offset your FFTs (left and right) to give more even cpu usage - the delay will remain the same - you'll just have more efficient use of resources. At some point I'll have an external for zero-latency partitioned convolution on mac that I'd be happy for someone to port / recompile for windows, although they'd have to deal with the fft stuff as I'll be using the apple routines. There is unfortunately no time-frame on this though as it's not a priority, so if you have code you're happy with I'd advise using that...
      If you need any help with the max/msp C API I'm pretty familiar with it - if the code you have is realtime then the port to an external could probably be done very quickly ..
      Regards,
      Alex
    • Dec 27 2007 | 10:49 pm
      Quote: AlexHarker wrote on Thu, 27 December 2007 13:48 ---------------------------------------------------- > > I think that although partitioned fft convolution is possible with max objects only, it is impractical in terms of CPU usage. > > I've been considering writing a C external for this for a month or so (I know there are one or two others already, but for various reasons I'd prefer to write my own). Anyway, this thread convinced me to try a max only version. However, the cost of simply doing the complex multiplication is higher with msp objects than vanilla c code - far higher again than the purpose written apple routines in the accelerate framework (sorry pc guys). However, I found the main problem is with simply moving the data around in buffers etc.... The cost of index~ objects is prohibitively expensive making it non-viable. I reckon most of your CPU would go on a medium length stereo impulse (10 secs or so), which on a 2.4 GHz machine is not what you want,,,,, > > So I didn't reach a final product - it wasn't worth it - plus although the processing itself is quite straightforward partitioning the impulse and doing the ffts on it is a bit of a pain (by no means impossible - but slightly unwieldy. > > So - I'd advise an external-based approach. If you can hack the limitation of machines with SSE instructions only then I'd advise vectorising the code - I think you could be looking at a speed increase of 2-4 times although I haven't tested that yet. For stereo you might like to offset your FFTs (left and right) to give more even cpu usage - the delay will remain the same - you'll just have more efficient use of resources. At some point I'll have an external for zero-latency partitioned convolution on mac that I'd be happy for someone to port / recompile for windows, although they'd have to deal with the fft stuff as I'll be using the apple routines. There is unfortunately no time-frame on this though as it's not a priority, so if you have code you're happy with I'd advise using that... > > If you need any help with the max/msp C API I'm pretty familiar with it - if the code you have is realtime then the port to an external could probably be done very quickly .. > > Regards, > > Alex ----------------------------------------------------
      really useful reply, thanks. i've started down the external route now - have decided i'm going to base it on the Pd external partconv~ by Ben Saylors (i hope he doesn't mind..) which uses the fftw library (http://www.fftw.org/). sounds like between us we'll sort out mac and windows versions. is it worth standardising the interface? i was thinking of just keeping it simple as possible, like:
      [conv~ buffername partitionsize]
      with a set message to change the buffer~ being used.
      i don't know anything about vectorization though, what does it involve?
    • Dec 28 2007 | 9:08 am
      On 27 Dec 2007, at 21:48, Alex Harker wrote:
      > At some point I'll have an external for zero-latency partitioned > convolution...
      hm, Lake dsp has a patent on this one, no? or are you thinking about something new/different?
    • Dec 28 2007 | 11:48 am
    • Dec 28 2007 | 12:02 pm
      I've managed to confirm from a uk government website that the European patent has been revoked - so as far as I'm aware - in my part of the world I'm free to write and distribute my external.....
      Alex
    • Dec 28 2007 | 1:07 pm
      On 28 Dec 2007, at 13:02, Alex Harker wrote:
      > I've managed to confirm from a uk government website that the > European patent has been revoked - so as far as I'm aware - in my > part of the world I'm free to write my external.....
      sounds like good news - thanks for letting us know!
      volker.
    • Dec 28 2007 | 3:26 pm
      Hi,
      do you have an URL for this?
      Best, Trond
      Alex Harker wrote: > > I've managed to confirm from a uk government website that the European patent has been revoked - so as far as I'm aware - in my part of the world I'm free to write my external..... > > Alex
    • Dec 29 2007 | 12:45 am
      Quote: Trond Lossius wrote on Fri, 28 December 2007 08:26 ---------------------------------------------------- > Hi, > > do you have an URL for this?
      The patent number is listed under revoked patents- it's the first in the list I think. You can google it to confirm that it's the patent in question.
      i believe the US equivalent is still valid however....
      Alex