Boost logo

Boost :

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2002-05-02 14:56:30


----- Original Message -----
From: "Paul C. Leopardi" <leopardi_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, May 02, 2002 1:22 PM
Subject: [boost] uBLAS vs MTL for sparse matrices

> Hi all,
> I am currently developing GluCat, a generic library of universal Clifford
> algebra templates - see http://glucat.sf.net
> GluCat 0.0.6 uses MTL 2.1.2-20.
>
> GluCat uses MTL because of its support for sparse matrices.
> GluCat often needs to manipulate matrices which have the same sparsity
> pattern as permutation matrices, eg. 1024 x 1024 with 1024 non-zeros.

But these matrices aren't permutation matrices, i.e. the non zero matrix
elements aren't always 1?

> To do this, GluCat routines use MTL iterators which provide iteration over
> the non-zero entries of a matrix. This means GluCat can iterate over a
sparse
> n x n matrix in O(n) time rather than O(n^2).
>
> I am thinking of making GluCat as Boost-compatible as possible, and of
> improving its readability. This would eventually involve operators,
concepts,
> etc. and may involve a switch from MTL to uBLAS, especially if MTL 3 is
not
> being actively developed.
>
> I have read that uBLAS now supports sparse matrices.

We've checked in the first sparse matrix format 9 month ago ;-)

> Does the sparse matrix
> data structure used in uBLAS povide the same sort of iterators as MTL?
> Is it possible to iterate over an n x n permutation matrix in O(n) time?
How?

Iteration over a matrix is possible in the following way:

        for (numerics::sparse_matrix<double>::const_iterator1 itmr =
m.begin1 ();
                itmr != m.end1 ();
                    ++ itmr) {
             for (numerics::sparse_matrix<double>::const_iterator2 itmc =
itmr.begin ();
                    itmc != itmr.end ();
                        ++ itmc) {
                            std::cout << *itmc << std::endl;
            }
        }

For O(n) complexity you better use sparse_vector_of_sparse_vector or
compressed_matrix (both currently undocumented ;-(

Regards

Joerg

P.S.: do we need to consider a class permutation_matrix<>?


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk