|Re: [eigen] Organization of the sparse module(s)|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Organization of the sparse module(s)
- From: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>
- Date: Fri, 4 Nov 2011 16:49:53 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=X77lhiD+G3fiy1cWRfJgbsJn7MkGJ3Z8s6n4+4ZcEOE=; b=Q5pBr5Wh3BVNlamenYLKFGAjPDd3K6OLfjxEY0aYzPpeXhsyvsvlRzBMXzKmstXYep 8jzrJ9Hd6Qp4eOPLF4g/swjUcYsxT2xyqWfZxkrV6KhbEYGwkx1Cm0LSl4Xms4pW23qE fWWGGakS/OnbQjCIxq+VOA6UWwhAGeDaPwndg=
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:
>> 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
>> * SparseCore *
>> - representation, manipulation,
>> - coefficient-wise operations, products (sparse-sparse, sparse-dense,
>> - 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
>> 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.