Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 luc.maison...@free.frwrote: 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!
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 gil...@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!
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 luc.maison...@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.orgdev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org --**--**- To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.orgdev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
On Thu, Oct 6, 2011 at 1:56 PM, Gilles Sadowski gil...@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!
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!
Yeah... but this is a rough neighborhood for folk like you and me. On Thu, Oct 6, 2011 at 5:52 PM, Greg Sterijevski gsterijev...@gmail.comwrote: 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!
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 ted.dunn...@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 gsterijev...@gmail.comwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
On Thu, Oct 6, 2011 at 9:13 PM, Phil Steitz phil.ste...@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!
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 gsterijev...@gmail.com wrote: My apologies! Forgot to tag the subject line. On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski gsterijev...@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!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
All. On Wed, Oct 5, 2011 at 12:34 AM, Chris Nix chris@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!
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 gil...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 ted.dunn...@gmail.com wrote: All. On Wed, Oct 5, 2011 at 12:34 AM, Chris Nix chris@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!
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 chris@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 gsterijev...@gmail.com wrote: My apologies! Forgot to tag the subject line. On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski gsterijev...@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!
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 gil...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 gil...@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 gil...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 gil...@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 gil...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 gil...@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 gil...@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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 luc.maison...@free.frwrote: 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!
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 luc.maison...@free.frwrote: 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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [MATH] Re: Pivoting QR Decomposition: Take Two!
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 gil...@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!
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 ted.dunn...@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 gil...@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!
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 gsterijev...@gmail.comwrote: 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 ted.dunn...@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 gil...@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!
What is the group's feeling on factory classes? +1 from me (obviously) On Wed, Oct 5, 2011 at 7:14 PM, Ted Dunning ted.dunn...@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 gsterijev...@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 ted.dunn...@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 gil...@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!
+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 gsterijev...@gmail.comwrote: What is the group's feeling on factory classes? +1 from me (obviously) On Wed, Oct 5, 2011 at 7:14 PM, Ted Dunning ted.dunn...@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 gsterijev...@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 ted.dunn...@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 gil...@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!
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-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
[MATH] Re: Pivoting QR Decomposition: Take Two!
My apologies! Forgot to tag the subject line. On Tue, Oct 4, 2011 at 8:35 PM, Greg Sterijevski gsterijev...@gmail.comwrote: 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