Re: conv2 performance

[Michael D. Godfrey]

On 3/1/10 9:07 AM, Soren Hauberg wrote:
> man, 01 03 2010 kl. 09:17 -0500, skrev John Swensen:
>    
> > >  On Feb 28, 2010, at 10:53 AM, John W. Eaton wrote:
> >      
> > > >  >  
> > > >  >  
> > > >  >  Maybe there is still room for improvement here.  I would happily use a
> > > >  >  free software library with a GPL-compatible license to implement this
> > > >  >  function, but I don't know whether one is available.
> > > >  >  
> > > >  >  jwe
> > > >  >  
> > >        
> > >  
> > >  I have recently been doing a lot of 2D convolutions.  I think the
> > >  fastest method should not involve loops of any kind.  As convolution
> > >  in the time domain (or spatial domain when considering images) is
> > >  multiplication in the frequency domain, the fastest method is to take
> > >  the FFT of both image and kernel, dot-multiply them, then take the
> > >  inverse FFT.
> >      
> > From what I understand, the downside is that this approach can loose
> quite a bit of precision. Here are some of the thoughts by a Matlab
> engineer:
>
>
> http://blogs.mathworks.com/steve/2009/11/03/the-conv-function-and-implementation-tradeoffs/
>
> Soren
>
>    
The Matlab engineer's analysis is not convincing.  One integer analysis 
as the basis for a
general claim of "loss of precision" is quite silly.   A lot of work has 
been done on numerical
stability of FFT's.  The use of both algorithms, depending on the length 
of the sequences is
worth considering.  One of its serious problems is matching behavior at 
the switch points.
Putting a lot of work into resolving that problem may not be worth it.  
Simpler would be
to provide both conv2 and an fft-based version.

Michael