Re: [ublas] [patch] matrix norms are inefficient for sparse matrices

From: Georg Baum (Georg.Baum_at_[hidden])
Date: 2005-08-30 02:14:00

Am Sonntag, 10. Juli 2005 09:38 schrieb Gunter Winkler:
> Zitat von Georg Baum <georg.baum_at_[hidden]>:
> > Hello,
> >
> > while playing a bit with the profiler I noticed that matrix_norm_inf
> > computes the norm by iterating over each element (i, j). The same is true
> > for matrix_norm_1 and matrix_norm_frobenius. This is of course
> > inefficient for sparse matrices.
> > I wonder why that is the case? I can't believe that such an inefficient
> > implementation is used without reason. Now I am wondering if I have to
> > expect more surprises like that? Or did I miss something?
>
> Maybe you are the first one who uses these norms for non-dense matrices.
>
> > I attach the patch I aam currently using for interested people to play
> > with. It to optimize the matrix norms and seems to work for
> > matrix_norm_inf (I did not yet test the other norms).
>
> Looking at the patch I see that you provided a better implementation for
> row major matrices. Did you also try column major matrices?

The patch was partly wrong. There is no obvious algorithm for matrix_norm_1 of 
row major matrices and for matrix_norm_inf of column major matrices, but 
matrix_norm_frobenius can be specialized.
Unfortunately I don't know the ublas internals well enough to figure out how 
to use a compile time if, so I had to make the layout_type typedef public for 
a lot of types which I don't like.
Here is the patch that I currently use in case somebody is interested.

Georg