commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <p...@steitz.com>
Subject Re: [math] linear algebra decomposition algorithms (SVD, Cholesky, QR, LU, eigen values ...)
Date Mon, 09 Jun 2008 02:42:53 GMT
Luc Maisonobe wrote:
> One of the task scheduled for 2.0 is the implementation of the Singular
> Value Decomposition.
>
> I think this addition should be done together with several other
> decompositions in a consistent scheme. What we have currently is:
>
>  - LU decomposition embedded directly into [Real/Big]MatrixImpl
>    without any reference to it in the [Real/Big]Matrix interfaces
>
>  - one QR decomposition as
>     1) an interface which is really only a way to retrieve results
>     2) an implementation which performs the decomposition on RealMatrix
>
>  - another QR decomposition hidden in the Levenberg-Marquardt estimator
>
> An API for these tasks was proposed by MathWorks and NIST with the JAMA
> package (http://math.nist.gov/javanumerics/jama/). This package provides
> specific classes for the decomposition (LUDecomposition, QRDecomposition
> ...). These classes provide accessors for the elements of the
> decomposition (say L and U) but more importantly they provide methods to
> use the decomposition: a solve method for LU, QR and Cholesky for
> example. Jama has been widely used but is dead now (see for example
> http://cio.nist.gov/esd/emaildir/lists/jama/msg01384.html). The code is
> in the public domain.
>
> I would propose to roughly follow Jama API, probably adding interfaces
> on top of the decomposition classes to be consistent with our other
> algorithms, and using the public domain Jama code as a basis. We could
> also address simply the issue about SVD in the original message.
>
> The changes in our code would be to extract LU from the XxxMatrixImpl
> classes, to add new methods to the QR interface and to see how the
> Levenberg-Marquardt algorithm can use this (I think this last step is
> the most difficult, as the QR decomposition used there is slightly
> distorted).
>
> What do you think about it ?
>   
I like this idea, with the following considerations.

1) The LU decomp embedded in RealMatrixImpl was not made public or 
included in the RealMatrix API precisely because I thought it would 
eventually be externalized.  So far so good.  The thing I want to make 
sure of is that the efficiency gain from caching it is still available 
to RealMatrixImpl.

2) I have always liked (well, mostly liked) the JAMA API and at one 
point we talked about just incorporating a whole lot of JAMA code 
directly into [math].  There are two reasons to be careful with this.  
The first is public domain does not necessarily mean unencumbered 
(somewhat bizarely, but IANAL).  The second is support.  We need to 
really understand how the code works to be able to support it.  For 
these two reasons, I am +1 on borrowing from the API, but would prefer 
clean room implementations of the *algorithms* that are implemented.  It 
is OK to get ideas from the code, but I would prefer to develop the 
implementations here or get them from authors who contribute directly 
under ASF CLAs.  I guess if we really, really want to take some of the 
code directly, we could go to legal-discuss, talk to the authors, etc.,...

Phil



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message