Re: [eigen] Organization of the sparse module(s)

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

On Fri, Nov 4, 2011 at 3:50 PM, Douglas Bates <bates@xxxxxxxxxxxxx> wrote:
> On Fri, Nov 4, 2011 at 9:30 AM, Gael Guennebaud
> <gael.guennebaud@xxxxxxxxx> wrote:
>> Hi,
>>
>> I'm in the process of moving the few sparse solvers currently spread
>> in the unsupported folder into official Eigen/ folder. So the question
>> is about the granularity of the module I'll create for that. For
>> consistency reason, the Sparse module should include everything that
>> is related to sparse and built-in. "Support" modules have to stay into
>> isolated modules. Here is the list of features with a proposal for an
>> organization:
>>
>> * SparseCore *
>> - representation, manipulation,
>> - coefficient-wise operations, products (sparse-sparse, sparse-dense,
>> sparse-permutation),
>> - triangular solvers
>> - ordering methods (currently AMD=approximate minimum degree only)
>>
>> * SimplicialFactorizations *
>> - direct LLT and LDLt decompositions and solving for SPD sparse matrices,
>> - two classes: SimplicialLLt and SimplicialLDLt
>> - future: direct simplicial LU and QR factorization and solver
>>
>> * IterativeLinearSolvers *
>> - ConjugateGradient (Iterative solver for Ax=b with A SPD)
>> - BiCGSTAB (Iterative solver for A square)
>> - Basic preconditioners:
>>  - IdentityPreconditioner
>>  - DiagonalPreconditioner (= Jacobi preconditioner)
>>  - future: SSOR, ILUT
>>
>> Three support modules:
>> * SuperLUSupport *
>> * CholmodSupport *
>> * UmfPackSupport *
>> future: MumpsSupport, PastixSupport, MetisSupport, ScotchSupport, etc.
>>
>>
>> Future could add some new modules:
>>
>> * ConstrainedLinearSolvers *
>>  - for both dense and sparse worlds
>>
>> * <a generic word for multifrontal and supernodal>Factorizations *
>>  - Fast direct LLt and LU factorizations based on supernodes or
>> multifrontal approaches (automatically make use of dense matrix
>> operations)
>>
>> Any opinion about this granularity? Another options for the direct
>> solvers would be to organize them into three modules:
>> DirectSparseCholesky, DirectSparseLU, DirectSparseQR.
>
> The ordering methods are closely tied to the factorizations and
> probably belong in SimplicialFactorizations.  I can't think of a
> general use for ordering methods other than for factorizations.
> However, if you are going to have three factorization modules, as
> described in the last paragraph, then it would make sense to put the
> ordering methods in a common parent module.

Yes that's mostly why I put them in SparseCore. Another reason is that
they might be useful for iterative solvers to reduce cache misses in
the multiple matrix-vector products, though I agree that for such use
case you probably want different ordering strategies since the goals
are different. In any case this does not prevent to put them into a
separated OrderingMethods module.

> While on the topic of ordering methods, having COLAMD in addition to
> AMD would be useful.  I haven't looked at the code in SuiteSparse
> sufficiently closely to determine how close the two algorithms are but
> I have had occasions where COLAMD on A produced less fill-in than AMD
> applied to A'A.  If you are going to incorporate a sparse QR you
> probably want COLAMD anyway.

For LU, QR, COLAMD and the likes the goal is indeed to grab the LGPL
algorithms from suitesparse and more particularly CSparse.

> The sparse matrix methods are central to my work and I would be happy
> to help in whatever way I can in their development.

We clearly need help for that parts ! My short term goal is to clean
what is already implemented, move what cannot be stabilized easily
into unsupported/SparseExtra, and write an extensive documentation.
Then I'll probably ask on this list a review of the documentation with
respect to the design, API and the like and if everybody agree make a
release with a stable Eigen/Sparse module.
gael