Re: [ublas] [patch] Fixes for compressed matrices

From: Michael Stevens (mail_at_[hidden])
Date: 2005-03-22 14:43:47

Hi Andreas,

On Tuesday 22 March 2005 14:24, Andreas Klöckner wrote:
>
> A while ago, I tried to change compressed_matrix<> to always have a
> complete index1 array. It occurred to me that this ruins the complexity
> guarantees of the push_back() and pop_back() methods, since then, upon
> each insertion, the filled remainder of the index1 array needs to be
> updated. These methods are important if you're building a
> compressed_matrix from a known and pre-sorted storage pattern, which
> should be linear-time.

OK I understand. I was looking at the insert_element case and not push_back. 
One possibility is to work the same way as coordinate_matrix does with its 
'sorted_' flag. I suspect a index1_complete function will be the preferred 
solution however.

> As a consequence, I'm not so sure any more that enforcing said invariant
> is a good idea.
With a separate function I assume?

> > Do you know if any other compressed matrix libraries yield similarly
> > incomplete index1 array?
>
> I know of none.
That would imply that nothing else has the equivalent of an efficient 
push_back. Interesting!

> > I have committed the the operation.hpp patch.
>
> It seems to me you changed the upper loop boundary to "filled1 ()" from
> my patch, which said "filled1 () - 1".  I believe your change is
> incorrect: The loop needs to iterate over each row of the matrix.
> index1_data_ has one more entry than the matrix has rows. The leftover
> entry is used to find the end of the last row.

Sorry my sloppyness. The automatic patch application failed. No idea why it 
looked like a valid diff. So I applied by hand and missed the change to -1. 
Sorry to waste your time on such a stupid mistake.

>
> I've attached a patch to fix this (compressed-axpy-2005-03-22.patch).
> The patch also fixes the premultiply (axpy_prod(x, A, ...)) case which I
> had previously forgotten and adds a missing "return v;" that was missing
> from Gunter's recent coordinate_matrix axpy_prod patch.
>
> I've also attached an updated patch against matrix_sparse.hpp
> (complete-index1-2005-03-22.patch) that adds a fixed, non-const version
> of complete_index1_array to compressed_matrix. The corresponding
> bindings patch is compressed-bindings-2005-03-22.patch.
>
> All patches are against CVS as of today.

I'll try and follow this up after Gunters patch!

Michael