Re: 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 <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

toeplitz.m.patch
Description: Text Data