Questions tagged [matrix-multiplication]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
0answers
31 views

fast multiplication of power of a matrix by a vector

I'm interested in computing of the product $M^n v$, where $M$ is an $m\times m$ matrix (over a semiring) and $v$ is column-vector, with the smallest number of multiplications in the underlying ...
4
votes
2answers
77 views

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

I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result (see ...
3
votes
0answers
45 views

Computing a series of matrix power - matrix products

Assuming we have two dense matrices $A \in \mathbb{R}^{m\times m}, B \in \mathbb{R}^{m\times n}$, is there a smart way to compute all entries of the series $A^1 B, A^2 B, A^3 B, \dots, A^k B$ up to ...
1
vote
1answer
33 views

Matrix Multiplication Verification

This question relates to the 2nd edition of Probability and Computation by Mitzenmacher and Upfal. The authors then use the Law of Total Probability My question concerns the line that begins with $\...
1
vote
1answer
76 views

Matrix-vector multiplication using only lower triangular of matrix

Suppose one has a large sparse symmetric positive definite matrix $A$ and wants to multiply it by a vector $x$. Only the lower triangular part of matrix A is stored/known. The multiplication $Ax$ ...
2
votes
1answer
237 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 ...
0
votes
0answers
52 views

Merging the submatrices' time complexity in matrix multiplication

This is a problem of CLRS: What is the largest $k$ such that if you can multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $...
0
votes
0answers
12 views

Best sparse matrix structure for Lanczos algorithm and/or matrix-vector multiplication

I have written a Lanczos routine which I am using for some problems in physics. Now, I would like to feed it some sparse matrices with very low densities (hamiltonians of large systems), and for that ...
0
votes
1answer
48 views

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

In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words: Multiplications are everything. The exponent on the eventual running time is fully dependent only ...
1
vote
1answer
104 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
43 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 ...
2
votes
1answer
246 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
75 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
63 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
1k 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
10 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 ...
1
vote
1answer
29 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
89 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) ...
0
votes
1answer
71 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
52 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 ...