commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <phil.ste...@gmail.com>
Subject Re: [Math] "LUDecomposition" in "AbstractLeastSquaresOptimizer"
Date Thu, 08 Sep 2011 07:41:09 GMT
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.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
>>>>>
>>>>>


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message