|Re: [eigen] Sparse Matrix Support|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Sparse Matrix Support
- From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- Date: Sat, 19 Jun 2010 00:32:34 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:received:in-reply-to :references:from:date:message-id:subject:to:content-type :content-transfer-encoding; bh=eqbGDTAmjW6Ri//bej78Ym9DAX+GhZItzI8F162DETo=; b=eWD2/KlmFQo1UkzcXh1mFWRFvh02SLtzqg4u+pztmYE5n8xUZZSRAaE+Rj3Jjhy8us HjvB8Y52JFPyHKjlsit6mYyyrj9QYbUo08bdkFViXZWoMX+QNKAKrFfJYh4PgWI0GEqe uzMgNrFWbPT5EqPIyEQfVmGsj0ocGIkaUlze8=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; b=Iw0W0daIlhDqDA9OJpsK6QRJBBLiBoU4eFs0AhnXWfy6HkZHDezSr9ADldpmxtEGP8 40D9jBNFnVDKmMV7I8sa5I29AxyIaqeDaC9ePZbea4URDEwyTQamSB1EXMsIEs93QE5B dKOpxjX+urtMpXBFa3adUnkqJ8fQoLmcwhMDU=
On Fri, Jun 18, 2010 at 7:56 PM, Sameer Agarwal
>> 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
> 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.