# Tag Info

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 ...
• 278k

### 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 ...
• 30.7k
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}$...
• 278k
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 ...
• 562

### 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 ...
• 162k
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 ...
• 30.7k
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.
• 15.8k

### 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 ...
• 162k

### 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.

### 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$...
• 278k
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 ...
• 213
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 ...
• 15.8k

### 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 ...
• 278k

### 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 ...
• 1,455
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$. ...
• 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 ...
• 30.7k
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 ...
• 4,257
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 ...
• 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$...
• 278k
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 ...
• 30.7k
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 ...
• 30.7k
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: ...
• 4,474

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