[MOAB-dev] Matrix3 EigenDecomp Bug

Thu Aug 20 10:07:17 CDT 2015

Hi Vijay,

That makes perfect sense. Thank you for clearing that up. I'll make sure 
to develop on top of master from now on.

On an additional note, I think that this fix should improve the scaling 
of the OBBTree significantly. Attached are the results before and after 
the fix on a few different models.

Cheers,

Patrick

On 08/19/2015 11:40 AM, Vijay S. Mahadevan wrote:
> 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
>>>>>>

-- 
Patrick C. Shriwise
Research Fellow
University of Wisconsin - Madison
Engineering Research Building - Rm. 428
1500 Engineering Drive
Madison, WI 53706
(608) 446-8173

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Eig_fix_rf.png
Type: image/png
Size: 34418 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/moab-dev/attachments/20150820/5d61b13f/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: MOAB_master_rf.png
Type: image/png
Size: 34965 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/moab-dev/attachments/20150820/5d61b13f/attachment-0003.png>