commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Sterijevski <gsterijev...@gmail.com>
Subject Re: [Math] "LUDecomposition" in "AbstractLeastSquaresOptimizer"
Date Thu, 08 Sep 2011 04:26:06 GMT
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.dunning@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 <gsterijevski@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.dunning@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 <
> > > gilles@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-unsubscribe@commons.apache.org
> > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > >
> > > >
> > >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message