Re: Sparse Toeplitz matrices

[Jaroslav Hajek]

On Fri, Apr 10, 2009 at 5:33 PM, Marco Caliari <address@hidden> 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