Mailing-List: contact dev-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Commons Developers List" <dev@commons.apache.org>
Received-SPF: pass (athena.apache.org: domain of gsterijevski@gmail.com
 designates 209.85.215.43 as permitted sender)
MIME-Version: 1.0
In-Reply-To: 
 <CAJwFCa0buExb9DhpdYA-fhhFJvrZ7zneJgNMzo4_Gn+D60dCHA@mail.gmail.com>
References: <20110907104543.GR2590@dusk.harfang.homelinux.org>
	<4E6767C3.1060103@free.fr>
	<20110907130559.GV2590@dusk.harfang.homelinux.org>
	<4E676DB3.7080905@free.fr>
	<20110907133412.GW2590@dusk.harfang.homelinux.org>
	<CAJwFCa2sSO7otKRPxEO0fFtqc7eqW12n2dka_1jm0CZiYCnTvw@mail.gmail.com>
	<CACMPRi11Z56WhAVPgkfguAA87z++atJdWhnKBi3X=-BmxqMnNw@mail.gmail.com>
	<CAJwFCa0buExb9DhpdYA-fhhFJvrZ7zneJgNMzo4_Gn+D60dCHA@mail.gmail.com>
Date: Wed, 7 Sep 2011 23:26:06 -0500
Message-ID: 
 <CACMPRi2nmS9C107MDTw-zF-nF6=RE8JgFj9HvdB5ucUGdX128w@mail.gmail.com>
Subject: Re: [Math] "LUDecomposition" in "AbstractLeastSquaresOptimizer"
From: Greg Sterijevski <gsterijevski@gmail.com>
To: Commons Developers List <dev@commons.apache.org>
Content-Type: multipart/alternative; boundary=0015174c3f9a970a4204ac6675aa

--0015174c3f9a970a4204ac6675aa
Content-Type: text/plain; charset=ISO-8859-1

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
> > > >
> > > >
> > >
> >
>

--0015174c3f9a970a4204ac6675aa--