LU is theoretically lower if you have a faster matrix multiply. Otherwise it is about 2n^3/3 + n^2 + n/3, I think.
On Wed, Sep 7, 2011 at 9:26 PM, Greg Sterijevski <gsterijev...@gmail.com>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? > > 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 > > > > > > > > > > > > > > > > > > > >
