Re: matrix convolution and fourier transform

Dave Robinson wrote:
>
>
> David Epstein wrote:
>>
>>
>> If matrices are of appropriate sizes, the fastest way to do
> matrix
>> convolution and/or correlation is, I am told, using fast
Fourier
>> transform.
>>
>> 1. Does Matlab code use this technique?
>> 2. Is there any way of finding out which algorithms are used in
>> Matlab code?
>> 3. (Most important) Can anyone direct me to a text where this
is
>> explained. I'm interested in the theory, not just the
algorithm.
>>
>> Thanks
>> David
>
> Have a look in your library for a little book "Brigham, O E 1974:
> The
> Fast Fourier Transform. Prentice-Hall. 252pp."
>
> To my surprise I have just looked it up on Amazon, and a version of
> it still seems to be in print
>
> <http://www.amazon.co.uk/exec/obidos/search-handle-form/202-7043940-5363056>
>
> This explains in detail all things regarding the FFT including fast
> correlation/convolution. In my opinion this must be one of the best
> volumes written on the subject, generated by someone with a passion
> for explaining what its about, and not trying to impress you by
> plastering each page by as many integral and summation signs as he
> can. The concepts are explained first, both verbally and
> diagramatically, then once you understand where you are going, he
> introduces the mathamatics.
>
> I am sure Steve Eddins can tell you whether the image processing
> pack
> uses the fast frequency domain algorithms, but it would surprise me
> if they don't; from memory I think that the fast algorithms
> overtake
> the conventional slip slide algorithms once the matrix exceeds
> 32x32
> pixels.
>
> Sorry I cannot give you a definate answer.
>
> Regards
>
> Dave Robinson

Thanks a lot for the replies. I am now reading Brigham's book, and
it's exactly what I need. As you say, very good style, which,
unfortunately is not very common.
David
.

Relevant Pages

  • Re: complexity of numerical software
    ... David N. Williams wrote: ... They have nothing to do with algorithms to find subsets, ... nonnegative normalized short floating-point numbers x, SQRT returns the correctly rounded value... ...
    (sci.math.symbolic)
  • Re: Google and Python usage
    ... > David M. Cooke wrote: ... test new features and algorithms that later get either discarded or recoded ... They rerun at least some programs enough times ...
    (comp.lang.python)
  • Re: little-oh
    ... David C. Ullrich wrote: ... It is the most classical text on algorithms, ... Omega, and little omega are defined as lower bounds. ...
    (sci.math)
  • Re: How to sort a vector and then append data
    ... >Hi David, ... >Now I see that the algorithms you propose works fine for contiguos ... won't be able to fix it when it breaks. ...
    (comp.lang.fortran)