Hi,
What would be the fastest algorithm to solve a 4 variables - 4 unknowns linear system ?
I have the feeling that it must be somewhere between brutal force methods (substitution) and more sophisticated iterative methods.
linear system 4*4
Linear systems with 4 variables and 4 unknowns are quite small and they can be solved in a very short time. For such a small systems I wouldn't use an iterative method. In fact, the other methods are a lot more accurate and you don't have to choose how much iterations are enough. I don't know what's the fastest general method, you can always implement several methods and then use a profiler to discover it yourself.
Anyway, the best performances can be obtained when the system has a particular form. For example, if you know your matrix represent an affine transformation. So, what are you doing? Why do you need a very fast 4x4 linear solver?
EDIT: Most methods requires several ifs, which can be a lot slower than a division or multiplication on modern architecture.
Anyway, the best performances can be obtained when the system has a particular form. For example, if you know your matrix represent an affine transformation. So, what are you doing? Why do you need a very fast 4x4 linear solver?
EDIT: Most methods requires several ifs, which can be a lot slower than a division or multiplication on modern architecture.
For something that small, and if your system has no special form, it might not be unreasonable to just hard-code Kramer's Rule. It has bad asymptotic complexity, but that's not an indicator of speed for small problems, and it has the advantage of requiring no branches (except perhaps to throw an error when the determinant is zero).
refering to another post :
http://www.gamedev.net/community/forums/post.asp?method=reply&topic_id=573015
I'm trying to find an efficient way to interpolate a function whose value is known at the 4 vertices of a quadrilateral ; in other words : the same as barycentric interpolation, but for a quad. I found another way than those discussed in the post : I take the non-linear function f(x,y) = a.x.y + b.x + c.y + d. I know the function's value at 4 points (x1,y1), (x2,y2), (x3,y3), (x4,y4), this gives 4 equations with 4 variables (a,b,c,d). I need to do this for quite a few polygons, preferably real-time, and twice for each polygon (I map 2D quads on 2D quads), so speed matters. I assume the matrix has, in a general case, no particular form.
http://www.gamedev.net/community/forums/post.asp?method=reply&topic_id=573015
I'm trying to find an efficient way to interpolate a function whose value is known at the 4 vertices of a quadrilateral ; in other words : the same as barycentric interpolation, but for a quad. I found another way than those discussed in the post : I take the non-linear function f(x,y) = a.x.y + b.x + c.y + d. I know the function's value at 4 points (x1,y1), (x2,y2), (x3,y3), (x4,y4), this gives 4 equations with 4 variables (a,b,c,d). I need to do this for quite a few polygons, preferably real-time, and twice for each polygon (I map 2D quads on 2D quads), so speed matters. I assume the matrix has, in a general case, no particular form.
Gaussian elimination takes 10 divisions and 26 multiplications. I don't know if you can do better, but it's probably hard.
If this is a practical question, the number of multiplications and divisions is an irrelevant metric.
This is probably a good way to go.
This is probably a good way to go.
LU factorization usually performs less FLOPS that other elimination techniques.
FLOPS refer arithmetics( add,subtract,mult,div).
FLOPS refer arithmetics( add,subtract,mult,div).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement