Re: [eigen] Sparse Matrix Support

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

On Fri, Jun 18, 2010 at 7:56 PM, Sameer Agarwal
<sameeragarwal@xxxxxxxxxx> wrote:
>> Ok, since that's a standard approach it's probably good to support
>> though I doubt it's the most efficient way of doing this. I plane to
>> simply provide a template Tripplet<Scalar,Index> class and then let
>> the user takes its favorite container like std::vector<Tripplet>.
>
> I would argue for a lower level interface with three arrays/iterators
> instead of one, as this would allow for easy interface with cholmod_triplet
> and matlab.
>  > And last but not the least, have you given any thought to supporting
>>
>> > block sparse matrices?
>>
>> This is very tricky and I'm still not sure how to implement it the
>> most efficient and simple way. Indeed, the idea is of course to reuse
>> the SparseMatrix class and let it stores small fixed size dense Matrix
>> for the scalar type. For instance, let's assume a 300x300 block matrix
>> represented as a 100x100 standard sparse matrix of Matrix3d. The pb is
>> that depending on the context, sometimes we want to see it as a
>> 300x300 matrix of double, and sometimes as a 100x100 matrix of
>> Matrix3d blocks. So this probably requires a lot of work to get it
>> right.
>
> Block sparse matrices have two uses. One as Trevor pointed out and I had
> forgotten, ease of representation for problems coming from PDEs. So we
> should see if we can allow for building sparse matrices out of a list of
> triplets just like we do for  scalars.
> The other is high performance operations. One way would indeed be to store
> the matrix as a collection of dense blocks and then represent matrix vector
> products as operations on these blocks using dense BLAS operations.
> But this does not necessarily require uniform block sizes. For example in
> the problem of interest to me, I am interested in storing block sparse
> jacobians where different blocks are of different size and the matrix itself
> is extremely rectangular.
> In those cases, we could just store i,j, row_size, col_size, double* or a
> block CSR or CSC version of it and that leads to a 2-3 times speedup over
> storing it has a generic sparse matrix.
> Designing a good API for this will require some effort, but I think its
> worth it.

Ok, so what you need is very different to what I had in mind (a sparse
matrix of small fixed size dense blocks). In the cases you described
you are more interested in a way to assemble, or "view", a collection
of sparse or dense (but quite large) matrices into a single big sparse
matrix. The blocks could potentially overlap each other. For this kind
of stuff we would only want to support a very few operations, so yes
that's definitely doable without too much effort.

gael

> Sameer
>
>
>
>