# Questions tagged [matrix-multiplication]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
37 views

### Complexity of multiplying 3 matrices

There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically ...
1 vote
32 views

### Matrix multiplication of natural numbers

I know matrix multiplication of matrices with real numbers is bounded by $\Omega (n^2 log(n))$, but what about if all numbers are natural? Can we use the same methods to get a lower bound for this ...
43 views

### Has Triangle Finding ever been faster than Matrix Multiplication?

The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977  to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
67 views

### What's the fastest known non-galactic algorithm for matrix multiplication of large matrices

"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
28 views

### Fast compute of F*P*FT matrix product

Let $P$ be a symmetric (positive definite, if that helps...) matrix of size $n$. Let $F$ be a matrix of size $n$. Is there an existing efficient algorithm implementation to calculate $FPF^T$ ? Is ...
1 vote
414 views

74 views

45 views

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

I would like to compute matrix multiplication A * B where A is Nx3 and B is 3x3. We also ...
953 views

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

In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity? Hi, I was reading this question but I ...
117 views

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

I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow ...
1 vote
602 views

### Why is the weight matrix diagonal in weighted least squares regression?

I was going through the theory for weighted least-squares fitting and I understood its basic underlying concepts, but I couldn't understand why exactly do we keep the weights as a diagonal matrix ...
2k views

### What is the intuition behind Strassen's Algorithm?

I came across Strassen's algorithm for matrix multiplication, which has time complexity $O(n^{2.81})$, significantly better than the naive $O(n^3)$. Of course, there have been several other ...
1 vote
69 views

### Lower bounds for orthogonal matrix multiplication

Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices? More precisely, let $T(N)$ denote the worst-case time of the ...
184 views

### Is this benchmark sufficient to consider my algorithm as an efficient matrix multiplication algorithm?

I built a matrix multiplication algorithm and now I need some thoughts about following benchmark. C++ chrono:: high resolution clock Time(micro second) (Dim)256--> (Naive algo ) 296807, (My algo) ...
1 vote
31 views

### How can follow this this guide to construct a graph with matrix/reachability

Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
133 views

### In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
1 vote
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$. How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...