Boost logo

Ublas :

From: Andreas Klöckner (kloeckner_at_[hidden])
Date: 2005-03-22 08:24:25

Hi Michael,

Michael Stevens schrieb:
> I was thinking of how to describe how the two index arrays are built and the
> invariant that 'complete_index1_data' enforces. That is to say if we keep the
> implementation where index1 may be incomplete we should somewhere document
> it.

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.

As a consequence, I'm not so sure any more that enforcing said invariant
is a good idea.

> Do you know if any other compressed matrix libraries yield similarly
> incomplete index1 array?

I know of none.

> 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.

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.


Dipl.-Math. techn. Andreas Klöckner   | FON +49 721 608-7982
Institut für Angewandte Mathematik II | FAX +49 721 608-6679
Universität Karlsruhe                 | EMAIL kloeckner_at_[hidden]
Englerstraße 2                        |
76128 Karlsruhe                       | RAUM 022
Germany                               | Kollegiengebäude Mathematik