4 ms·

It's worth pointing out that you should rarely, if ever, use exact formulas since there are a lot of problems with numerical stability amongst other things. Oft

by omn123 13y ago

It's worth pointing out that you should rarely, if ever, use exact formulas since there are a lot of problems with numerical stability amongst other things. Often it is faster to just numerically solve the system. For example, in your case you are solving Ax=b which you can easily solve by a simple LU decomposition. Plus if your A changes, your exact formula is wrong, so using an LU decomposition just makes sense. Plus your code will look way cleaner as well. And way easier to debug. http://en.wikipedia.org/wiki/LU_decomposition http://en.wikipedia.org/wiki/LU_decomposition

hiker 13y ago
His system of equations is not linear so vanilla Ax=b won't work.
- omn123 13y ago
  It is actually linear. a,b,c,d are the unknowns and x1 and x2 are the inputs. A bit confusing since normally x1,x2 denote the unknowns.
  - zmk_ 13y ago
    Not if you are doing econometrics/statistics.
  - tomrod 13y ago
    Unless you like econometrics: then X are data, betas and gammas and sigmas are unknown (oh my!). Jargon is fun, unless I want to communicate across fields :/.
    - omn123 13y ago
      Well today I learned. I never knew that. Stupid mathematics and its inconsistent notation.
      - tomrod 13y ago
        It makes sense when you look at historical development, but there is no reason to learn separate notations now without learning all sides :).
- sanskritabelt 13y ago
  He's solving for abcd, which is linear in powers of x. I'm not going to argue for what's the correct solution, but it's certainly not that mess.
albertzeyer 13y ago
In case that the exact formulas for this solution would be numerically unstable, why would the LU decomposition improve the numerical stability? Also, why should it be faster? Well, to be fair, in that example, if the compiler does those `pow(x2 - x1, 3.)` calls multiple times, this would not be optimal, but otherwise, it should be ok. I did this because I will probably never ever change the matrix A here and I wanted to make that code very fast. Otherwise, it's of course a good idea to use some more generic solution.
- omn123 13y ago
  I'm not implying yours are not unstable, it's just there is a chance it might be. Typically exact formulas exhibit such properties. LU decomposition is numerically stable, for the most part. You can run into problems with floating point arithmetic if you're not careful. This just has to do with the way you solve the problem. By breaking up the matrix into an upper and lower triangular part and solving the resulting triangular system, you often avoid things like powers or square roots and just reduce everything to basic addition and multiplication which tend to have more stable numerical properties. As for speed, well in this small case of N=4 there is probably very little speed increase since LU is O(N^{3}), although this can be improved depending on symmetries of the matrix. Maybe for N=5 I might write out the exact formulas but beyond that I would just a LU solver since the amount of code for an LU solver is fairly compact. But, as you correctly point out, if you are never changing the matrix A then you are probably safe with writing it out this way. I just come from a numerical fluids background so seeing exact formulas makes me uneasy. And in my work since the number of grid points N tends to be variable so general formulas are not available. Plus I've noticed a lot of programmers tend to not know numerical algorithms. In fairness, I don't blame them. All the numerical computations courses I've taken and TAed are very boring and don't make you do anything fun and numerical analysis has this reputation of being dry. If you actually made them write stuff like a Navier-Stokes solver, you would get them interested. By the way if you want to learn more about numerical linear algebra, which is the cornerstone of most scientific and high performance computing, I personally enjoy Trefethen and Bau's book. Although it's aimed at a mathematical audience and assumes such.
  - 13y ago
exDM69 13y ago
The conventional wisdom (in scientific computing) that you seldom need to compute an inverse of a matrix does not apply to computer graphics. 4x4 matrix inverse is one of the most useful functions in computer graphics and is used a lot. It is most often used as a hand rolled 4x4 matrix inversion function, not a generic NxN matrix inversion.

by omn123 13y ago

hiker 13y ago

His system of equations is not linear so vanilla Ax=b won't work.

omn123 13y ago
It is actually linear. a,b,c,d are the unknowns and x1 and x2 are the inputs. A bit confusing since normally x1,x2 denote the unknowns.
- zmk_ 13y ago
  Not if you are doing econometrics/statistics.
- tomrod 13y ago
  Unless you like econometrics: then X are data, betas and gammas and sigmas are unknown (oh my!). Jargon is fun, unless I want to communicate across fields :/.
  - omn123 13y ago
    Well today I learned. I never knew that. Stupid mathematics and its inconsistent notation.
    - tomrod 13y ago
      It makes sense when you look at historical development, but there is no reason to learn separate notations now without learning all sides :).
sanskritabelt 13y ago
He's solving for abcd, which is linear in powers of x. I'm not going to argue for what's the correct solution, but it's certainly not that mess.

albertzeyer 13y ago

In case that the exact formulas for this solution would be numerically unstable, why would the LU decomposition improve the numerical stability? Also, why should it be faster? Well, to be fair, in that example, if the compiler does those `pow(x2 - x1, 3.)` calls multiple times, this would not be optimal, but otherwise, it should be ok. I did this because I will probably never ever change the matrix A here and I wanted to make that code very fast. Otherwise, it's of course a good idea to use some more generic solution.

omn123 13y ago
I'm not implying yours are not unstable, it's just there is a chance it might be. Typically exact formulas exhibit such properties. LU decomposition is numerically stable, for the most part. You can run into problems with floating point arithmetic if you're not careful. This just has to do with the way you solve the problem. By breaking up the matrix into an upper and lower triangular part and solving the resulting triangular system, you often avoid things like powers or square roots and just reduce everything to basic addition and multiplication which tend to have more stable numerical properties. As for speed, well in this small case of N=4 there is probably very little speed increase since LU is O(N^{3}), although this can be improved depending on symmetries of the matrix. Maybe for N=5 I might write out the exact formulas but beyond that I would just a LU solver since the amount of code for an LU solver is fairly compact. But, as you correctly point out, if you are never changing the matrix A then you are probably safe with writing it out this way. I just come from a numerical fluids background so seeing exact formulas makes me uneasy. And in my work since the number of grid points N tends to be variable so general formulas are not available. Plus I've noticed a lot of programmers tend to not know numerical algorithms. In fairness, I don't blame them. All the numerical computations courses I've taken and TAed are very boring and don't make you do anything fun and numerical analysis has this reputation of being dry. If you actually made them write stuff like a Navier-Stokes solver, you would get them interested. By the way if you want to learn more about numerical linear algebra, which is the cornerstone of most scientific and high performance computing, I personally enjoy Trefethen and Bau's book. Although it's aimed at a mathematical audience and assumes such.
- 13y ago

exDM69 13y ago

The conventional wisdom (in scientific computing) that you seldom need to compute an inverse of a matrix does not apply to computer graphics. 4x4 matrix inverse is one of the most useful functions in computer graphics and is used a lot. It is most often used as a hand rolled 4x4 matrix inversion function, not a generic NxN matrix inversion.