Sparse Toeplitz matrices

[Marco Caliari]

Dear all,

I modified the toeplitz.m file I found in the Mercurial archive in order 
to optimize the sparse case. I home somebody can make a proper changeset.

Best regards,

Marco

On Sat, 11 Apr 2009, Jaroslav Hajek wrote:

> On Fri, Apr 10, 2009 at 5:33 PM, Marco Caliari <marco.caliari at univr.it> wrote:
>> Dear maintainers,
>>
>> I usually use finite differences (sparse) matrices and I find quite
>> convenient to use the function toeplitz.m to generate them. However, I
>> discovered that
>>
>> toeplitz(sparse([-2,1,zeros(1,N-2)]))
>>
>> can be quite slow if N is big.
>> I wrote the attached function which should be used only to generate sparse
>> Toeplitz matrices. Against Octave 3.1.54 I can see the following speedups:
>>
>> octave-3.1.54:1> N = 5000;
>> octave-3.1.54:2> tic,A = toeplitz(sparse([-2,1,zeros(1,N-2)]));,toc
>> Elapsed time is 4.78363 seconds.
>> octave-3.1.54:3> tic,B = mytoeplitz(sparse([-2,1,zeros(1,N-2)]));,toc
>> Elapsed time is 0.095167 seconds.
>> octave-3.1.54:4> A-B
>> ans =
>>
>> Compressed Column Sparse (rows = 5000, cols = 5000, nnz = 0 [0%])
>> octave-3.1.54:5>
>> tic,A=toeplitz(sparse([0,-1,zeros(1,N-2)]),sparse([0,1,zeros(1,N-2)]));,toc
>> Elapsed time is 3.8 seconds.
>> octave-3.1.54:6>
>> tic,B=mytoeplitz(sparse([0,-1,zeros(1,N-2)]),sparse([0,1,zeros(1,N-2)]));,toc
>> Elapsed time is 0.021 seconds.
>> octave-3.1.54:7> A-B
>> ans =
>>
>> Compressed Column Sparse (rows = 5000, cols = 5000, nnz = 0 [0%])
>>
>> If interested, I can try to make a patch against toeplitz.m.
>>
>
> Yes, please do. Be sure to patch the most recent version, though - I
> optimized it very recently (with the full case in mind), but your
> approach seems to be superior for sparse matrices.
>
>
>> Best regards,
>>
>> Marco
>
>
>
> --
> RNDr. Jaroslav Hajek
> computing expert & GNU Octave developer
> Aeronautical Research and Test Institute (VZLU)
> Prague, Czech Republic
> url: www.highegg.matfyz.cz
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: toeplitz.m.patch
Type: text/x-diff
Size: 1014 bytes
Desc: 
Url : https://www-old.cae.wisc.edu/pipermail/octave-maintainers/attachments/20090416/a0486be9/attachment.bin