5 ms·

Is there more context around what exactly he's getting at? In games we use matrix inverses all the time(and since they're usually a specialized affine transform

Is there more context around what exactly he's getting at? In games we use matrix inverses all the time(and since they're usually a specialized affine transform there's cheap shortcuts to calculate them) for stiff like hit detection or animation.

rcxdude 10y ago
More talking about applications where the matrices are large, like statistics, machine learning (but I repeat myself), signal processing, etc. In games pretty much all matrices are around 4x4, instead of millions by millions.
- vvanders 10y ago
  Ah, that's the context I was missing, thanks! In games we can usually just transpose the inner 3x3 R+S, invert scale and handle translation similarly to get a semi-quick inverse.
  - GFK_of_xmaspast 10y ago
    This is the difference between matrices that are SO(3) (which have trivial inverses) and matrices that are just GL(n) (which: don't).
    - Hydraulix989 10y ago
      This. Or you know how to calculate the closed-form inverse a priori like with projection matrices (e.g. gluUnProject).
  - deleted 10y ago
    [deleted]
- theoh 10y ago
  There's an neat technique for fitting RBF representations to dense point clouds. Instead of the impractical matrix inversion, the trick is to solve the linear system with a fast multipole method, similar to the Barnes-Hut algorithm for the n-body problem. Carr, J.C. et al, "Reconstruction and Representation of 3D Objects with Radial Basis Functions", Siggraph 2001 http://dl.acm.org/citation.cfm?id=383266 http://dl.acm.org/citation.cfm?id=383266
- majewsky 10y ago
  Another relevant difference is that precision is not nearly as critical in games as in most numerical applications. Errors of a few percent will likely go unnoticed. Graphics implementations therefore usually only use single precision.
askee 10y ago
In general there are no shortcuts, and when the matrix A is not small (e.g. m x n with m,n << 100), you don't want to invert A, especially if you are only interested in x (from A x = b). Instead, use numerical minimization schemes like conjugated gradients and variants thereof or Quasi-Newton methods (BFGS). Combined with preconditioning as well as regularization or denoising this usually yields good results. Compressive sampling methods (total variation regularization) have received lots of attention in the last ten years.
- mturmon 10y ago
  This comment seems to be a diversion from the question asked. The main point of OP is that solving A x = b is commonly done with factorizations of A, not by explicit computation of inv(A). Resorting to a numerical minimization (like MINRES) would be unusual unless the dimension is much bigger than hundreds. Certainly it's not relevant in a graphics computation with dimension of 3, 4, or 6. My laptop inverts a 4Kx4K general matrix in 1.5s. It solves a 4K linear system in 0.5s.
neutronicus 10y ago
In games you're probably applying many small inverse matrices to many small vectors. In partial differential equations, you solve a single large linear system where the unknown vector represents a field defined at every point on a spatial mesh. In my research, specifically, that spatial mesh can have as many as 10^7 grid points. For linear systems of this size, any exact solution at all is impractical - we exclusively employ iterative approximations built from terms of the form (A^n) b since matrix-vector products are about the only things we can compute in a reasonable amount of time.
- x0x0 10y ago
  And not only are the matrices small, they're probably known (or assumed) to be well-conditioned. Inverting even a small hilbert matrix will probably go boom.
  - GFK_of_xmaspast 10y ago
    Not just well conditioned, but special orthogonal.

rcxdude 10y ago

More talking about applications where the matrices are large, like statistics, machine learning (but I repeat myself), signal processing, etc. In games pretty much all matrices are around 4x4, instead of millions by millions.

vvanders 10y ago
Ah, that's the context I was missing, thanks! In games we can usually just transpose the inner 3x3 R+S, invert scale and handle translation similarly to get a semi-quick inverse.
- GFK_of_xmaspast 10y ago
  This is the difference between matrices that are SO(3) (which have trivial inverses) and matrices that are just GL(n) (which: don't).
  - Hydraulix989 10y ago
    This. Or you know how to calculate the closed-form inverse a priori like with projection matrices (e.g. gluUnProject).
- deleted 10y ago
  [deleted]
theoh 10y ago
There's an neat technique for fitting RBF representations to dense point clouds. Instead of the impractical matrix inversion, the trick is to solve the linear system with a fast multipole method, similar to the Barnes-Hut algorithm for the n-body problem. Carr, J.C. et al, "Reconstruction and Representation of 3D Objects with Radial Basis Functions", Siggraph 2001 http://dl.acm.org/citation.cfm?id=383266 http://dl.acm.org/citation.cfm?id=383266
majewsky 10y ago
Another relevant difference is that precision is not nearly as critical in games as in most numerical applications. Errors of a few percent will likely go unnoticed. Graphics implementations therefore usually only use single precision.

askee 10y ago

In general there are no shortcuts, and when the matrix A is not small (e.g. m x n with m,n << 100), you don't want to invert A, especially if you are only interested in x (from A x = b). Instead, use numerical minimization schemes like conjugated gradients and variants thereof or Quasi-Newton methods (BFGS). Combined with preconditioning as well as regularization or denoising this usually yields good results. Compressive sampling methods (total variation regularization) have received lots of attention in the last ten years.

mturmon 10y ago
This comment seems to be a diversion from the question asked. The main point of OP is that solving A x = b is commonly done with factorizations of A, not by explicit computation of inv(A). Resorting to a numerical minimization (like MINRES) would be unusual unless the dimension is much bigger than hundreds. Certainly it's not relevant in a graphics computation with dimension of 3, 4, or 6. My laptop inverts a 4Kx4K general matrix in 1.5s. It solves a 4K linear system in 0.5s.

neutronicus 10y ago

In games you're probably applying many small inverse matrices to many small vectors. In partial differential equations, you solve a single large linear system where the unknown vector represents a field defined at every point on a spatial mesh. In my research, specifically, that spatial mesh can have as many as 10^7 grid points. For linear systems of this size, any exact solution at all is impractical - we exclusively employ iterative approximations built from terms of the form (A^n) b since matrix-vector products are about the only things we can compute in a reasonable amount of time.

x0x0 10y ago
And not only are the matrices small, they're probably known (or assumed) to be well-conditioned. Inverting even a small hilbert matrix will probably go boom.
- GFK_of_xmaspast 10y ago
  Not just well conditioned, but special orthogonal.