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?

Improve this question
$\endgroup$
3
  • 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, 2016 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, 2016 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, 2016 at 13:42

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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