You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Greg Sterijevski <gs...@gmail.com> on 2011/10/05 03:35:32 UTC
Pivoting QR Decomposition: Take Two!
Hello all,
A while back I was interested in being able to do pivoting qr decomposition.
I noticed that Chris Nix submitted a patch, but he indicated that he had
more work to do (testing and filling in functionality). In the discussion
around this, Luc suggested that I look at the QR decomposition in
Levenberg-Marquardt. I did just that a few days ago. The code was very clear
and nicely written (kudos to Luc). So, I copied the routine and made a new
PivotingQRDecomposition class. The class is intended as a "drop in
replacement" for QRDecomposition. I also copied the QRSolverTest and
QRDecompositionTest. With the exception of testUnderdetermined in the solver
test and testAEqualQR in QRDecompositionTest, the tests are unchanged (and
all pass!). With testUndertermined, the "zeroed" rows of the solution matrix
are interspersed throughout the matrix (because of pivoting). So I change
the test to count all the rows that have zero norms, and check that it is
the correct number. In testAEqualQR, I added a multiplication by the
permutation matrix.
What is the best way to proceed? I don't want to trounce the additions that
Chris made, but it looks like Chris has more sophisticated classes in mind.
I don't see this proposed change competing with his. Does it make sense to
bring back QRDecomposition interface (sorry Sebastien)? We can then keep
both implementations until we are satisfied the pivoting one works.
Thoughts?
-Greg
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
Actually, you can easily get all the information at least in degenerate
form.
The two cases are:
- getPivot() ... the identity permutation can be returned
- getRank() ... it is reasonable to throw an exception stating that rank
is not available (UnsupportedOperationException, in particular). This is
*exactly* analogous to the way that many iterators do not allow remove() to
be called.
On Thu, Oct 6, 2011 at 3:21 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> IIUC, there are things you can query from a "PivotingQRDecomposition" that
> you cannot from the "FastQRDecomposition", then when you get the interface
> "QRDecomposition", you've lost these additional features. And if you impose
> that the interface contains them, then if you request the "fast"
> implementation, and then query the "pivoting" features, what happens?
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
> >>
> >>What is the group's feeling on factory classes? +1 from me (obviously)
> >>
> >+1 for me, I like factories.
>
> -0. We used factories and removed most of them. In fact, what we
> removed was when factories are used to hide implementation and only
> an interface and a factory are available to users. This is a
> different cases.
>
> There are other places too where we still have some factories, even
> in new code (an example would be Region in the geometry package if I
> remember well).
-1 for a factory.
[Note that I haven't thought at all about use-cases (and thus at how a
factory would be best to answer those unspecified needs). Please give
some examples.]
We indeed removed several factories that IMO were an hindrance because they
were hiding important specifics of algorithms. [E.g. there was a root
solvers factory that would return one of the solvers which CM provides. How
is it the role of a library to decide which solver is good for a given
user?]
Factories are undisputably good when they generate the *one* correct
implementation (cf. the well-known example of GUI widgets that must
correspond to the chosen "theme" or the current low-level graphics
primitives).
In CM, there is a factory that creates one or another kind of matrix,
depending on the number of entries. [This seems reasonable but, the
threshold being somewhat arbitrary, I would be interested to know how
many applications rely on this automatic choice of implementation.]
However, in this case, what would a factory bring?
When the user knows what he wants, I much prefer explicit instantiation
because the code clearly shows what class is being used (obviously):
PivotingQRDecomposition qr = new PivotingQRDecomposition(m);
vs
QRDecomposition qr = QRDecompositionFactory.create(true);
or (even worse IMHO)
QRDecomposition = DecompositionFactory.createQRDecomposition(true);
where the boolean parameter is assumed to select whether the "pivoting"
feature is enabled or not.
IIUC, there are things you can query from a "PivotingQRDecomposition" that
you cannot from the "FastQRDecomposition", then when you get the interface
"QRDecomposition", you've lost these additional features. And if you impose
that the interface contains them, then if you request the "fast"
implementation, and then query the "pivoting" features, what happens?
Also, since each decomposition (LU, SVD, ...) provides different methods
(except the common "getSolver"; see my previous post), it is fairly clear
that a generic "Decomposition" interface would not be useful at all.
I argue again that, at the CM level, there isn't enough context to make a
uniformly right decision.
Applications that would benefit from a factory can of course create them at
their level.
Best regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Thu, Oct 06, 2011 at 07:52:55PM -0500, Greg Sterijevski wrote:
> If you really think about, all of the decomposition classes should be
> handled by factories. The decompositions all seem to occur in the
> constructor. Everything else is derived from those results, so one could
> argue that the actual decomposition code could be written very procedurally
> and put into the factory as a static private method. The returned class from
> the factory would be nothing more than a container of the results and
> methods to get the data and derivatives of the data.
Sorry, but I don't see the logical link between "all calculations occur in
the constructor" and "factories". That's why I had been expecting a real
example that would clearly show that the current applications of the
decomposition classes could be more elegantly and/or efficiently be dealt
with in a design based on factories. [But we can/should defer this
discussion until after the release of 3.0.]
Best,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hi.
> > > Yes, this application would be similar to the ones you nixed. It would be
> > a
> > > factory returning an abstract class, with the appropriate methods
> > throwing
> > > exceptions (like getRank for the non-pivoting version-as Ted mentions in
> > a
> > > later entry in this blog).
> > >
> > > As Ted asks, what is the issue with this?
> >
> > What I'm asking is: What is the issue with 2 concrete classes (and possibly
> > an abstract base class, if there is some code to share)?
> >
>
> The issue is that the different classes are really an implementation detail
> from the user's point of view. What they care about is rank-revealing or
> not. They don't really care about pivoting except insofar as they know that
> is how rank revealing QR is done.
OK, then the pivoting implementation should preferrably be in a class named
"RankRevealingQRDecomposition"?
> It can be done with multiple classes, but just as java collections and now
> guava provide constructors that hide implementation details but expose user
> details, I think that this is good practice elsewhere as well.
I agree. The question is to identify the "interesting" specifics. In this
case, if "getRank()" is interesting, it should not be the result of an
implementation detail that, if not present, would generate an exception.
> For example, if you say Maps.newHashMap(), do you *really* care which hash
> table implementation you get?
No.
But this case is not the same since the user will choose one or the other
implementation based on his knowledge that he will be able to obtain, or
not, something from "getRank()".
Having
* one class per implementation, or
* 2 implementations in the same class and selecting one or the other by
passing a boolean,
is exactly the same for the user.
For the developer, I contend that it is tidier to separate the algorithms
along class boundaries.
>
> > [As Ted pointed out, the CM design is not based around factories (which is
> > fine IMO until proven otherwise); changing that would require a strong
> > argument and should lead to a complete revision of the basic layout of the
> > library, in order to be consistent. Maybe for 4.0 :-).]
> >
>
> Sure. Whatever. (checking out)
>
> To stretch the argument, why not create a "UniversalDecomposition" class
> > with all the methods in it:
> >
>
> Because that is just a straw man argument that isn't directed toward making
> things better. Just because an extreme form isn't right doesn't mean that
> moving that direction isn't a good idea.
>
> To paraphrase, I would like to find a minimum of (x-1)^2. Starting at 0, I
> could say that moving to 0.5 is good. You could say that the value is much
> larger at 20 and therefore moving to 0.5 is a bad idea.
>
>
> > getCholeskyL()
> > getLuL()
> > getLuU()
> > getLuP()
> > getQrQ()
> > getQrR()
> > getQrH()
> > getSvdU()
> > getSvdS()
> > getSvdV()
> > ...
> > and throw "UnsupportedOperationException" as necessary?
> >
> >
> Most of the Java world got past this many years ago.
I'd be interested by a pointer.
I'm all for CM to be "state-of-the-art" but it should be done in an orderly
fashion lest someone dropping in some months/years from now will not be able
to figure out what were the guiding principles in the design.
If the design is coherent, it will be easier to modify it globally to adopt
a new paradigm. On the other hand, if the library uses mixed coding styles,
it will become extremely difficult to figure out why one style was used here
and another there, and if it was done on purpose or just on a whim of the
programmer.
Best regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
On Thu, Oct 6, 2011 at 9:13 PM, Phil Steitz <ph...@gmail.com> wrote:
> Lets a) stop top-posting (Gilles has asked politely a couple of times now)
> and b) stay focused on solving the problems we actually have. We could
> endlessly debate refactoring approaches.
Sorry about the top posting, I am big culprit here... Was not aware that the
mailing list's protocol was being violated. Will interleave from now on.
Or we could fix the stuff blocking 3.0 and get a release out. Let's do
> that.
>
>
Will push the pivoting QR under JIRA MATH-630. There will be a few
checkstyle errors. I apologize in advance. Was not suggesting the whole
codebase should be refactored, just looking for the right way to push
pivoting QR into the mix. The thread began with a suggestion of using only
the pivoting QR (meaning dropping the non pivoting one). The discussion
brought us to the understanding that both implementations should be
retained. I feel it has been a useful discussion-whether we use factories or
not.
> Phil
>
>
-Greg
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Phil Steitz <ph...@gmail.com>.
Lets a) stop top-posting (Gilles has asked politely a couple of times now) and b) stay focused on solving the problems we actually have. We could endlessly debate refactoring approaches. Or we could fix the stuff blocking 3.0 and get a release out. Let's do that.
Phil
On Oct 6, 2011, at 6:33 PM, Ted Dunning <te...@gmail.com> wrote:
> Yeah... but this is a rough neighborhood for folk like you and me.
>
> On Thu, Oct 6, 2011 at 5:52 PM, Greg Sterijevski <gs...@gmail.com>wrote:
>
>> If you really think about, all of the decomposition classes should be
>> handled by factories. The decompositions all seem to occur in the
>> constructor. Everything else is derived from those results, so one could
>> argue that the actual decomposition code could be written very procedurally
>> and put into the factory as a static private method. The returned class
>> from
>> the factory would be nothing more than a container of the results and
>> methods to get the data and derivatives of the data.
>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
Yeah... but this is a rough neighborhood for folk like you and me.
On Thu, Oct 6, 2011 at 5:52 PM, Greg Sterijevski <gs...@gmail.com>wrote:
> If you really think about, all of the decomposition classes should be
> handled by factories. The decompositions all seem to occur in the
> constructor. Everything else is derived from those results, so one could
> argue that the actual decomposition code could be written very procedurally
> and put into the factory as a static private method. The returned class
> from
> the factory would be nothing more than a container of the results and
> methods to get the data and derivatives of the data.
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
If you really think about, all of the decomposition classes should be
handled by factories. The decompositions all seem to occur in the
constructor. Everything else is derived from those results, so one could
argue that the actual decomposition code could be written very procedurally
and put into the factory as a static private method. The returned class from
the factory would be nothing more than a container of the results and
methods to get the data and derivatives of the data.
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
On Thu, Oct 6, 2011 at 1:56 PM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> On Thu, Oct 06, 2011 at 02:56:28PM -0500, Greg Sterijevski wrote:
> > Yes, this application would be similar to the ones you nixed. It would be
> a
> > factory returning an abstract class, with the appropriate methods
> throwing
> > exceptions (like getRank for the non-pivoting version-as Ted mentions in
> a
> > later entry in this blog).
> >
> > As Ted asks, what is the issue with this?
>
> What I'm asking is: What is the issue with 2 concrete classes (and possibly
> an abstract base class, if there is some code to share)?
>
The issue is that the different classes are really an implementation detail
from the user's point of view. What they care about is rank-revealing or
not. They don't really care about pivoting except insofar as they know that
is how rank revealing QR is done.
It can be done with multiple classes, but just as java collections and now
guava provide constructors that hide implementation details but expose user
details, I think that this is good practice elsewhere as well.
For example, if you say Maps.newHashMap(), do you *really* care which hash
table implementation you get?
> [As Ted pointed out, the CM design is not based around factories (which is
> fine IMO until proven otherwise); changing that would require a strong
> argument and should lead to a complete revision of the basic layout of the
> library, in order to be consistent. Maybe for 4.0 :-).]
>
Sure. Whatever. (checking out)
To stretch the argument, why not create a "UniversalDecomposition" class
> with all the methods in it:
>
Because that is just a straw man argument that isn't directed toward making
things better. Just because an extreme form isn't right doesn't mean that
moving that direction isn't a good idea.
To paraphrase, I would like to find a minimum of (x-1)^2. Starting at 0, I
could say that moving to 0.5 is good. You could say that the value is much
larger at 20 and therefore moving to 0.5 is a bad idea.
> getCholeskyL()
> getLuL()
> getLuU()
> getLuP()
> getQrQ()
> getQrR()
> getQrH()
> getSvdU()
> getSvdS()
> getSvdV()
> ...
> and throw "UnsupportedOperationException" as necessary?
>
>
Most of the Java world got past this many years ago.
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Thu, Oct 06, 2011 at 02:56:28PM -0500, Greg Sterijevski wrote:
> Yes, this application would be similar to the ones you nixed. It would be a
> factory returning an abstract class, with the appropriate methods throwing
> exceptions (like getRank for the non-pivoting version-as Ted mentions in a
> later entry in this blog).
>
> As Ted asks, what is the issue with this?
What I'm asking is: What is the issue with 2 concrete classes (and possibly
an abstract base class, if there is some code to share)?
[As Ted pointed out, the CM design is not based around factories (which is
fine IMO until proven otherwise); changing that would require a strong
argument and should lead to a complete revision of the basic layout of the
library, in order to be consistent. Maybe for 4.0 :-).]
To stretch the argument, why not create a "UniversalDecomposition" class
with all the methods in it:
getCholeskyL()
getLuL()
getLuU()
getLuP()
getQrQ()
getQrR()
getQrH()
getSvdU()
getSvdS()
getSvdV()
...
and throw "UnsupportedOperationException" as necessary?
Best,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
Why were these removed? Was it because the alternative implementations
weren't different enough?
On Thu, Oct 6, 2011 at 12:47 AM, Luc Maisonobe <Lu...@free.fr>wrote:
> Le 06/10/2011 04:04, Sébastien Brisard a écrit :
>
>>
>>> What is the group's feeling on factory classes? +1 from me (obviously)
>>>
>>> +1 for me, I like factories.
>>
>
> -0. We used factories and removed most of them. In fact, what we removed
> was when factories are used to hide implementation and only an interface and
> a factory are available to users. This is a different cases.
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
Yes, this application would be similar to the ones you nixed. It would be a
factory returning an abstract class, with the appropriate methods throwing
exceptions (like getRank for the non-pivoting version-as Ted mentions in a
later entry in this blog).
As Ted asks, what is the issue with this?
On Thu, Oct 6, 2011 at 2:47 AM, Luc Maisonobe <Lu...@free.fr> wrote:
> Le 06/10/2011 04:04, Sébastien Brisard a écrit :
>
>
>>> What is the group's feeling on factory classes? +1 from me (obviously)
>>>
>>> +1 for me, I like factories.
>>
>
> -0. We used factories and removed most of them. In fact, what we removed
> was when factories are used to hide implementation and only an interface and
> a factory are available to users. This is a different cases.
>
> There are other places too where we still have some factories, even in new
> code (an example would be Region in the geometry package if I remember
> well).
>
> Luc
>
>
>
> Sébastien
>>
>> ------------------------------**------------------------------**---------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>>
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 06/10/2011 04:04, Sébastien Brisard a écrit :
>>
>> What is the group's feeling on factory classes? +1 from me (obviously)
>>
> +1 for me, I like factories.
-0. We used factories and removed most of them. In fact, what we removed
was when factories are used to hide implementation and only an interface
and a factory are available to users. This is a different cases.
There are other places too where we still have some factories, even in
new code (an example would be Region in the geometry package if I
remember well).
Luc
> Sébastien
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Sébastien Brisard <se...@m4x.org>.
>
> What is the group's feeling on factory classes? +1 from me (obviously)
>
+1 for me, I like factories.
Sébastien
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
+1 from me as well. They are a lot of what makes guava so nice to use.
On Wed, Oct 5, 2011 at 5:24 PM, Greg Sterijevski <gs...@gmail.com>wrote:
> What is the group's feeling on factory classes? +1 from me (obviously)
>
> On Wed, Oct 5, 2011 at 7:14 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > I think that a factory style is fine. Sadly, CM uses constructor style a
> > lot and it may be hard to change that expectation. I suppose that the
> QRD
> > constructor can call some other factory and just delegate to the results.
> > Looks ugly but keeps the constructor style. If losing the constructor
> > style is allowable then the factory is a great option.
> >
> > Whether the two implementations exist in one class or two should be an
> > implementation detail that the user really doesn't see much or care
> about.
> > No need to hide it, but absolutely no reason to put it in their face,
> > either.
> >
> > Pushing WIP code is always good.
> >
> > On Wed, Oct 5, 2011 at 5:06 PM, Greg Sterijevski <gsterijevski@gmail.com
> > >wrote:
> >
> > > I am sympathetic to this point of view [one class two algorithms-Ted's
> > > point], but it seems like a step into the C world. Could we not
> > accomplish
> > > the same through some factory method? We can have two classes, but the
> > user
> > > might only get a reference to the abstract base. The other reason is
> that
> > > the implementations are quite dissimilar. The current QRDecomposition
> > class
> > > works on the transpose of the A matrix. Luc's implementation works on
> the
> > > data matrix in the original shape. Furthermore, the solver classes
> > exhibit
> > > differences imposed by pivoting and the transpose vs non transpose
> > > difference.
> > >
> > > I am also of the mind we should keep both classes. Speed is a big
> issue,
> > > especially if one is making the case (as Luc has) that java is
> > competitive
> > > to fortran. I do think it might be a good idea to refactor (if
> possible)
> > > the
> > > Marquardt class. The decomposition is identical.
> > >
> > > Does it make sense to push the code for further comments or should I
> > attach
> > > it and the tests to this email thread?
> > >
> > > -Greg
> > >
> > > On Wed, Oct 5, 2011 at 3:46 PM, Ted Dunning <te...@gmail.com>
> > wrote:
> > >
> > > > Actually, I think it really would be nicer for the user to have one
> > class
> > > > that internally decides which implementation to use. The user
> doesn't
> > > see
> > > > this as two classes. They see it as a single operation (QR
> > > decomposition)
> > > > that might have a little different behavior (default slow and
> > featureful,
> > > > optionally faster).
> > > >
> > > > On Wed, Oct 5, 2011 at 1:38 PM, Gilles Sadowski <
> > > > gilles@harfang.homelinux.org> wrote:
> > > >
> > > > > From what I understand, the user will know whether he needs speed
> or
> > > the
> > > > > more flexible (but less efficient) alternative.
> > > > > Thus it is fine to have two implementations in separate classes:
> The
> > > user
> > > > > instantiates the one he needs.
> > > > > We could name them "PivotingQRDecomposition" and
> > "FastQRDecomposition"
> > > in
> > > > > order to emphasize their expected usage.
> > > > > Any potentially duplicated code should go in a new
> > > > > "AbstractQRDecomposition"
> > > > > which the other two will inherit from.
> > > > >
> > > >
> > >
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
What is the group's feeling on factory classes? +1 from me (obviously)
On Wed, Oct 5, 2011 at 7:14 PM, Ted Dunning <te...@gmail.com> wrote:
> I think that a factory style is fine. Sadly, CM uses constructor style a
> lot and it may be hard to change that expectation. I suppose that the QRD
> constructor can call some other factory and just delegate to the results.
> Looks ugly but keeps the constructor style. If losing the constructor
> style is allowable then the factory is a great option.
>
> Whether the two implementations exist in one class or two should be an
> implementation detail that the user really doesn't see much or care about.
> No need to hide it, but absolutely no reason to put it in their face,
> either.
>
> Pushing WIP code is always good.
>
> On Wed, Oct 5, 2011 at 5:06 PM, Greg Sterijevski <gsterijevski@gmail.com
> >wrote:
>
> > I am sympathetic to this point of view [one class two algorithms-Ted's
> > point], but it seems like a step into the C world. Could we not
> accomplish
> > the same through some factory method? We can have two classes, but the
> user
> > might only get a reference to the abstract base. The other reason is that
> > the implementations are quite dissimilar. The current QRDecomposition
> class
> > works on the transpose of the A matrix. Luc's implementation works on the
> > data matrix in the original shape. Furthermore, the solver classes
> exhibit
> > differences imposed by pivoting and the transpose vs non transpose
> > difference.
> >
> > I am also of the mind we should keep both classes. Speed is a big issue,
> > especially if one is making the case (as Luc has) that java is
> competitive
> > to fortran. I do think it might be a good idea to refactor (if possible)
> > the
> > Marquardt class. The decomposition is identical.
> >
> > Does it make sense to push the code for further comments or should I
> attach
> > it and the tests to this email thread?
> >
> > -Greg
> >
> > On Wed, Oct 5, 2011 at 3:46 PM, Ted Dunning <te...@gmail.com>
> wrote:
> >
> > > Actually, I think it really would be nicer for the user to have one
> class
> > > that internally decides which implementation to use. The user doesn't
> > see
> > > this as two classes. They see it as a single operation (QR
> > decomposition)
> > > that might have a little different behavior (default slow and
> featureful,
> > > optionally faster).
> > >
> > > On Wed, Oct 5, 2011 at 1:38 PM, Gilles Sadowski <
> > > gilles@harfang.homelinux.org> wrote:
> > >
> > > > From what I understand, the user will know whether he needs speed or
> > the
> > > > more flexible (but less efficient) alternative.
> > > > Thus it is fine to have two implementations in separate classes: The
> > user
> > > > instantiates the one he needs.
> > > > We could name them "PivotingQRDecomposition" and
> "FastQRDecomposition"
> > in
> > > > order to emphasize their expected usage.
> > > > Any potentially duplicated code should go in a new
> > > > "AbstractQRDecomposition"
> > > > which the other two will inherit from.
> > > >
> > >
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
I think that a factory style is fine. Sadly, CM uses constructor style a
lot and it may be hard to change that expectation. I suppose that the QRD
constructor can call some other factory and just delegate to the results.
Looks ugly but keeps the constructor style. If losing the constructor
style is allowable then the factory is a great option.
Whether the two implementations exist in one class or two should be an
implementation detail that the user really doesn't see much or care about.
No need to hide it, but absolutely no reason to put it in their face,
either.
Pushing WIP code is always good.
On Wed, Oct 5, 2011 at 5:06 PM, Greg Sterijevski <gs...@gmail.com>wrote:
> I am sympathetic to this point of view [one class two algorithms-Ted's
> point], but it seems like a step into the C world. Could we not accomplish
> the same through some factory method? We can have two classes, but the user
> might only get a reference to the abstract base. The other reason is that
> the implementations are quite dissimilar. The current QRDecomposition class
> works on the transpose of the A matrix. Luc's implementation works on the
> data matrix in the original shape. Furthermore, the solver classes exhibit
> differences imposed by pivoting and the transpose vs non transpose
> difference.
>
> I am also of the mind we should keep both classes. Speed is a big issue,
> especially if one is making the case (as Luc has) that java is competitive
> to fortran. I do think it might be a good idea to refactor (if possible)
> the
> Marquardt class. The decomposition is identical.
>
> Does it make sense to push the code for further comments or should I attach
> it and the tests to this email thread?
>
> -Greg
>
> On Wed, Oct 5, 2011 at 3:46 PM, Ted Dunning <te...@gmail.com> wrote:
>
> > Actually, I think it really would be nicer for the user to have one class
> > that internally decides which implementation to use. The user doesn't
> see
> > this as two classes. They see it as a single operation (QR
> decomposition)
> > that might have a little different behavior (default slow and featureful,
> > optionally faster).
> >
> > On Wed, Oct 5, 2011 at 1:38 PM, Gilles Sadowski <
> > gilles@harfang.homelinux.org> wrote:
> >
> > > From what I understand, the user will know whether he needs speed or
> the
> > > more flexible (but less efficient) alternative.
> > > Thus it is fine to have two implementations in separate classes: The
> user
> > > instantiates the one he needs.
> > > We could name them "PivotingQRDecomposition" and "FastQRDecomposition"
> in
> > > order to emphasize their expected usage.
> > > Any potentially duplicated code should go in a new
> > > "AbstractQRDecomposition"
> > > which the other two will inherit from.
> > >
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
I am sympathetic to this point of view [one class two algorithms-Ted's
point], but it seems like a step into the C world. Could we not accomplish
the same through some factory method? We can have two classes, but the user
might only get a reference to the abstract base. The other reason is that
the implementations are quite dissimilar. The current QRDecomposition class
works on the transpose of the A matrix. Luc's implementation works on the
data matrix in the original shape. Furthermore, the solver classes exhibit
differences imposed by pivoting and the transpose vs non transpose
difference.
I am also of the mind we should keep both classes. Speed is a big issue,
especially if one is making the case (as Luc has) that java is competitive
to fortran. I do think it might be a good idea to refactor (if possible) the
Marquardt class. The decomposition is identical.
Does it make sense to push the code for further comments or should I attach
it and the tests to this email thread?
-Greg
On Wed, Oct 5, 2011 at 3:46 PM, Ted Dunning <te...@gmail.com> wrote:
> Actually, I think it really would be nicer for the user to have one class
> that internally decides which implementation to use. The user doesn't see
> this as two classes. They see it as a single operation (QR decomposition)
> that might have a little different behavior (default slow and featureful,
> optionally faster).
>
> On Wed, Oct 5, 2011 at 1:38 PM, Gilles Sadowski <
> gilles@harfang.homelinux.org> wrote:
>
> > From what I understand, the user will know whether he needs speed or the
> > more flexible (but less efficient) alternative.
> > Thus it is fine to have two implementations in separate classes: The user
> > instantiates the one he needs.
> > We could name them "PivotingQRDecomposition" and "FastQRDecomposition" in
> > order to emphasize their expected usage.
> > Any potentially duplicated code should go in a new
> > "AbstractQRDecomposition"
> > which the other two will inherit from.
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
Actually, I think it really would be nicer for the user to have one class
that internally decides which implementation to use. The user doesn't see
this as two classes. They see it as a single operation (QR decomposition)
that might have a little different behavior (default slow and featureful,
optionally faster).
On Wed, Oct 5, 2011 at 1:38 PM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> From what I understand, the user will know whether he needs speed or the
> more flexible (but less efficient) alternative.
> Thus it is fine to have two implementations in separate classes: The user
> instantiates the one he needs.
> We could name them "PivotingQRDecomposition" and "FastQRDecomposition" in
> order to emphasize their expected usage.
> Any potentially duplicated code should go in a new
> "AbstractQRDecomposition"
> which the other two will inherit from.
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hi.
> Sounds like it would be nice to have both implementations in the same class
> with a "usePivoting(boolean)" method to select which is used. I would
> recommend pivoting as the default since it gives fewer surprises and more
> diagnostic information to the naive user.
>
> Except for the extra indexing costs, a pivoting implementation should be
> about twice as costly as a non-pivoting implementation. If you don't do the
> pivoting by indirection, this could be significantly more due to copying.
>
> I haven't had instances where I would have much cared, but it would be nice
> to have the option for extra speed if I needed it.
>
> On Wed, Oct 5, 2011 at 10:52 AM, Luc Maisonobe <Lu...@free.fr>wrote:
>
> > 4. Implement the best algorithm as "QRDecomposition" in ("linear"), and
> >> remove duplicate code ("LevenbergMarquardt" will call the
> >> implementation
> >> in "linear"; if replacing the LM currently internal version makes some
> >> test fail, we should worry and look for the bug either in LM or in the
> >> new QR or in the tests).
> >>
> >
> > I'm not sure one implementation only is always feasible. The one I put in
> > Levenberg-Marquardt is perhaps more suited to some cases because of
> > pivoting, but I'm quite sure it is not as efficient as the classical one
> > which is really fast (I always used it as an example in conferences to show
> > that Java can be as fast as fortran in some application, because it is as
> > fast as lapack with ATLAS blas on matrices up to about 1000 rows and
> > columns).
>From what I understand, the user will know whether he needs speed or the
more flexible (but less efficient) alternative.
Thus it is fine to have two implementations in separate classes: The user
instantiates the one he needs.
We could name them "PivotingQRDecomposition" and "FastQRDecomposition" in
order to emphasize their expected usage.
Any potentially duplicated code should go in a new "AbstractQRDecomposition"
which the other two will inherit from.
I don't see that there would be any benefit in reviving a "QRDecomposition"
interface.
However, it would be nice to create another one:
---CUT---
public interface DecompositionSolverProvider {
DecompositionSolver getSolver();
}
---CUT---
which all "...Decomposition" would implement (all of them already provide
this "getSolver" method).
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
Sounds like it would be nice to have both implementations in the same class
with a "usePivoting(boolean)" method to select which is used. I would
recommend pivoting as the default since it gives fewer surprises and more
diagnostic information to the naive user.
Except for the extra indexing costs, a pivoting implementation should be
about twice as costly as a non-pivoting implementation. If you don't do the
pivoting by indirection, this could be significantly more due to copying.
I haven't had instances where I would have much cared, but it would be nice
to have the option for extra speed if I needed it.
On Wed, Oct 5, 2011 at 10:52 AM, Luc Maisonobe <Lu...@free.fr>wrote:
> 4. Implement the best algorithm as "QRDecomposition" in ("linear"), and
>> remove duplicate code ("LevenbergMarquardt" will call the
>> implementation
>> in "linear"; if replacing the LM currently internal version makes some
>> test fail, we should worry and look for the bug either in LM or in the
>> new QR or in the tests).
>>
>
> I'm not sure one implementation only is always feasible. The one I put in
> Levenberg-Marquardt is perhaps more suited to some cases because of
> pivoting, but I'm quite sure it is not as efficient as the classical one
> which is really fast (I always used it as an example in conferences to show
> that Java can be as fast as fortran in some application, because it is as
> fast as lapack with ATLAS blas on matrices up to about 1000 rows and
> columns).
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 05/10/2011 18:02, Gilles Sadowski a écrit :
> On Wed, Oct 05, 2011 at 10:18:19AM -0500, Greg Sterijevski wrote:
>> Hi Gilles,
>>
>> There are currently [at least] two qr decompositions in existence in cm.
>> There is QRDecomposition in package linear and there is embedded in
>> LevenbergMarquardtOptimizer the guts of a pivoting QR decomposition. So
>> adding a PivotingQRDecomposition class in linear would initially push that
>> to 3 implementations. Here are a couple of scenarios:
>>
>> 1. Eliminate QRDecomposition from linear. Eliminate LevenbergMarquardt's
>> embed qr decompositon and have the PivotingQRDecomposition become the de
>> jure standard.
>>
>> 2. Eliminate just QRDecomposition, not touching Marquardt-Levenberg. (Don't
>> play with something that works)
>>
>> 3. Keep all three until the next major release, marking QRDecomposition (the
>> class) as deprecated.
>
> 4. Implement the best algorithm as "QRDecomposition" in ("linear"), and
> remove duplicate code ("LevenbergMarquardt" will call the implementation
> in "linear"; if replacing the LM currently internal version makes some
> test fail, we should worry and look for the bug either in LM or in the
> new QR or in the tests).
I'm not sure one implementation only is always feasible. The one I put
in Levenberg-Marquardt is perhaps more suited to some cases because of
pivoting, but I'm quite sure it is not as efficient as the classical one
which is really fast (I always used it as an example in conferences to
show that Java can be as fast as fortran in some application, because it
is as fast as lapack with ATLAS blas on matrices up to about 1000 rows
and columns).
Luc
>
> Gilles
>
>> -Greg
>>
>> On Wed, Oct 5, 2011 at 9:39 AM, Gilles Sadowski<
>> gilles@harfang.homelinux.org> wrote:
>>
>>> On Wed, Oct 05, 2011 at 08:46:55AM -0500, Greg Sterijevski wrote:
>>>> Hi Gilles,
>>>>
>>>> The class passes all current tests for QRDecomposition. Are you
>>> suggesting I
>>>> rip out the QRDecomposition from OLSMultipleRegression...etc and then
>>> make
>>>> sure there are no test failures? Or are you suggestion a new set of
>>> tests?
>>>
>>> None of the above, I guess (IIUC).
>>> I'm just saying that if "QR decomposition" is a well defined concept, it
>>> should be implemented in the class "QRDecomposition" in package "linear",
>>> and classes that need the functionality should "import" it from there.
>>> I.e.
>>> there should not be duplicate code (which from what I read in this thread,
>>> seems to exist in "OLSMultipleRegression" and
>>> "LevenbergMarquardtOptimizer").
>>>
>>>
>>> Gilles
>>>
>>>>
>>>> -Greg
>>>>
>>>> On Wed, Oct 5, 2011 at 5:16 AM, Gilles Sadowski<
>>>> gilles@harfang.homelinux.org> wrote:
>>>>
>>>>> Hi.
>>>>>
>>>>>>> A while back I was interested in being able to do pivoting qr
>>>>>>> decomposition. I noticed that Chris Nix submitted a patch, but he
>>>>> indicated
>>>>>>> that he had more work to do (testing and filling in functionality).
>>> In
>>>>> the
>>>>>>> discussion around this, Luc suggested that I look at the QR
>>>>> decomposition in
>>>>>>> Levenberg-Marquardt. I did just that a few days ago. The code was
>>> very
>>>>> clear
>>>>>>> and nicely written (kudos to Luc). So, I copied the routine and
>>> made a
>>>>> new
>>>>>>> PivotingQRDecomposition class. The class is intended as a "drop in
>>>>>>> replacement" for QRDecomposition. I also copied the QRSolverTest
>>> and
>>>>>>> QRDecompositionTest. With the exception of testUnderdetermined in
>>> the
>>>>> solver
>>>>>>> test and testAEqualQR in QRDecompositionTest, the tests are
>>> unchanged
>>>>> (and
>>>>>>> all pass!). With testUndertermined, the "zeroed" rows of the
>>> solution
>>>>> matrix
>>>>>>> are interspersed throughout the matrix (because of pivoting). So I
>>>>> change
>>>>>>> the test to count all the rows that have zero norms, and check that
>>> it
>>>>> is
>>>>>>> the correct number. In testAEqualQR, I added a multiplication by
>>> the
>>>>>>> permutation matrix.
>>>>>>>
>>>>>>> What is the best way to proceed? I don't want to trounce the
>>> additions
>>>>> that
>>>>>>> Chris made, but it looks like Chris has more sophisticated classes
>>> in
>>>>> mind.
>>>>>>> I don't see this proposed change competing with his. Does it make
>>> sense
>>>>> to
>>>>>>> bring back QRDecomposition interface (sorry Sebastien)? We can then
>>>>> keep
>>>>>>> both implementations until we are satisfied the pivoting one works.
>>>>>
>>>>> -1
>>>>> Please do the required testing. Only the "current best" implementation
>>>>> should remain.
>>>>>
>>>>>
>>>>> Regards,
>>>>> Gilles
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>>>
>>>>>
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Wed, Oct 05, 2011 at 10:18:19AM -0500, Greg Sterijevski wrote:
> Hi Gilles,
>
> There are currently [at least] two qr decompositions in existence in cm.
> There is QRDecomposition in package linear and there is embedded in
> LevenbergMarquardtOptimizer the guts of a pivoting QR decomposition. So
> adding a PivotingQRDecomposition class in linear would initially push that
> to 3 implementations. Here are a couple of scenarios:
>
> 1. Eliminate QRDecomposition from linear. Eliminate LevenbergMarquardt's
> embed qr decompositon and have the PivotingQRDecomposition become the de
> jure standard.
>
> 2. Eliminate just QRDecomposition, not touching Marquardt-Levenberg. (Don't
> play with something that works)
>
> 3. Keep all three until the next major release, marking QRDecomposition (the
> class) as deprecated.
4. Implement the best algorithm as "QRDecomposition" in ("linear"), and
remove duplicate code ("LevenbergMarquardt" will call the implementation
in "linear"; if replacing the LM currently internal version makes some
test fail, we should worry and look for the bug either in LM or in the
new QR or in the tests).
Gilles
> -Greg
>
> On Wed, Oct 5, 2011 at 9:39 AM, Gilles Sadowski <
> gilles@harfang.homelinux.org> wrote:
>
> > On Wed, Oct 05, 2011 at 08:46:55AM -0500, Greg Sterijevski wrote:
> > > Hi Gilles,
> > >
> > > The class passes all current tests for QRDecomposition. Are you
> > suggesting I
> > > rip out the QRDecomposition from OLSMultipleRegression...etc and then
> > make
> > > sure there are no test failures? Or are you suggestion a new set of
> > tests?
> >
> > None of the above, I guess (IIUC).
> > I'm just saying that if "QR decomposition" is a well defined concept, it
> > should be implemented in the class "QRDecomposition" in package "linear",
> > and classes that need the functionality should "import" it from there.
> > I.e.
> > there should not be duplicate code (which from what I read in this thread,
> > seems to exist in "OLSMultipleRegression" and
> > "LevenbergMarquardtOptimizer").
> >
> >
> > Gilles
> >
> > >
> > > -Greg
> > >
> > > On Wed, Oct 5, 2011 at 5:16 AM, Gilles Sadowski <
> > > gilles@harfang.homelinux.org> wrote:
> > >
> > > > Hi.
> > > >
> > > > > > A while back I was interested in being able to do pivoting qr
> > > > > > decomposition. I noticed that Chris Nix submitted a patch, but he
> > > > indicated
> > > > > > that he had more work to do (testing and filling in functionality).
> > In
> > > > the
> > > > > > discussion around this, Luc suggested that I look at the QR
> > > > decomposition in
> > > > > > Levenberg-Marquardt. I did just that a few days ago. The code was
> > very
> > > > clear
> > > > > > and nicely written (kudos to Luc). So, I copied the routine and
> > made a
> > > > new
> > > > > > PivotingQRDecomposition class. The class is intended as a "drop in
> > > > > > replacement" for QRDecomposition. I also copied the QRSolverTest
> > and
> > > > > > QRDecompositionTest. With the exception of testUnderdetermined in
> > the
> > > > solver
> > > > > > test and testAEqualQR in QRDecompositionTest, the tests are
> > unchanged
> > > > (and
> > > > > > all pass!). With testUndertermined, the "zeroed" rows of the
> > solution
> > > > matrix
> > > > > > are interspersed throughout the matrix (because of pivoting). So I
> > > > change
> > > > > > the test to count all the rows that have zero norms, and check that
> > it
> > > > is
> > > > > > the correct number. In testAEqualQR, I added a multiplication by
> > the
> > > > > > permutation matrix.
> > > > > >
> > > > > > What is the best way to proceed? I don't want to trounce the
> > additions
> > > > that
> > > > > > Chris made, but it looks like Chris has more sophisticated classes
> > in
> > > > mind.
> > > > > > I don't see this proposed change competing with his. Does it make
> > sense
> > > > to
> > > > > > bring back QRDecomposition interface (sorry Sebastien)? We can then
> > > > keep
> > > > > > both implementations until we are satisfied the pivoting one works.
> > > >
> > > > -1
> > > > Please do the required testing. Only the "current best" implementation
> > > > should remain.
> > > >
> > > >
> > > > Regards,
> > > > Gilles
> > > >
> > > > ---------------------------------------------------------------------
> > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > >
> > > >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > For additional commands, e-mail: dev-help@commons.apache.org
> >
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
Hi Gilles,
There are currently [at least] two qr decompositions in existence in cm.
There is QRDecomposition in package linear and there is embedded in
LevenbergMarquardtOptimizer the guts of a pivoting QR decomposition. So
adding a PivotingQRDecomposition class in linear would initially push that
to 3 implementations. Here are a couple of scenarios:
1. Eliminate QRDecomposition from linear. Eliminate LevenbergMarquardt's
embed qr decompositon and have the PivotingQRDecomposition become the de
jure standard.
2. Eliminate just QRDecomposition, not touching Marquardt-Levenberg. (Don't
play with something that works)
3. Keep all three until the next major release, marking QRDecomposition (the
class) as deprecated.
-Greg
On Wed, Oct 5, 2011 at 9:39 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> On Wed, Oct 05, 2011 at 08:46:55AM -0500, Greg Sterijevski wrote:
> > Hi Gilles,
> >
> > The class passes all current tests for QRDecomposition. Are you
> suggesting I
> > rip out the QRDecomposition from OLSMultipleRegression...etc and then
> make
> > sure there are no test failures? Or are you suggestion a new set of
> tests?
>
> None of the above, I guess (IIUC).
> I'm just saying that if "QR decomposition" is a well defined concept, it
> should be implemented in the class "QRDecomposition" in package "linear",
> and classes that need the functionality should "import" it from there.
> I.e.
> there should not be duplicate code (which from what I read in this thread,
> seems to exist in "OLSMultipleRegression" and
> "LevenbergMarquardtOptimizer").
>
>
> Gilles
>
> >
> > -Greg
> >
> > On Wed, Oct 5, 2011 at 5:16 AM, Gilles Sadowski <
> > gilles@harfang.homelinux.org> wrote:
> >
> > > Hi.
> > >
> > > > > A while back I was interested in being able to do pivoting qr
> > > > > decomposition. I noticed that Chris Nix submitted a patch, but he
> > > indicated
> > > > > that he had more work to do (testing and filling in functionality).
> In
> > > the
> > > > > discussion around this, Luc suggested that I look at the QR
> > > decomposition in
> > > > > Levenberg-Marquardt. I did just that a few days ago. The code was
> very
> > > clear
> > > > > and nicely written (kudos to Luc). So, I copied the routine and
> made a
> > > new
> > > > > PivotingQRDecomposition class. The class is intended as a "drop in
> > > > > replacement" for QRDecomposition. I also copied the QRSolverTest
> and
> > > > > QRDecompositionTest. With the exception of testUnderdetermined in
> the
> > > solver
> > > > > test and testAEqualQR in QRDecompositionTest, the tests are
> unchanged
> > > (and
> > > > > all pass!). With testUndertermined, the "zeroed" rows of the
> solution
> > > matrix
> > > > > are interspersed throughout the matrix (because of pivoting). So I
> > > change
> > > > > the test to count all the rows that have zero norms, and check that
> it
> > > is
> > > > > the correct number. In testAEqualQR, I added a multiplication by
> the
> > > > > permutation matrix.
> > > > >
> > > > > What is the best way to proceed? I don't want to trounce the
> additions
> > > that
> > > > > Chris made, but it looks like Chris has more sophisticated classes
> in
> > > mind.
> > > > > I don't see this proposed change competing with his. Does it make
> sense
> > > to
> > > > > bring back QRDecomposition interface (sorry Sebastien)? We can then
> > > keep
> > > > > both implementations until we are satisfied the pivoting one works.
> > >
> > > -1
> > > Please do the required testing. Only the "current best" implementation
> > > should remain.
> > >
> > >
> > > Regards,
> > > Gilles
> > >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > For additional commands, e-mail: dev-help@commons.apache.org
> > >
> > >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Wed, Oct 05, 2011 at 08:46:55AM -0500, Greg Sterijevski wrote:
> Hi Gilles,
>
> The class passes all current tests for QRDecomposition. Are you suggesting I
> rip out the QRDecomposition from OLSMultipleRegression...etc and then make
> sure there are no test failures? Or are you suggestion a new set of tests?
None of the above, I guess (IIUC).
I'm just saying that if "QR decomposition" is a well defined concept, it
should be implemented in the class "QRDecomposition" in package "linear",
and classes that need the functionality should "import" it from there. I.e.
there should not be duplicate code (which from what I read in this thread,
seems to exist in "OLSMultipleRegression" and "LevenbergMarquardtOptimizer").
Gilles
>
> -Greg
>
> On Wed, Oct 5, 2011 at 5:16 AM, Gilles Sadowski <
> gilles@harfang.homelinux.org> wrote:
>
> > Hi.
> >
> > > > A while back I was interested in being able to do pivoting qr
> > > > decomposition. I noticed that Chris Nix submitted a patch, but he
> > indicated
> > > > that he had more work to do (testing and filling in functionality). In
> > the
> > > > discussion around this, Luc suggested that I look at the QR
> > decomposition in
> > > > Levenberg-Marquardt. I did just that a few days ago. The code was very
> > clear
> > > > and nicely written (kudos to Luc). So, I copied the routine and made a
> > new
> > > > PivotingQRDecomposition class. The class is intended as a "drop in
> > > > replacement" for QRDecomposition. I also copied the QRSolverTest and
> > > > QRDecompositionTest. With the exception of testUnderdetermined in the
> > solver
> > > > test and testAEqualQR in QRDecompositionTest, the tests are unchanged
> > (and
> > > > all pass!). With testUndertermined, the "zeroed" rows of the solution
> > matrix
> > > > are interspersed throughout the matrix (because of pivoting). So I
> > change
> > > > the test to count all the rows that have zero norms, and check that it
> > is
> > > > the correct number. In testAEqualQR, I added a multiplication by the
> > > > permutation matrix.
> > > >
> > > > What is the best way to proceed? I don't want to trounce the additions
> > that
> > > > Chris made, but it looks like Chris has more sophisticated classes in
> > mind.
> > > > I don't see this proposed change competing with his. Does it make sense
> > to
> > > > bring back QRDecomposition interface (sorry Sebastien)? We can then
> > keep
> > > > both implementations until we are satisfied the pivoting one works.
> >
> > -1
> > Please do the required testing. Only the "current best" implementation
> > should remain.
> >
> >
> > Regards,
> > Gilles
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > For additional commands, e-mail: dev-help@commons.apache.org
> >
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
Hi Gilles,
The class passes all current tests for QRDecomposition. Are you suggesting I
rip out the QRDecomposition from OLSMultipleRegression...etc and then make
sure there are no test failures? Or are you suggestion a new set of tests?
-Greg
On Wed, Oct 5, 2011 at 5:16 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> Hi.
>
> > > A while back I was interested in being able to do pivoting qr
> > > decomposition. I noticed that Chris Nix submitted a patch, but he
> indicated
> > > that he had more work to do (testing and filling in functionality). In
> the
> > > discussion around this, Luc suggested that I look at the QR
> decomposition in
> > > Levenberg-Marquardt. I did just that a few days ago. The code was very
> clear
> > > and nicely written (kudos to Luc). So, I copied the routine and made a
> new
> > > PivotingQRDecomposition class. The class is intended as a "drop in
> > > replacement" for QRDecomposition. I also copied the QRSolverTest and
> > > QRDecompositionTest. With the exception of testUnderdetermined in the
> solver
> > > test and testAEqualQR in QRDecompositionTest, the tests are unchanged
> (and
> > > all pass!). With testUndertermined, the "zeroed" rows of the solution
> matrix
> > > are interspersed throughout the matrix (because of pivoting). So I
> change
> > > the test to count all the rows that have zero norms, and check that it
> is
> > > the correct number. In testAEqualQR, I added a multiplication by the
> > > permutation matrix.
> > >
> > > What is the best way to proceed? I don't want to trounce the additions
> that
> > > Chris made, but it looks like Chris has more sophisticated classes in
> mind.
> > > I don't see this proposed change competing with his. Does it make sense
> to
> > > bring back QRDecomposition interface (sorry Sebastien)? We can then
> keep
> > > both implementations until we are satisfied the pivoting one works.
>
> -1
> Please do the required testing. Only the "current best" implementation
> should remain.
>
>
> Regards,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hi.
> > A while back I was interested in being able to do pivoting qr
> > decomposition. I noticed that Chris Nix submitted a patch, but he indicated
> > that he had more work to do (testing and filling in functionality). In the
> > discussion around this, Luc suggested that I look at the QR decomposition in
> > Levenberg-Marquardt. I did just that a few days ago. The code was very clear
> > and nicely written (kudos to Luc). So, I copied the routine and made a new
> > PivotingQRDecomposition class. The class is intended as a "drop in
> > replacement" for QRDecomposition. I also copied the QRSolverTest and
> > QRDecompositionTest. With the exception of testUnderdetermined in the solver
> > test and testAEqualQR in QRDecompositionTest, the tests are unchanged (and
> > all pass!). With testUndertermined, the "zeroed" rows of the solution matrix
> > are interspersed throughout the matrix (because of pivoting). So I change
> > the test to count all the rows that have zero norms, and check that it is
> > the correct number. In testAEqualQR, I added a multiplication by the
> > permutation matrix.
> >
> > What is the best way to proceed? I don't want to trounce the additions that
> > Chris made, but it looks like Chris has more sophisticated classes in mind.
> > I don't see this proposed change competing with his. Does it make sense to
> > bring back QRDecomposition interface (sorry Sebastien)? We can then keep
> > both implementations until we are satisfied the pivoting one works.
-1
Please do the required testing. Only the "current best" implementation
should remain.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
Yes, in the interest of brevity I left out the fact that rank is calculated
as well. This is exactly Luc's implementation from Marquardt-Levenberg.
Is this what you are talking about with the cryptic 'all'?
On Wed, Oct 5, 2011 at 7:20 AM, Ted Dunning <te...@gmail.com> wrote:
> All.
>
> On Wed, Oct 5, 2011 at 12:34 AM, Chris Nix <ch...@gmail.com> wrote:
>
> > Additionally, any pivoting QRDecomposition class should also have a
> > getRank() method since it is after all 'rank-revealing' and in most (or
> > all?) cases it would be more efficient than
> > SingularValueDecomposition.getRank().
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Ted Dunning <te...@gmail.com>.
All.
On Wed, Oct 5, 2011 at 12:34 AM, Chris Nix <ch...@gmail.com> wrote:
> Additionally, any pivoting QRDecomposition class should also have a
> getRank() method since it is after all 'rank-revealing' and in most (or
> all?) cases it would be more efficient than
> SingularValueDecomposition.getRank().
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
Chris,
I hope that this isn't stepping on your toes. I was a bit concerned about
that.
-Greg
On Wed, Oct 5, 2011 at 2:34 AM, Chris Nix <ch...@gmail.com> wrote:
> Greg,
>
> Apologies that I've not had more time on this, I started a new job that
> doesn't afford it at the moment, :(.
>
> I would say that a single implementation, with or without pivoting, makes
> sense to save confusion. Your clearer code would be a good choice for
> maintainability.
>
> One possible word of caution with replacing the current implementation with
> a pivoting version is that current users of the QRDecomposition may not
> expect a third factor, namely P, particularly in the solvers. This is not
> really a problem, but it should be well documented as a change to v2 to
> save
> confusion and perhaps method names, ie testAEqualQR should be changed to
> make this clear.
>
> Additionally, any pivoting QRDecomposition class should also have a
> getRank() method since it is after all 'rank-revealing' and in most (or
> all?) cases it would be more efficient than
> SingularValueDecomposition.getRank().
>
> Chris.
>
>
> On 5 October 2011 05:05, Greg Sterijevski <gs...@gmail.com> wrote:
>
> > My apologies! Forgot to tag the subject line.
> >
> > On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski <gsterijevski@gmail.com
> > >wrote:
> >
> > > Hello all,
> > >
> > > A while back I was interested in being able to do pivoting qr
> > > decomposition. I noticed that Chris Nix submitted a patch, but he
> > indicated
> > > that he had more work to do (testing and filling in functionality). In
> > the
> > > discussion around this, Luc suggested that I look at the QR
> decomposition
> > in
> > > Levenberg-Marquardt. I did just that a few days ago. The code was very
> > clear
> > > and nicely written (kudos to Luc). So, I copied the routine and made a
> > new
> > > PivotingQRDecomposition class. The class is intended as a "drop in
> > > replacement" for QRDecomposition. I also copied the QRSolverTest and
> > > QRDecompositionTest. With the exception of testUnderdetermined in the
> > solver
> > > test and testAEqualQR in QRDecompositionTest, the tests are unchanged
> > (and
> > > all pass!). With testUndertermined, the "zeroed" rows of the solution
> > matrix
> > > are interspersed throughout the matrix (because of pivoting). So I
> change
> > > the test to count all the rows that have zero norms, and check that it
> is
> > > the correct number. In testAEqualQR, I added a multiplication by the
> > > permutation matrix.
> > >
> > > What is the best way to proceed? I don't want to trounce the additions
> > that
> > > Chris made, but it looks like Chris has more sophisticated classes in
> > mind.
> > > I don't see this proposed change competing with his. Does it make sense
> > to
> > > bring back QRDecomposition interface (sorry Sebastien)? We can then
> keep
> > > both implementations until we are satisfied the pivoting one works.
> > >
> > > Thoughts?
> > >
> > > -Greg
> > >
> >
>
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Chris Nix <ch...@gmail.com>.
Greg,
Apologies that I've not had more time on this, I started a new job that
doesn't afford it at the moment, :(.
I would say that a single implementation, with or without pivoting, makes
sense to save confusion. Your clearer code would be a good choice for
maintainability.
One possible word of caution with replacing the current implementation with
a pivoting version is that current users of the QRDecomposition may not
expect a third factor, namely P, particularly in the solvers. This is not
really a problem, but it should be well documented as a change to v2 to save
confusion and perhaps method names, ie testAEqualQR should be changed to
make this clear.
Additionally, any pivoting QRDecomposition class should also have a
getRank() method since it is after all 'rank-revealing' and in most (or
all?) cases it would be more efficient than
SingularValueDecomposition.getRank().
Chris.
On 5 October 2011 05:05, Greg Sterijevski <gs...@gmail.com> wrote:
> My apologies! Forgot to tag the subject line.
>
> On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski <gsterijevski@gmail.com
> >wrote:
>
> > Hello all,
> >
> > A while back I was interested in being able to do pivoting qr
> > decomposition. I noticed that Chris Nix submitted a patch, but he
> indicated
> > that he had more work to do (testing and filling in functionality). In
> the
> > discussion around this, Luc suggested that I look at the QR decomposition
> in
> > Levenberg-Marquardt. I did just that a few days ago. The code was very
> clear
> > and nicely written (kudos to Luc). So, I copied the routine and made a
> new
> > PivotingQRDecomposition class. The class is intended as a "drop in
> > replacement" for QRDecomposition. I also copied the QRSolverTest and
> > QRDecompositionTest. With the exception of testUnderdetermined in the
> solver
> > test and testAEqualQR in QRDecompositionTest, the tests are unchanged
> (and
> > all pass!). With testUndertermined, the "zeroed" rows of the solution
> matrix
> > are interspersed throughout the matrix (because of pivoting). So I change
> > the test to count all the rows that have zero norms, and check that it is
> > the correct number. In testAEqualQR, I added a multiplication by the
> > permutation matrix.
> >
> > What is the best way to proceed? I don't want to trounce the additions
> that
> > Chris made, but it looks like Chris has more sophisticated classes in
> mind.
> > I don't see this proposed change competing with his. Does it make sense
> to
> > bring back QRDecomposition interface (sorry Sebastien)? We can then keep
> > both implementations until we are satisfied the pivoting one works.
> >
> > Thoughts?
> >
> > -Greg
> >
>
[MATH] Re: Pivoting QR Decomposition: Take Two!
Posted by Greg Sterijevski <gs...@gmail.com>.
My apologies! Forgot to tag the subject line.
On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski <gs...@gmail.com>wrote:
> Hello all,
>
> A while back I was interested in being able to do pivoting qr
> decomposition. I noticed that Chris Nix submitted a patch, but he indicated
> that he had more work to do (testing and filling in functionality). In the
> discussion around this, Luc suggested that I look at the QR decomposition in
> Levenberg-Marquardt. I did just that a few days ago. The code was very clear
> and nicely written (kudos to Luc). So, I copied the routine and made a new
> PivotingQRDecomposition class. The class is intended as a "drop in
> replacement" for QRDecomposition. I also copied the QRSolverTest and
> QRDecompositionTest. With the exception of testUnderdetermined in the solver
> test and testAEqualQR in QRDecompositionTest, the tests are unchanged (and
> all pass!). With testUndertermined, the "zeroed" rows of the solution matrix
> are interspersed throughout the matrix (because of pivoting). So I change
> the test to count all the rows that have zero norms, and check that it is
> the correct number. In testAEqualQR, I added a multiplication by the
> permutation matrix.
>
> What is the best way to proceed? I don't want to trounce the additions that
> Chris made, but it looks like Chris has more sophisticated classes in mind.
> I don't see this proposed change competing with his. Does it make sense to
> bring back QRDecomposition interface (sorry Sebastien)? We can then keep
> both implementations until we are satisfied the pivoting one works.
>
> Thoughts?
>
> -Greg
>