On 9/7/11 9:26 PM, Greg Sterijevski wrote: > I thought that QR is of O(n^3) complexity, while LU is probably in the > vicinity of O(n^2.5). While this is not a barn burning improvement, it is an > improvement. Consider that if you are using the covariance of the parameters > in deciding how to make the next step (some kind of inverse hessian rule), > the repeated calls to inverse add up?
Sounds a little contrived. I can't see the speed difference as really material given that we are talking about parameter covariance matrices. I would be fine with any of the three - LU, Cholesky (which may also be fastest, btw) or QR. Phil > > Would it be a terrific eyesore to include a constructor with a boolean > argument that says bUseQR? The call to LU is localized, so there is minimal > refactoring. One could also pass the boolean into the getCovariances > method. > > > > > On Wed, Sep 7, 2011 at 4:48 PM, Ted Dunning <ted.dunn...@gmail.com> wrote: > >> It shouldn't be all that different from QR (at most about 2x different). >> >> On Wed, Sep 7, 2011 at 1:16 PM, Greg Sterijevski <gsterijev...@gmail.com >>> wrote: >>> It is also my recollection that LU is very quick to calculate. Would it >> be >>> possible to allow users to choose? >>> >>> On Wed, Sep 7, 2011 at 3:07 PM, Ted Dunning <ted.dunn...@gmail.com> >> wrote: >>>> Does the LUDecomposition not use pivots? LU should always do so since >> it >>>> is >>>> numerically unstable otherwise. I would be surprised if it doesn't >> given >>>> the normal level of quality in commons math. >>>> >>>> QR is, of course, almost always preferable to LU as you note. But I >>> would >>>> be surprised at radically different answers. >>>> >>>> Perhaps the only real difference between the two methods in this one >> case >>>> is >>>> a difference in threshold. >>>> >>>> What is the condition number of your matrix? >>>> >>>> On Wed, Sep 7, 2011 at 6:34 AM, Gilles Sadowski < >>>> gil...@harfang.homelinux.org> wrote: >>>> >>>>> Hi. >>>>> >>>>>>>>> In class "AbstractLeastSquaresOptimizer" (in >>>>> "o.a.c.m.optimization.general"), >>>>>>>>> the method "getCovariances()" uses "LUDecompositionImpl" to >>> compute >>>>> the >>>>>>>>> inverse of a matrix. >>>>>>>>> In my application, this leads to a "SingularMatrixException". If >> I >>>>> change >>>>>>>>> "LUDecompositionImpl" to "QRDecompositionImpl", no exception is >>>>> raised. >>>>>>>>> Also, keeping "LUDecompositionImpl" but passing a much lower >>>>> singularity >>>>>>>>> threshold, does not raise the exception either. >>>>>>>>> >>>>>>>>> Thus, I wonder whether there was a reason for using "LU", and if >>>> not, >>>>>>>>> whether I could change the decomposition solver to "QR" (as this >>> is >>>> a >>>>>>>>> cleaner solution than guessing a good value for the threshold). >>>>>>>> There are no reason for LU decomposition, and QR decomposition is >>>>>>>> known to be more stable. So I would also consider switching to >> this >>>>>>>> algorithm is a cleaner solution. >>>>>>> Fine. I'll open a JIRA issue. >>>>>>> >>>>>>> A unit test "testNonInvertible" in >> "LevenbergMarquardtOptimizerTest" >>>>> fails >>>>>>> with the change to "QRDecomposition" because no >>>>> "SingularMatrixException" >>>>>>> is raised anymore. >>>>>>> What was the purpose of that test? >>>>>> The purpose was to check that impossible problems were detected >>>> properly. >>>>> My question should have been clearer: Was the previous behaviour >>> correct >>>>> (i.e. an exception *must* be raised somehow)? >>>>> The switch to "QR" seems to imply that a previously impossible >> problem >>> is >>>>> now quite possible. So, is the problem really impossible or was the >>> test >>>>> actually testing a fragile implementation of "getCovariances()"? >>>>> >>>>> >>>>> 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
