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

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

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: the overhead is one int per nonzero entry. Actually,
for such a particularly tough problem it has to be reformulated such
that you don't have to explicitly form the matrix, then you
reformulate it has a set of overlapping local problems and you iterate
multiple times till you converge to the global solution (I don't know
the name of this kind of approcach but I guess there exist a name for
it !) This is standard practice in CG.

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.


>
> This example suggests that adjacency matrices of large graphs are a countless
> source of applications for sparse matrices...
>
> Cheers,
>
> Benoit
>