3
$\begingroup$

The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, let's say we use floating-point numbers. Ideally, the approach would be fast enough for small $n$ and, of course, should not require size ($n$ value) of ~$10 ^ 6$ to break even relative to brute-force cubic time approach. The lower the running time, the better. Given ties, the lower the coefficient for running time, the better. Given ties again, lower space requirement is desired. Algebraic or combinatorial approaches are acceptable.

Then, what is a suitable algorithm choice for this moderate-size-input square matrix product problem?

$\endgroup$
  • 4
    $\begingroup$ There are literally dozens of different "fastest" algorithms, depending on the particular structure of the matrices and the structure of the computer operating on them. Which cases are you looking for? (Or is this just a self-answered question to publish our own work on stack exchange?) $\endgroup$ – Cort Ammon Dec 15 '16 at 23:40
  • 2
    $\begingroup$ Please edit your question to make it more focused and define the requirements or criteria for evaluation. While answering your own question is fine, you still need to make sure your question meets our quality standards and is not too broad. It's great to answer your own question, but the question should be of reasonable quality too. See also blog.stackoverflow.com/2011/07/…, meta.stackexchange.com/q/183847/160917, meta.stackexchange.com/a/256654/160917, meta.stackexchange.com/a/137369/160917. $\endgroup$ – D.W. Dec 16 '16 at 0:03
  • 2
    $\begingroup$ Likely a good choice is to use some well-known package or library for linear algebra. $\endgroup$ – Juho Dec 28 '16 at 13:42
7
$\begingroup$

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.