[MOAB-dev] Matrix3 EigenDecomp Bug

Wed Aug 19 11:40:08 CDT 2015

Patrick, the confusion is perhaps triggered due to mixing terminology.
Essentially, in MOAB we use the standard git workflow model [1] where
instead of next, our integration testing branch is named develop. This
is partly because when I implemented the model, I started with the
gitflow workflow [2], which does use develop as a start for all
feature branches. But I found this inconvenient because PR merges
always get tested against master leading to unnecessary confusion of
merge conflicts.

Anyway, apart from the branch name develop, our current model follows
[1] and not [2]. Sorry about the confusion if any. I had to adapt our
workflow that suited best the development needs and this is what we
have for now :) Hope things are clear now. Let me know if you have
questions.

Vijay

[1] https://www.kernel.org/pub/software/scm/git/docs/gitworkflows.html
[2] https://www.atlassian.com/git/tutorials/comparing-workflows/gitflow-workflow

On Wed, Aug 19, 2015 at 12:11 AM, Patrick Shriwise <shriwise at wisc.edu> wrote:
> 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
>>>>>
>