CODEWITHSUNDEEP
c++cmatrixssesimd
user1095108
user1095108

Reputation: 14603

vector * matrix product efficiency issue

Just as Z boson recommended, I am using a column-major matrix format in order to avoid having to use the dot product. I don't see a feasible way to avoid it when multiplying a vector with a matrix, though. The matrix multiplication trick requires efficient extraction of rows (or columns, if we transpose the product). To multiply a vector by a matrix, we therefore transpose:

(b * A)^T = A^T * b^T

A is a matrix, b a row vector, which, after being transposed, becomes a column vector. Its rows are just single scalars and the vector * matrix product implementation becomes an inefficient implementation of dot products of columns of (non-transposed) matrix A with b. Is there a way to avoid performing these dot products? The only way I see that could do it, would involve row extraction, which is inefficient with the column-major matrix format.

Upvotes: 1

Views: 753

Answers (1)

Z boson
Z boson

Reputation: 33679

This can be understood from original post on this (my first on SO) efficient-4x4-matrix-vector-multiplication-with-sse-horizontal-add-and-dot-prod . The rest of the discussion applies to 4x4 matrices.

Here are two methods to do do matrix times vector (v = Mu where v and u are column vectors)

method 1) v1 = dot(row1, u), v2 = dot(row2, u), v3 = dot(row3, u), v4 = dot(row4, u)
method 2) v = u1*col1 + u2*col2 + u3*col3 + u4*col4.

The first method is more familiar from math class while the second is more efficient for a SIMD computer. The second method uses vectorized math (like numpy) e.g. 

u1*col1 = (u1x*col1x, u1y*col1y, u1z*col1z, u1w*col1w).

Now let's look at vector times matrix (v = uM where v and u are row vectors)

method 1) v1 = dot(col1, u), v2 = dot(col2, u), v3 = dot(col3, u), v4 = dot(col4, u)
method 2) v = u1*row1 + u2*row2 + u3*row3 + u4*row4.

Now the roles of columns and rows have swapped but method 2 is still the efficient method to use on a SIMD computer.

To do matrix times vector efficiently on a SIMD computer the matrix should be stored in column-major order. To do vector times matrix efficient on a SIMD computer the matrix should be stored in row-major order.

As far as I understand OpenGL uses column major ordering and does matrix times vector and DirectX uses row-major ordering and does vector times matrix. If you have three matrix transformations that you do in order M1 first then M2 then M3 with matrix times vector you write it as 

v = M3*M2*M1*u //u and v are column vectors - OpenGL form

With vector times matrix you write

v = u*M1*M2*M3 //u and v are row vectors - DirectX form

Neither form is better than the other in terms of efficiency. It's just a question of notation (and causing confusion which is useful when you have competition).

It's important to note that for matrix*matrix row-major versus column-major storage is irrelevant.

If you want to know why the vertical SIMD instructions are faster than the horizontal ones that's a separate question which should be asked but in short the horizontal ones really act in serial rather than parallel and are broken up into several micro-ops (which is why ironically dppd is faster than dpps).

Upvotes: 1

Related Questions