[MOAB-dev] Matrix3 EigenDecomp Bug

Tue Aug 18 21:54:17 CDT 2015

Patrick, thanks for finding this bug. This is quite bad. Any algorithm
that relied on the eigenvectors would've failed in a bad way. We will
make reviewing the PR a high priority since this shouldn't have passed
through the cracks this long anyway.

On another note, I'm planning to add a lightweight, templated dense
matrix/vector classes soon that support pivoted LU, QR and SVD. Some
of these are needs driven due to our surface reconstruction work and
others due to discretization kernels. So if there is a broader use for
dense LA classes, would be glad to hear what other requirements need
to be considered.

> I think you should patch against 'master' rather than 'develop'.  The

As Paul mentions, always start your development based on up to date
master. The develop branch can be unstable and is an evolving feature
integration test bed. This is especially true now since we merged few
things contributed by Kitware that still need some refining. In
general, master should always be the starting HEAD.

Vijay

On Tue, Aug 18, 2015 at 9:15 PM, Paul Wilson <paul.wilson at wisc.edu> wrote:
> Hi Patrick,
>
> I think you should patch against 'master' rather than 'develop'.  The
> 'develop' branch may requires an update to CMake?  It is using something
> called GenerateExportHeader
>
> Paul
>
>
> On 08/18/2015 08:48 PM, Patrick Shriwise wrote:
>
> Cool! I hope it helps. We'll fine out soon. I actually found some time to
> get the fix into a branch tonight but I'm actually having trouble compiling
> with the develop branch.
>
> Getting an error like:
>
> In file included from
> ../../../src/test/dagmc/dagmc_pointinvol_test.cpp:10:0:
> ../../../src/tools/dagmc/DagMC.hpp:4:26: fatal error: dagmc_export.h: No
> such file or directory
>  #include "dagmc_export.h"
>
> These export headers are new to me. Any ideas?
>
> Cheers,
>
> Patrick
>
> On 08/18/2015 08:16 PM, Grindeanu, Iulian R. 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
>
>
>
> --
> -- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ --
> Paul Wilson ~ UW-Madison ~ 608-263-0807 ~ cal: http://go.wisc.edu/pphw-cal
> Professor, Engineering Physics. ~ http://cnerg.engr.wisc.edu
> Faculty Director, Advanced Computing Infrastructure ~ http://aci.wisc.edu