commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <>
Subject Re: [math] Q-R -decomposition
Date Sat, 01 Apr 2006 19:19:59 GMT
On 4/1/06, Joni Salonen <> wrote:
> On 3/30/06, Phil Steitz <> wrote:
> > Great!  The first thing to do is to open a Bugzilla ticket and attach
> > the code to it, with that apache license in the class file headers
> > (look at any apache java class for an example).   Ideally, you should
> > also develop and include a test class.  Your main method could be the
> > start of this.  Have a look at the RealMatrix test classes for
> > examples.  We can talk further about design here on the list.   From a
> > quick glance at your code, it looks like you have just implemented the
> > decomp algorithm statically (which is a great start) and we should
> > talk about how to structure the API, class name, numerical stability,
> > and package placement.
> >
> I have created some tests now and included them in the bugzilla ticket.
> It would seem most natural to implement QR in math.linear because
> that's where the rest of the linear algebra related stuff is.

+1 - see below.  The only real question here is do we need a
subpackage for matrix decompositions.  Since I think it is unlikely
that we will have more than a handful of these, I am OK putting these
into the top level, i.e. in .linear.

> Initially I thought the algorithm, as it doesn't require state as
> such, could be included in the RealMatrix or RealMatrixImpl class,
> like the LU decomposition. But I'm not sure if that would be pushing
> too many responsibilities to one class. What is your view on this?

Agreed.  The only reason that the LU decomp is included in
RealMatrixImpl is that it is used in several of the basic algebraic
methods (e.g. solve, isSingular, inverse) included there and
maintaining a cached (compacted) LU matrix as part of the
RealMatrixImpl class makes those methods more efficient.  In
retrospect, it would probably have been better to externalize the
decomp and have RealMatrixImpl use the external class to create the
decomposition.  We could still do this without breaking backward
compatibility and with no loss of efficiency.  All that the impl needs
is a way to populate / refresh the cached LU decomp matrix.  Note also
that the LU decomp is not currently exposed as part of the RealMatrix
API.  This is because we thought that eventually we would externalize

So, for QR, we should implement this as a separate class.  To be
consistent with the rest of [math], we should also make the
implementation pluggable.  See summary below.

> I also had a look at Jama yesterday. There they defer the explicit
> generation of the Q part of the decomposition until the user calls
> getQ(), which I guess has a computational advantage over calculating
> the whole decomp if the user of the API only needs R. This of course
> implies that the algorithm has a state and it's most natural to
> implement it as a class of its own.

Again, I think this should be a separate (immutable) class with state,
with the decomp done in the constructor, which should take a
RealMatrix (not impl) as argument (using getData to copy if argument
is not a RealMatrixImp).  I am not sure I understand what you mean
about the Q and R accessors in Jama.  It looks to me like they are
just doing transformations to provide Q and R separately.  I think it
makes sense to provide those accessors (as we should in the LU case
when we externalize that).

> From the release plan I read that the QR-decomposition will be needed
> for linear regression. Does that mean that it will be used mainly for
> least-squares fitting? In that case both Q and R are needed most of
> the time, so having the algorithm in a separate class is not strictly
> necessary..

The immediate motivation is for solving the normal equations.  I don't
think we should include the solve() method that Jama has in this
class, though.  I think it is more natural to have that in the OLS

Tests are a good start.

Returning to the overall API design, I think it makes sense to follow
the abstract factory pattern used elsewhere in [math] (e.g. the
distributions package) to provide for pluggable decomp implementations
with defaults provided.  So what we would end up with would be an
abstract DecompositionFactory class with a concrete
DecompositionFactoryImpl subclass providing default implementations. 
Interfaces for decompositions would be abstracted.  User code with
look like this:

QRDecomposition qr =

where QRDecomposition is the interface and
DecompositionFactory.newInstance() returns a DecompositionFactoryImpl
and createQRDecomposition(matrix) invokes the constructor for
QRDecompositionImpl, which is the default implementation.  This setup
is used in the distributions and analysis packages to provide
pluggable implementations.

To get started, we can just define QRDecomposition,
QRDecompositionImpl.  If there are no objections / better ideas, we
can then add the factory impls and do the same for LU decomp (and
Cholesky, which I think we may also have laying around somewhere).



To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message