Sign in to follow this  
ATC

Need help with Matrix decomposition algorithm...

Recommended Posts

Hello again my noble Lords and Ladies, lol...

I'm running through all of the essential data types of my engine (Vector2, Vector3, Vector4, ColorF, Quaternion, Matrix, etc...). I've just fixed all the bugs in my math API and added some optimizations for speed/efficiency. But now I'm left with one last problem... This dreaded Matrix.Decompose method!

I really just don't know wtf I'm doing on this one, which feels unusual and frustrating for a figure-it-out-guy like me... I was able to handle everything else in the API, but this one just escapes me for some reason. I'm a college dropout and self-taught programmer (and self-taught at almost everything else lol...always learned better on my own). I only had a year and one semester of college, so I lack formal education in complex mathematics. So when I look up matrix decomposition, on Wikipedia for instance, it's all a bunch of "junk" and symbols that have no meaning to [i]me[/i]... For example, I have no clue wtf this is supposed to be/mean:


[img]http://upload.wikimedia.org/math/5/b/3/5b382df47b3fe37fcd8ce6db40bc9a9e.png[/img]


I tried implementing this several different times and could never get it to work and yield proper results... it's a very big, mind-numbing operation. Since it would never work I ended up scrapping the code I wrote, so I don't even have code to post. I'm [i]very [/i]sorry for that, as I know it's frowned upon to come here with no code because it shows no [i]effort[/i]. But believe me, I've tried and tried and tried to figure this out. If you've seen any of my other posts over the past few years you'll know I'm not the type of guy who comes here and asks others to do my work for me!

But I really need some help with this... a pseudo-code example, a link to a working implementation in C/C++/C#, an actual implementation of it one of you have done, the implementation from SlimDX/OpenTK/etc... something! I need [i]some [/i]way to understand and/or just get it working. What I understand is [b]code [/b]and the [i]practical application[/i] of mathematics... What I don't understand are these complex, "high-level" theoretical math concepts and funny symbols, formulas and diagrams.

So is there anyone who can help me with this? At this point I'm lost for ideas... :-\

I was always a poor math student... I simply suck at math when I'm not applying it to something useful. When I'm using mathematical concepts in code, however, I'm quite good at it. It's just the odd way my brain works... I hated all my math lessons from Kindergarten to college, but I actually enjoy solving math challenges in programming. That might sound weird or stupid but that's just me lol..

Anyhow, thank you for your valuable time and best regards,

ATC

[b]EDIT:[/b]

It appears SlimDX doesn't even implement their own algorithm! It looks like they're DllImporting it from DirectX... Perhaps that speaks to the mind-numbing complexity of the algorithm, lol? I suspect its really for performance reasons, but maybe it's a bit of both lol

[b]EDIT 2:[/b]

Running through the OpenTK source now too... Apparently it doesn't even [i]have[/i] a Decompose method... Edited by ATC

Share this post


Link to post
Share on other sites
Alright, I am assuming that you are referring to [url="http://en.wikipedia.org/wiki/Cholesky_decomposition#The_Cholesky.E2.80.93Banachiewicz_and_Cholesky.E2.80.93Crout_algorithms"]this particular type[/url] of matrix decomposition. The equation you posted equates the matrix A to the product of L and L[sup]T[/sup] and shows what each element of the resultant matrix is. The article I linked to also gives equations for the various elements of L. I believe the main stumbling block for your understanding of this method is the sigma notation used in the equations. When you see a [url=en.wikipedia.org/wiki/Sigma]capital sigma[/url] in a mathematical equation, it means that you are to sum the term to the right of the sigma up to the limit on the top. I should probably try to give an example:
[img]http://upload.wikimedia.org/math/c/4/4/c44ded964a8098fdd9e0fbe482c88db8.png[/img] This is one of the equations from the linked page, and what the sigma notation is representing here is "sum L(j,k) squared over k from 1 to j-1". So if j is 3 for example, then L(3,3) would be equal to sqrt( A(3,3)-(L(3,1)*L(3,1)+L(3,2)*L(3,2)) ). In my opinion at least, this is a rather simple method once you get past the notation, so I am not sure why OpenTK doesn't implement this method. I also note that this method only works for symmetric matrices, i.e. matrices where the elements on one side of the central diagonal are equal to the corresponding elements on the other side. I hope that my explanation has been sufficiently clear to be of help to you, and will be happy to help explain anything else you are having trouble with (or provide some implementation help if it comes to that).

Share this post


Link to post
Share on other sites
I'm still totally lost lol... Remember, I have no mathematics foundation to help me here, and I'm not even sure what all these "A"s and "L"s are standing in for.

I'm aware there are different types of decomposition algorithms. And I'm not exactly sure which one I need to use? I need to mirror the functionality of Matrix.Decompose found in DirectX and XNA.

Share this post


Link to post
Share on other sites
Sigh... Lol I'm feeling hopeless. I keep scouring Google to try to find some sort of working implementation or something to help me understand it and come back empty-handed each time.

However, I'm having a discussion in another thread on micro-optimization of math routines for my engine's math API, and I'm curious about Intel's Math Kernel Library; which can indeed interface/interop with C#. It appears that Intel actual implements Matrix decomposition in their library. So perhaps I might be able to just defer the work to their implementation if using the MKL would be beneficial to my project? However, I hate to have to give up on something like that... It will, literally, haunt me all the rest of my days if I give up lol.

Share this post


Link to post
Share on other sites
I was once in the same boat as you somewhat, I wanted an algorithm to do LU decomposition because I had heard that you can compute the inverse of a matrix with the decomposition though I never was able to find any information on exactly how to go about that. I did however write a working algorithm to do the decomposition and it should still be here on gamedev somewhere.. (I'll check my posts and then get back to you) though I was told it was lacking "pivoting" or something.. I'm no math genius I just learn enough to get by in programming (and possibly a little extra if it peaks my interest which is more often than not).

hold on let me find that post for you..

EDIT: Sorry, seems my old posts/topics have been deleted =/ .. blows.. well I'm not that great at math and it took me a good few hours to read about LU decomposition and how it is done, to come up with an algorithm. I'm sure if you keep at it you will come up with the algorithm as well it wasn't complex at all if I remember correctly just a few for loops.

It might be around somewhere, I used to go by CodeCriminal around here but have since changed my handle.

EDIT2: Woo found it http://www.gamedev.net/topic/562662-lu-decomposition-and-computing-the-determinant-of-an-nxn-matrixsolved/ Edited by roadysix

Share this post


Link to post
Share on other sites
[quote name='roadysix' timestamp='1348605366' post='4983724']
I'm no math genius I just [u][b]learn enough to get by in programming[/b][/u] (and possibly a little extra if it peaks my interest which is more often than not).
[/quote]

Bingo. You couldn't have described my math skills better lol.

Thank you, I will be awaiting your reply to see the algorithm.

Share this post


Link to post
Share on other sites
Above post

I'm actually working on a small library of random items that include math related things such as vectors and matrices.
if you want id be willing to share code, or give feedback over skype or something though I don't have a mic. I don't yet have a
class for quaternions so I'd be interested to see your implementation. Edited by roadysix

Share this post


Link to post
Share on other sites
[quote name='roadysix' timestamp='1348607000' post='4983741']
Above post

I'm actually working on a small library of random items that include math related things such as vectors and matrices.
if you want id be willing to share code, or give feedback over skype or something though I don't have a mic. I don't yet have a
class for quaternions so I'd be interested to see your implementation.
[/quote]

Sure, you share with me and I'll share with you. You certainly can have/use my Quaternion implementation. :-)

Send me a pm and we can connect on Skype.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this