[GRASS-dev] gmath and gpde update

[Soeren Gebbert]

I may found a way to avoid licensing problems or the need to
convince the meschach developers to change there license
to be compatible with the gpl.

We can use parts of the ccmath library.
http://freshmeat.net/projects/ccmath/

The ccmath library is licensed under the LGPL,
and i hope we don't face any problems with this license?

To replace the nr code in grass we need:

* a fast lu decomposition with pivoting
* computation of eigen values and eigen vectors
* singular value decomposition

Here a cite from the ccmath matrix library documentation:

#######################################################

               The matrix algebra library contains functions that
               perform the standard computations of linear algebra.
               General areas covered are:

                         o Solution of Linear Systems
                         o Matrix Inversion
                         o Eigensystem Analysis
                         o Matrix Utility Operations
                         o Singular Value Decomposition
...

 o  Solving and Inverting Linear Systems:

    solv  --------- solve a general system of real linear equations.
    solvps  ------- solve a real symmetric linear system.
    solvru  ------- solve a real right upper triangular linear system.
    solvtd  ------- solve a tridiagonal real linear system.

    minv  --------- invert a general real square matrix.
    psinv  -------- invert a real symmetric matrix.
    ruinv  -------- invert a right upper triangular matrix.

...

 o  Eigensystem Analysis:

    eigen  ------ extract all eigen values and vectors of a real
                  symmetric matrix.
    eigval  ----- extract the eigen values of a real symmetric matrix.
    evmax  ------ compute the eigen value of maximum absolute magnitude
                  and its corresponding vector for a symmetric matrix.

...

 o Singular Value Decomposition:

    svdval  ----- compute the singular values of a m by n real matrix.
    sv2val  ----- compute the singular values of a real matrix
                  efficiently for m >> n.
    svduv  ------ compute the singular values and the transformation
                  matrices u and v for a real m by n matrix.
    sv2uv  ------ compute the singular values and transformation
                  matrices efficiently for m >> n.
    svdu1v  ----- compute the singular values and transformation
                  matrices u1 and v, where u1 overloads the input
                  with the first n column vectors of u.
    sv2u1v  ----- compute the singular values and the transformation
                  matrices u1 and v efficiently for m >> n.

end
#######################################################

So the ccmath library provides all the algorithms we need to replace the nr
code in grass.

I would suggest to extract the needed parts from ccmath and integrate
them in the gmath library structure i already created (take a look at the
patch i provided).
I would suggest an extraction of needed parts because the ccmath library
ships a lot of algorithms we don't need and
the source code is not well documented and difficult to read.
We only need the matrix computation algorithm including documentation and
tests.

I will keep my sparse matrix solver and matrix-vector algorithm in gmath and
extend them,
(more sparse matrix and sparse vector operations ... inspired from
meschach),
to implement in the future a sparse ILU and LU factorisation with minimal
fill in.
This is needed for huge sparse linear equation systems with bad condition.
Such linear equation systems
can not be solved with the sparse matrix solver i implemented.

Things to be done (very roughly estimated):

* extraction of the needed algorithm from ccmath
* Implementation of a wrapper around these functions, so a user can replace
the grass ccmath extraction with
  a distribution or self compiled version of the ccmath library.
* integration of the documentation and the tests of ccmath matrix into gmath
* integration of the ccmath solver in the gmath solver structure. This may
result in a modification of the current matrix
  access methods and a rewrite of the blas 1, 2 and 3 functions i
implemented.
* replacing the nr code which results in the modification of all dependent
gmath code and grass modules
* writing tests for all depended modules
* improving the grass sparse matrix algorithms and solver

Well i guess i will need at least another year to code this.
...

So, how about this approach? Any hints, suggestions or criticism?
Did i over see an issue?


Best regards
Soeren




2009/1/15 Glynn Clements <glynn at gclements.plus.com>

>
> Moritz Lennert wrote:
>
> > > I don't really see a problem with it. It's a "you do not have the
> > > freedom to make this program less free" restriction, similar to the
> > > restrictions imposed by the GPL.
> >
> > Well, the first paragraphe of the DFSG is:
> >
> > "Free Redistribution
> >
> > The license of a Debian component may not restrict any party from
> > selling or giving away the software as a component of an aggregate
> > software distribution containing programs from several different
> sources."
> >
> > So, forbidding to sell seems against the DFSG...
>
> The meschach licence doesn't prohibit selling an aggregation of which
> meschach is a component.
>
> That makes the problematic clause even more pointless. You could sell
> a CD containing meschach and a two-line script, on the basis that
> meschach is free but the script costs $50k.
>
> > > Essentially, it's a question of how to resolve competing freedoms, and
> > > the meschach licence took a different view to the GPL. It's just a
> > > different (and incompatible) sort of "free".
> >
> > There seems to be a possibility of exceptions for these situations in
> > the GPL[1]:
>
> Only the copyright holder can provide such an exemption.
>
> The author can release their code under any licence they choose,
> including e.g. GPL-but-you-can-link-against-meschach (KDE provided
> such an exemption for Qt before it was available under the GPL).
>
> But you can't provide such an exemption for anyone else's GPL code. So
> you couldn't distribute a binary linked against e.g. both meschach and
> readline. I don't know if this would apply on a module-by-module basis
> or to GRASS as a whole. IOW, whether you can claim that GRASS is a
> "mere aggregation" of its components or a single work. I suspect the
> latter.
>
> > So, we might be able to do this, but AFAICT this would need the
> > agreement of all people holding copyright over GRASS code.
>
> Yes. Including any GPL libraries (e.g. readline).
>
> --
> Glynn Clements <glynn at gclements.plus.com>
> _______________________________________________
> grass-dev mailing list
> grass-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/grass-dev/attachments/20090115/1ae4f302/attachment-0001.html