# Questions tagged [matrix-multiplication]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
48 views

### Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
1 vote
23 views

### Algorithm for solving linear equations if interested only in the first component

If I want to solve $\mathbf A \mathbf x = \mathbf b$, but I am only interested in the value of $x_1$, what algorithm should I use, and will it always be strictly more efficient than solving for all of ...
41 views

### Floating point operations in a zero padded Strassen multiplication

So I've seen other posts here that do discuss this, but I'm not quite sure how the time complexity (I think?) relates to the actual number of floating point operations done per second when you're ...
• 103
1 vote
44 views

### Compute matrix inversion / multiplication using a black box

Suppose you're given a black box $A$, and you're told $A$ can invert a matrix (assuming the matrix is invertible) $M$ in $O(T_A)$. You're also given a black box $B$, and you're told $B$ can multiply ...
• 1,942
58 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 ...
• 101
1 vote
34 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 ...
• 31
44 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 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
79 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 ...
• 356
32 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 ...
• 101
1 vote
559 views

90 views

• 17
48 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 ...
• 103
1k 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 ...
135 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 ...
• 213
1 vote
839 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 ...
• 113
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
78 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 ...
• 215
211 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) ...
• 3
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 ...
• 227
151 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 ...
• 103
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 ...