Re: [eigen] first benchmark of large and sparse matrix

["Gael Guennebaud" <gael.guennebaud@xxxxxxxxx>]

On Mon, Jun 23, 2008 at 10:38 AM, Benoît Jacob <jacob@xxxxxxxxxxxxxxx> wrote:
> On Monday 23 June 2008 10:13:37 Gael Guennebaud wrote:
>> On Mon, Jun 23, 2008 at 7:30 AM, Benoît Jacob <jacob@xxxxxxxxxxxxxxx> wrote:
>> > On Monday 23 June 2008 07:05:30 Benoît Jacob wrote:
>> >> this is of high interest for Krita and for Step and probably has
>> >> countless interesting applications
>> >
>> > I forgot to mention that support for sparse matrices should be of high
>> > interest to OpenBabel (chemistry lib, also considering eigen2): if I
>> > remember well they sometimes apply solving algorithms to the adjacency
>> > matrix of a molecule, so for a molecule with N atoms the matrix is NxN
>> > and has 2N nonzero entries. As far as I remember they used to apply dense
>> > algorithms, so N^3 complexity which is only doable for small N (like
>> > 10^2) while some molecules they deal with have up to 10^5 atoms.
>>
>> hm... if there are only 2N nonzero entries then using a sparse matrix
>> is  pointless:
>
> I don't know much about sparse matrices, I believed that the less nonzero
> entries the more sense it made to use a sparse matrix.
>
>> the overhead is one int per nonzero entry.
>
> Precisely, since there are few nonzero entries, this is acceptable!

arf sorry sorry I read "2N zero entries"  and then I wrote "2N nonzero
entries" but in my mind it was still "2N zero entries"..... next time
I'll wait to be really awake, so forget what I said.... a sparse
matrix is perfect for that !

>
> Indeed, if the entries are only 0 and 1 then it is not optimal to store as a
> sparse matrix, but still, that is already quite good and far better than
> dense storage; moreover, I don't know if chemists do that, but at least in
> math it's useful to work with adjacency matrices of graphs with arbitrary
> values associated to graph edges, so in this case it's really a sparse
> matrix.

yes yes sure, with 2N non zero entries it's really sparse. Acually I
was surprised that the corresponding matrix was so dense, so I though
the graph also included collision constraints or whatever else....

>
>> Also, I think it's very important to support natively linear system
>> solvers as I know many users would never accept a dependency on
>> another lib.... especially if this lib depends itself on lapack that
>> is the case of most of them.
>
> OK. Let's see if we can use GMM++ code: GMM++ is LGPL 2.1-or-later.
>
> http://www.gnu.org/licenses/gpl-faq.html#AllCompatibility
>
> - normally, we can't copy and paste their code
> - but we can write to the author, he's cool
> - or we can ship some GMM++ code in separate files, without relicensing.

hm... it looks like things are worse because most of the algo provided
in GMM++ comes from ITL, which is not LGPL, it is a custom one which
is more like GPL (non commercial use) :
http://www.osl.iu.edu/research/itl/LICENSE.php3

gael.