Most efficient matrix multiplication algorithm

I think this is the sort of question which reveals more about the interviewer than the candidate. Any company that expects you to write your own matrix multiplication software, or to study matrix methods, likes wasting time.

Personally, I'd use a library, having checked the problem domain to see if we are dealing with any special cases (sparse, does not fit in main memory - yep, I've inverted huge matrices using Choleski elimination on DecTapes).

But what would I know :-)

Bill

Agree.

Agree on the "write your own" part only. To study, or at least, to be aware of the existence of alternative methods is always a good thing.

I see this type of questions as probing the candidate's knowledge for approaches other than the obvious one, not as testing his ability to implement or develop other methods.

For the particular case of matrix multiplication, Strassen's algorithm come to mind. (

Try searching for "fast matrix multiplication".

Roberto Waltman

It also review the candidate's educational background. Modern educations don't go into the basic theories.

Writing the code during the interview is riduclous, but talking about it is fine.

I would not want to re-implement it without reason. The theory is that the matrices can be reduced to blocks of submatrices, with identity and zero matrices everywhere else. A good interviewing test is to take a sample matrix and guess how small can it be reduced.

Depending on the job interviewed for, it may have been something as simple as fishing for a question -- "how big are the matrices?" or "do you mean optimize the algorithm or do peephole optimization?"

Or, as several others have mentioned, the interviewer may have just been looking for broad exposure to algorithms and such.

--Charles

You can calculate the address of an array element using index to an array or using pointers. If the CPU has many registers, then you could load multiple row values

A simple example:

X11 X12 Y11 Y12 * = X21 X22 Y21 Y22

---------------------------------------------------------- (X11*Y11)+(X12*Y21) (X11*Y12)+(X12*Y22)

(X21*Y11)+(X22*Y21) (X21*Y12)+(X22*Y22)

One sees that each value has to be used twice. In a 3 x 3 matrix, each value has to be used 3 times.

An algorithm which loads each X value only once will be more efficient than the "obvious" algorithm.

You may also want to know about the memory structure of the CPU. If there are different memories with widely different access times, you may want to optimize for that. Locking caches, copying from external slow memories to internal fast memories etc.

You also want to know the goal of the company. Is maintainable/portable code more important than wringing out the last bit of performance.