triangular matrix

Hi,

Its okay. Asking for advice in homework that involves game development is appropriate here as long as you are not asking for a complete answer to a stated problem.

I appreciate that you mentioned that your question is related to game development and you are not asking for the complete answer to an assignment. I''m still curious to know what aspect of your game requires that you calculate determinants of large matrices (because I can''t imagine off the top of my head). Also, would be nice to know what class the assignment is for. Since you know how to calculate determinants, have you taken a linear algebra class? (I would expect the answer to your question to be presented in such a class.)

A bientot,

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

It is actually just a Computer Science AP class at my high school. I am trying to go a little above and beyond the call of duty; all of my classmates are making chess and checkers games that do not work and I want to make something more interesting. The game I want to do is that old cannon game (or some other weapon) where you just shoot back and forth at each other. To draw the terrain I was going to use 6th and higher degree least squares regression polynomials. But to do that I need to solve large systems of equations (all of the summations of the least squares in the matrices) so I needed to calculate the determinant.

But, after I posted I figured out how to do the upper triangle matrix (kind of like row reduction) ... and then after that I figured that I was going about everything wrong. I should have just used row reduction in the first place to solve the equations.

So that is the story ... the reason it didn''t seem related is because I was taking the insanely more difficult route.

Well you made an EXCELLENT discovery when you decided to use row reduction (Gaussian elimination) to solve the system. Sounds like you were originally using Cramer's rule to find the inverse of the matrix, to solve x = A^-1b from Ax=b. The Cramer's rule approach is always a poor approach, and is the most expensive method for all systems with > 2 or 3 equations. In fact, once the number of equations gets to be moderate (hundreds, maybe thousands, which is not really a huge number of equations), it can literally take years to run on a fast computer whereas even simple Gaussian elimination runs in minutes. I remember reading a description of a problem that Cramer's rule could not complete in a time period greater than the age of the universe while other methods could solve the problem in at worst a few hours. I kid you not. You've overcome an extremely common linear algebra misconception! (The only time I could ever recommend Cramer's rule is for very rare occasions when you need to solve a system symbolically rather than numerically. For example, in computational fluid dynamics we often need to find symbolically the eigenvalues of the Navier-Stokes equations, and that means dealing with a system of 5 nasty equations. Those eigenvalues can be found using Cramer's rule, but the algebra is a nightmare.)

Did you find out how to use LU decomposition to get the upper triangular matrix?

I applaud you for taking the initiative to do something unique and interesting with your project. Good luck on your computer science class!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on December 10, 2001 4:42:15 PM

I''m not sure if it is LU decomposition that I used but this is what it looks like (I am initially doing this in java-script just for testing purposes):

// makes this matrix an upper triangle matrix Object.MP_Library.Matrix.prototype.Matrix_upper_triangle = function () { // loop through every column of this matrix for (var k = 0; k < this.num_columns; k++) { // loop through every row below the k-k element for (var j = (k+1); j < this.num_rows; j++) { // make the element zero by doing an elementary row operation this.Matrix_elem_CMA (k, (-this.element[j][k] / this.element[k][k]), j); } } }

"Matrix" is a class and the method "Matrix_elem_CMA" does the elementary row operation of adding one row times a constant to another row. I pick the constants to multiply the rows by so that it will cancel out the first element. I''m having a hard time explain, but I am sure you understand. Once I found the upper triangle matrix I just multiplied the diagonals together to find the determinant (even though I really didn''t have to).

Thanks for the information.