Questions tagged [matrix-multiplication]
The matrix-multiplication tag has no usage guidance.
12
questions
1
vote
1answer
70 views
Iterated multiplication of permutation matrices
Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where
$m=\mathit{poly}(n)$
$m=\...
0
votes
1answer
40 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 ...
1
vote
1answer
97 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 ...
5
votes
1answer
55 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 ...
0
votes
0answers
17 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 ...
20
votes
2answers
877 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
0answers
7 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 ...
0
votes
1answer
64 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
1answer
27 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 ...
0
votes
1answer
53 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
1answer
43 views
Is matrix multiplication cheaper than inverse?
In wiki, it is shown that the time complexity of matrix multiplication and matrix inverse is similar. But people always to argue it is easier to do matrix multiplication rather than inverse. Is this ...
2
votes
1answer
166 views
Calculate boolean matrix multiplication (BMM) using transitive closure
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 ...
