Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Received-SPF: pass (asf.osuosl.org: domain of phil.steitz@gmail.com designates
 64.233.182.191 as permitted sender)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=Ds//MWbQ35JAmyG6U6it2ERLVEXMm2H2TN/SvfEHPjR2uj0Ds2CZpZqV1kqZLsiQ5474iGXrUwojJrJsV7D//H1Ubn4zWhxeFRjMNrDvC4yVSfip15+R9Z5/IUvWL0z2ZVfyVUqJcp3chuih4rDhNlIX5Li8NlfLJJOSOsrcA2s=
Message-ID: <8a81b4af0605201447x1c051cd8j5bc99eb4be932d0c@mail.gmail.com>
Date: Sat, 20 May 2006 14:47:54 -0700
From: "Phil Steitz" <phil.steitz@gmail.com>
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Subject: Re: [math] Q-R -decomposition
In-Reply-To: <238221690605201026g5398c0e8g3bf05b645f912929@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
References: <238221690603290914y3b6b6f25n92109b43ff0956c9@mail.gmail.com>
	 <8a81b4af0603291436v71641423y155281c6efdebccf@mail.gmail.com>
	 <238221690603312338h759b284fve47f22be32675209@mail.gmail.com>
	 <8a81b4af0604011119r48e65a62l8abeace01e36dd85@mail.gmail.com>
	 <238221690605080253y2d44f995q658f3e85cf897313@mail.gmail.com>
	 <8a81b4af0605142042s1194870al6d97d57ad63f9249@mail.gmail.com>
	 <238221690605201026g5398c0e8g3bf05b645f912929@mail.gmail.com>

On 5/20/06, Joni Salonen <joni.salonen@gmail.com> wrote:
> > > The algorithm used there produces the matrix R and an array of
> > > Householder vectors. When the getQ() is called, the Householder
> > > vectors are made into matrices that are multiplied together to yield
> > > the Q matrix. This seems to be the best way to go about things.
> > >
> > That seems fine to me, in terms of the state maintained in the decomp
> > class and the API as well - i.e., provide the accessors for Q and R,
> > but maintain state efficiently.
> >
> Done; this is what QRDecompositionImpl does now. Singular and
> rectangular cases are covered. The tests are more extensive, too.
> http://issues.apache.org/jira/browse/MATH-148

Thanks! I will commit the later versions to give us something to start with=
.
>
> There is one thing I'm not sure about: matrix dimensions. Some sources
> define the QR-factorization of an m x n matrix so that Q is m x m
> (square) and R is m x n, others say that Q is m x n and R is n x n
> (square). The current implementation does the former. Of course it's
> also possible to define Q as m x r and R as r x n, where r is min{m,
> n} or the rank of the original matrix. Do you have any insights on
> what should be done?

I am reviewing the implementation code and the Householder reflections
algorithm to figure out why this is the case.  The definitions that I
have seen (including the ones that you reference in the javadoc) use
the second approach (R is square).  Generally, m is assumed to be
greater than or equal to n and I think the matrix has to be full rank
for the decomp to be unique.  I am not an expert in this area, so will
defer to others if there are good arguments for using the definition
that your implementation uses.  The important thing is to document
exactly what the code does, both in the interface javadoc and the
impl.  It would be awkward in this case to have the interface
under-specified regarding the dimensions of the factors, so this
should probably be settled independently of the algorithm.
>
> > > I suppose we won't have a base interface for matrix decompositions?
> >
> > We can talk about that, but if we go with the design above, there is
> > really no place for it, unless I am missing something.  Now is a good
> > time to discuss these things, though, as once we define the API, we
> > (and our users) are going to have to live with it for some time.
> > Other than a "decompose" method (which the design above does not
> > include), its hard for me to see what a base decomposition interface
> > would include. The accessors are all different depending on the
> > decomp.  Could be I am missing something, though, so if you have ideas
> > about how to better structure this, please speak up.
> >
> It seems that many decompositions are used for solving linear systems.
> A decomposition object "knows" what the system is like and has access
> to the raw factorized data that can be packed in some way, so it would
> make some sense to ask it solve systems, too. Plus: users would be
> able to switch between different implementations, like with the
> Collections API.

Beyond what is available in the API (Q and R), what exactly does the
QR Decomp "know" that makes solving easier?
>
> Then again, solving systems doesn't seem like something inherent to
> the idea of a matrix factorization. Could it be a better idea to have
> an interface like "LinearSystemSolver" which then can be implemented
> by decomposition classes?

Probably a good idea, even if we don't have the decomp classes
implement it. I guess there is nothing wrong with the decomp
implementation classes implementing the linear solver interface.  Need
to think about this some more from both usability and extensibility
standpoint, but I think the interface makes sense in any case.

Thanks again for contributing this stuff.

Phil

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