Skip to main content
18 votes
Accepted

What is the intuition behind Strassen's Algorithm?

The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a ...
Yuval Filmus's user avatar
5 votes
Accepted

Usage of matrix multiplication for distance products

Nice idea! But no, that doesn't work, alas. The problem with your approach is that the numbers become enormous, which makes matrix multiplication slow. It is tempting to say that the running time of ...
D.W.'s user avatar
  • 162k
5 votes

What is the intuition behind Strassen's Algorithm?

It’s reasonably obvious that if you can calculate a 2x2 matrix product with 7 multiplications and quite a few additions, you get an asymptotically faster algorithm. You need 8 products. But for ...
gnasher729's user avatar
  • 31.1k
4 votes
Accepted

In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$...
Yuval Filmus's user avatar
4 votes
Accepted

Are there absolute reasons to prefer row/column-major memory ordering?

Whether row-major or column-major order is more efficient, depends on the storage access patterns of a specific application. The underlying principle of computing is that accessing storage in ...
Steve's user avatar
  • 562
3 votes
Accepted

Floating point operations in a zero padded Strassen multiplication

You wouldn’t pad to a power of two. First, for small matrix sizes you would just produce the fastest code you can, without using Strassen at all. Then you figure out for which n a 2n x 2n matrix is ...
gnasher729's user avatar
  • 31.1k
3 votes
Accepted

Compute matrix inversion / multiplication using a black box

It was shown in 1969, by Strassen, that matrix multiplication and matrix inversion have the same computational complexity. Details can be found on Wikipedia.
Nathaniel's user avatar
  • 15.9k
3 votes

Can dot producting the result of vector-matrix multiplication speed up the runtime?

No. It is not possible to reduce the time complexity below $O(n^2)$ time. It takes $\Theta(n^2)$ time just to read every entry in $A$. Moreover, the result depends on every entry of $A$ (if there ...
D.W.'s user avatar
  • 162k
3 votes

Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?

More "down to earth" fast matrix multiplication algorithms are described at this url. If you know better ones for these matrix sizes (all up to 32x23), their definitions is welcome.
sedoglavic's user avatar
3 votes

Is matrix multiplication cheaper than inverse?

Matrix multiplication and matrix inverse have the same asymptotic running time. If we denote the running time of multiplying two $n \times n$ matrices by $T_1(n)$, and that of inverting an $n \times n$...
Yuval Filmus's user avatar
2 votes
Accepted

Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size ...
shimao's user avatar
  • 213
2 votes
Accepted

Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

It looks like the article was written by someone who does not understand matrix multiplication. the number of additions is equal to the number of entries in the matrix, so four for the two-by-two ...
Nathaniel's user avatar
  • 15.9k
2 votes

Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?

Le Gall improved over Williams' result, and Alman and Williams improved over his result. The latter is currently the state of the art for multiplying two square matrices. The best known algorithms for ...
Yuval Filmus's user avatar
2 votes

Floating point operations in a zero padded Strassen multiplication

See, the idea is to choose the next power of $2$ for $n$ so that we have $\frac{N}{2} < n \le N$. Then, in an asymptotic sense, it does not matter whether you use $n$ or $N$. Here's why: The actual ...
codeR's user avatar
  • 1,807
1 vote

Complexity of multiplying 3 matrices

No. If you can multiply two $n \times n$ matrices in time $O(f(n))$ then you can also multiply three matrices $A,B,C$ in the same asymptotic running time by first computing $M=AB$ and then $MC$. ...
Steven's user avatar
  • 29.5k
1 vote

Super-linear parallelism or speedup in parallel matrix multiplication algorithms

When you multiply two n x n matrices using the naive algorithm, your problem size is not n, but n^2. The number of operations is not n, but n^3. Unless someone is more clever than I am, an infinite ...
gnasher729's user avatar
  • 31.1k
1 vote
Accepted

Super-linear parallelism or speedup in parallel matrix multiplication algorithms

Let's start from the definitions, in order to clarify things. The work of a computation executed by $p$ processors is the total number of operations performed. Ignoring the parallel overhead, the work ...
Massimo Cafaro's user avatar
1 vote

Matrix-vector multiplication using only lower triangular of matrix

Answer by Clayton Gotberg [1], modified: If $\textbf{A}$ is a symmetric matrix and $\textbf{A}_{LT}$ is the lower triangular part of the matrix and $\textbf{A}_{UT}$ is the upper triangular part of ...
Justin Shenk's user avatar
  • 1,035
1 vote
Accepted

Iterated multiplication of permutation matrices

Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$...
Yuval Filmus's user avatar
1 vote
Accepted

matrix multiplication speedup when the matrix elements are 0, 1 and -1

Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like ...
gnasher729's user avatar
  • 31.1k
1 vote

In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

You can take any matrix with N/2 < n < N rows and columns, pad it, and multiply it with Strassen's algorithm (or the naive algorithm for example), and then drop lots of zeroes that were created ...
gnasher729's user avatar
  • 31.1k
1 vote

Calculate boolean matrix multiplication (BMM) using transitive closure

Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows: ...
Narek Bojikian's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible