If Q is an orthogonal matrix, then its inverse is equal to its transpose. So, Q times its inverse is equal to the indentity matrix, and Q times its transpose is equal to the indentity matrix. They are equal.
Cramer's Rule is almost never implemented for computers since it is so slow and you almost never need the exact value of the determinant.
Fastest way to inverse an orthogonal 4x4 matrix?
To form the inverse of a orthogonal matrix with entries A_ij, swap each A_ij with A_ji. In doing so, you need not swap components along the diagonal since A_11 = A_11, A_22 = A_22, etc.
probably it's faster to calculate it as
matrix4x4 result;
result[1,1]=param[1,1]
result[1,2]=param[2,1]
and so-on. Then calculate translation vector, by writing multiplying by transposed param.
I think it might be more reasonable to make class that contains 3x3 matrix and translation vector, or 3x4 matrix. And define multiplication and inverse on that class, and multiplication with vector. (not hard to do), and conversion to 4x4 matrix.
I have similar class that contains quaternion(for rotation) and vector(for translation), with operations multiply, inverse, etc. That class works exactly as if it's matrix that does rotation and translation only.
matrix4x4 result;
result[1,1]=param[1,1]
result[1,2]=param[2,1]
and so-on. Then calculate translation vector, by writing multiplying by transposed param.
I think it might be more reasonable to make class that contains 3x3 matrix and translation vector, or 3x4 matrix. And define multiplication and inverse on that class, and multiplication with vector. (not hard to do), and conversion to 4x4 matrix.
I have similar class that contains quaternion(for rotation) and vector(for translation), with operations multiply, inverse, etc. That class works exactly as if it's matrix that does rotation and translation only.
About Cramer's Rule. Please take the following information seriously.
To solve a systems of equations using Cramer's Rule requires about O((n+1)!) operations. (Please forgive that my quote above was wrong.)
Gaussian Elimination requires around O(n3/3) operations.
For a 2x2 matrix, Cramer's Rule requires around 6 operations, compared with Gaussian Elimination's 3.
So, Cramer's Rule takes TWICE AS LONG as Gaussian Elimination even for a lowly 2x2 matrix. Still, for a 2x2 it is cheap enough that you may consider using it----implemented in closed form instead of a generic loop, to avoid loop overhead.
For a 4x4 matrix, Cramer's Rule requires around 120 operations, compared with Gaussian Elimination's 21.
Cramer's Rule takes nearly SIX TIMES AS LONG as Gaussian Elimination for a 4x4 matrix.
Conclusion? NEVER, EVER use Cramer's Rule to solve a system of equations or find the inverse of a matrix larger than 2x2 if you are doing the inverse very frequently, for example every frame in a game render loop.
I'll close with a quote from "Computational Fluid Mechanics and Heat Transfer" by Tannehill et al. The quote is paraphrased for brevity.
"A number of horror stories have been told about the large computation time required to solve systems of equations by Cramer's Rule. The operation count for solving this [11 x 11] problem by Cramer's Rule is 82!, a very large number (4.75 x 10122). If we applied Cramer's Rule to this problem using a machine capable of performing 100 megaflops, the calculation would require about 3.20 x 10101 years. Using Gaussian Elimination would only require a fraction of a second on the same machine."
Even on modern computers, to use Cramer's Rule on an 11x11 matrix would require darned near TEN TIMES THE AGE OF THE UNIVERSE to solve!
(If you think 11x11 is a larger matrix than you will ever see, consider that multi-rigid body systems with many simultaneous contacts, and also very simple fluid dynamics (water, smoke) systems will involve matrices larger than this---though you won't need the inverse of the matrix and won't be doing Gaussian Elimination either.)
Moral of the story: Cramer's Rule SUCKS for ANY matrix larger than a 2x2!
[Edited by - grhodes_at_work on September 25, 2004 10:16:29 PM]
To solve a systems of equations using Cramer's Rule requires about O((n+1)!) operations. (Please forgive that my quote above was wrong.)
Gaussian Elimination requires around O(n3/3) operations.
For a 2x2 matrix, Cramer's Rule requires around 6 operations, compared with Gaussian Elimination's 3.
So, Cramer's Rule takes TWICE AS LONG as Gaussian Elimination even for a lowly 2x2 matrix. Still, for a 2x2 it is cheap enough that you may consider using it----implemented in closed form instead of a generic loop, to avoid loop overhead.
For a 4x4 matrix, Cramer's Rule requires around 120 operations, compared with Gaussian Elimination's 21.
Cramer's Rule takes nearly SIX TIMES AS LONG as Gaussian Elimination for a 4x4 matrix.
Conclusion? NEVER, EVER use Cramer's Rule to solve a system of equations or find the inverse of a matrix larger than 2x2 if you are doing the inverse very frequently, for example every frame in a game render loop.
I'll close with a quote from "Computational Fluid Mechanics and Heat Transfer" by Tannehill et al. The quote is paraphrased for brevity.
"A number of horror stories have been told about the large computation time required to solve systems of equations by Cramer's Rule. The operation count for solving this [11 x 11] problem by Cramer's Rule is 82!, a very large number (4.75 x 10122). If we applied Cramer's Rule to this problem using a machine capable of performing 100 megaflops, the calculation would require about 3.20 x 10101 years. Using Gaussian Elimination would only require a fraction of a second on the same machine."
Even on modern computers, to use Cramer's Rule on an 11x11 matrix would require darned near TEN TIMES THE AGE OF THE UNIVERSE to solve!
(If you think 11x11 is a larger matrix than you will ever see, consider that multi-rigid body systems with many simultaneous contacts, and also very simple fluid dynamics (water, smoke) systems will involve matrices larger than this---though you won't need the inverse of the matrix and won't be doing Gaussian Elimination either.)
Moral of the story: Cramer's Rule SUCKS for ANY matrix larger than a 2x2!
[Edited by - grhodes_at_work on September 25, 2004 10:16:29 PM]
Another tip I'd like to show here, because it's something I noticed by myself and hardly ever saw it anywhere else. It's a very clear way to memorize 3x3 general matrix inversion 'geometrically', I could say visually.
If your 3x3 matrix is made of 3 columns (that is the local axes) [X,Y,Z] then the inverse is just the transposed of (the comatrix) [Y^Z,Z^X,X^Y] divided by the determinant which is (X^Y).Z = (Y^Z).X = (Z^X).Z. These 3 last formulas represent the same volume of a paralleloid (english word ?) defined by the three edges X, Y, Z. That's what an adjoint matrix is all about in 3D.
Then you immediately see that for an orthonormal matrix, X=Y^Z, Y=Z^X, Z=X^Y, (X^Y).Z = (Y^Z).X = (Z^X).Z = 1. And this demonstrates the inversion <=> transposition theorem.
Thus with a cross product and a dot product is all you need to write a general 3x3 inversion.
You maybe wondered how a math professor could invert a 3x3 numerical matrix or linear system in his head. Now you know why.
With the same demonstration as in my first post you can see how to deal with a translation added. How a 3x4 3D affine matrix (a 4x4 with {0,0,0,1} as last row) can be 'inversed'.
If your 3x3 matrix is made of 3 columns (that is the local axes) [X,Y,Z] then the inverse is just the transposed of (the comatrix) [Y^Z,Z^X,X^Y] divided by the determinant which is (X^Y).Z = (Y^Z).X = (Z^X).Z. These 3 last formulas represent the same volume of a paralleloid (english word ?) defined by the three edges X, Y, Z. That's what an adjoint matrix is all about in 3D.
Then you immediately see that for an orthonormal matrix, X=Y^Z, Y=Z^X, Z=X^Y, (X^Y).Z = (Y^Z).X = (Z^X).Z = 1. And this demonstrates the inversion <=> transposition theorem.
Thus with a cross product and a dot product is all you need to write a general 3x3 inversion.
You maybe wondered how a math professor could invert a 3x3 numerical matrix or linear system in his head. Now you know why.
With the same demonstration as in my first post you can see how to deal with a translation added. How a 3x4 3D affine matrix (a 4x4 with {0,0,0,1} as last row) can be 'inversed'.
Quote:Original post by grhodes_at_work
About Cramer's Rule. Please take the following information seriously.
To solve a systems of equations using Cramer's Rule requires about O((n+1)!) operations. (Please forgive that my quote above was wrong.)
Gaussian Elimination requires around O(n3/3) operations.
For a 2x2 matrix, Cramer's Rule requires around 6 operations, compared with Gaussian Elimination's 3.
So, Cramer's Rule takes TWICE AS LONG as Gaussian Elimination even for a lowly 2x2 matrix. Still, for a 2x2 it is cheap enough that you may consider using it----implemented in closed form instead of a generic loop, to avoid loop overhead.
For a 4x4 matrix, Cramer's Rule requires around 120 operations, compared with Gaussian Elimination's 21.
Cramer's Rule takes nearly SIX TIMES AS LONG as Gaussian Elimination for a 4x4 matrix.
Like i said before i'm not using cramer's rule, using adjoints methods:
M-1 = (1 / det(M)) * adj(M)
i read that this is faster for small matrices upto 4-by-4 because of its branchless nature & vectorizable operations in hardware but Gaussian's elimination does less mathematical operations.
[Edited by - snk_kid on September 26, 2004 2:34:58 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
