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

[Douglas Bates <bates@xxxxxxxxxxxxx>]

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.

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.

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