Re: toeplitz multiplication

[Paul Kienzle]

On Nov 29, 2006, at 6:07 PM, Gorazd Brumen wrote:

> Hi,
>
> As far as I could see it, we also dont have the toeplitz
> matrix * vector multiplication routines. This is really
> easy done using two fft and an inverse fft.
>
> Am I mistaken or does there exist this implementation to
> the operator * ?
>
> I could provide the c++/liboctave code, but please tell
> me first if this
>
> a) exists
>
> b) should be implmented as a c++ code or can it also be
> done as an octave script and what is the preferred option?

I would be concerned about the numerical properties of the
FFT vs. the direct multiplication.  A similar issue arises
in convolution where we have the choice of conv and fftconv
so the user can decide between speed and accuracy.

For small n, you won't care about the relative speed of O(n^2)
and O(nlogn), particularly since the constant is large.  For
large n an octave implementation is fine. Also, for large n
you should be representing the toeplitz  matrix as two vectors
with specialized algorithms and save both speed and memory.

- Paul