[MOAB-dev] Matrix3 EigenDecomp Bug

[Patrick Shriwise]

Hi Vijay,

I'll push this fix into the master branch as its a critical bug fix. In 
general, I thought that the majority of development was intended to be 
done on top of the develop branch and then eventually merged into master 
near the time of a new release. Am I misunderstanding?

Cheers,


Patrick

On 08/18/2015 11:06 PM, Vijay S. Mahadevan wrote:
>> Anyway, GeomTopoTool is using obb tree, and FBEngine is using GeomTopoTool, so the implications of this bug are many.
> I'm more concerned about the dependence of the Coupler on Matrix3
> class. Even though we don't use eigen decomposition anywhere, makes me
> wonder what else is screwed up here. I couldn't find any unit tests
> for this either.
>
> Vijay
>
> On Tue, Aug 18, 2015 at 8:16 PM, Grindeanu, Iulian R.
> <iulian at mcs.anl.gov> wrote:
>> So it was a message from Steve Jackson, in March 2010 :)
>> The link is not working anymore, but maybe someone still has that presentation.
>>
>> Anyway, GeomTopoTool is using obb tree, and FBEngine is using GeomTopoTool, so the implications of this bug are many.
>>
>> thanks for finding it!
>>
>> Iulian
>>
>> "
>> Cc:
>>   fathom at lists.mcs.anl.gov
>> Tuesday, March 02, 2010 10:44 AM
>> I will be presenting some slides on OBB tree performance profiling at this meeting.  They can be found here: http://mywebspace.wisc.edu/stjackson/web/fathom_slides_march2.pdf
>>
>> ~S
>> "
>> ________________________________________
>> From: Patrick Shriwise [shriwise at wisc.edu]
>> Sent: Tuesday, August 18, 2015 7:26 PM
>> To: Paul Wilson; Grindeanu, Iulian R.; moab-dev at mcs.anl.gov
>> Subject: Re: [MOAB-dev] Matrix3 EigenDecomp Bug
>>
>> Hi all,
>>
>> As Paul said, nothing for sure as to the improvement for scaling, but it
>> would make sense. As the number of triangles goes up, deeper trees, more
>> boxes.
>>
>> And you're right, this is only used in the OBB Tree. That makes sense as
>> it's the only relatively complex linear algebra capability we need so
>> far. Otherwise we'd be accessing a known library for that I assume.
>>
>> I'll submit a PR to fix the problem this week (my sister is visiting or
>> I'd do it tomorrow) and report back on the scaling asap.
>>
>> Cheers,
>>
>> Patrick
>>
>> On 08/18/2015 05:47 PM, Paul Wilson wrote:
>>> Hi Iulian,
>>>
>>> On 08/18/2015 05:16 PM, Grindeanu, Iulian R. wrote:
>>>> Ouch
>>>> only obb tree is using it.
>>>> So only obb tree is affected by it
>>>>
>>>> indeed, it is returning cartVect's as you said
>>>> It should be returning the transpose
>>>>
>>>> strange nobody noticed
>>>>
>>>> I remember somebody did a study of our obb tree and it was not
>>>> scaling properly
>>>>
>>>> Could this be the reason?
>>> This is almost certainly true.  Patrick discovered this while trying
>>> to understand why some DAGMC problems were so slow.  He visualized the
>>> OBB trees from that problem and they didn't really make any sense.  It
>>> was a problem with many long high aspect triangles that were aligned
>>> to an axis, but the OBB was not aligned to that axis.
>>>
>>> Early indications are that it will make an improvement - we'll know
>>> more soon.
>>>
>>> Paul
>>>
>>>>
>>>> ________________________________________
>>>> From: moab-dev-bounces at mcs.anl.gov [moab-dev-bounces at mcs.anl.gov] on
>>>> behalf of shriwise [shriwise at wisc.edu]
>>>> Sent: Tuesday, August 18, 2015 3:56 PM
>>>> To: moab-dev at mcs.anl.gov
>>>> Subject: [MOAB-dev] Matrix3 EigenDecomp Bug
>>>>
>>>> Hey all,
>>>>
>>>> After a day or so of working on this, I found an error in the Eigenvalue
>>>> decomposition function provided by Matrix3.
>>>>
>>>> I believe that its computation is correct, but the way that it returns
>>>> the Eigenvectors is at the very least ambiguous, and I would argue that
>>>> it is simply incorrect.
>>>>
>>>> Typically the matrix produced by this decomposition contains the vectors
>>>> in a column-based manner, but the vectors are being returned in an array
>>>> of CartVects where each CartVect contains a row of the resulting matrix.
>>>> The problem being that the solution matrix in this case is indeed column
>>>> based. So while the correct information is available, it is returned in
>>>> such a way that leads one to believe each CartVect contains one of the
>>>> EigenVectors when this is not the case.
>>>>
>>>> I found this by comparing the results of this function to that of a
>>>> common linear algebra library, Armadillo.
>>>>
>>>> I've attached the test program I was using if anyone is curious.
>>>>
>>>> Normally, I would simply fix it and create a PR but I'm not quite
>>>> certain how to proceed. I think probably the best way is to fix this at
>>>> the source in Matrix3.hpp but I don't want any reliant functionality to
>>>> be affected without notice. This is a long standing bug affecting the
>>>> OBBTree. I'll start working on a fix tomorrow morning, perhaps by
>>>> finding anywhere this is used and double checking the use of the
>>>> returned Eigenvectors. Does that sound amenable to all?
>>>>
>>>> Cheers,
>>>>
>>>> --
>>>> Patrick C. Shriwise
>>>> Research Fellow
>>>> University of Wisconsin - Madison
>>>> Engineering Research Building - Rm. 428
>>>> 1500 Engineering Drive
>>>> Madison, WI 53706
>>>> (608) 446-8173
>>>>