Questions tagged [matrix-multiplication]
The matrix-multiplication tag has no usage guidance.
25
questions
0
votes
0
answers
27
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
2
answers
227
views
Can dot producting the result of vector-matrix multiplication speed up the runtime
Suppose we have a matrix $A$ of dimension $n \times n$ and 2 vectors $\vec{u}$ and $\vec{v}$ of dimension $n$.
Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(n)...
- 177
0
votes
0
answers
27
views
What will be the Computational Complexity in terms of order O of the operations shown in the following figure
Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors.
So, first, I have to do a scalar multiplication with a vector ...
3
votes
3
answers
180
views
Are there absolute reasons to prefer row/column-major memory ordering?
I've heard it said that "fortran uses column-major ordering because it's faster" but I'm not sure that's true. Certainly, matching column-major data to a column-major implementation will ...
- 143
0
votes
3
answers
100
views
Super-linear parallelism or speedup in parallel matrix multiplication algorithms
I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T_1$, Span $T_\infty$ and Parallelism (ratio $T_1/T_\infty$). What is called ''...
- 23
0
votes
0
answers
12
views
runtime of solving matrix differential equation wrt dimensions of matrix
Suppose a computer solves a coupled differential equations (with given boundary conditions) of which each equation deals with $2^n \times 2^n$ size of matrices as solutions. My question is
Does time-...
- 101
3
votes
0
answers
54
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 ...
- 141
4
votes
2
answers
85
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 ...
- 5,254
3
votes
0
answers
48
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 ...
- 71
1
vote
1
answer
80
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 $\...
0
votes
0
answers
58
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
$...
- 389
0
votes
1
answer
183
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$ ...
- 9
0
votes
1
answer
98
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 ...
- 612
1
vote
1
answer
123
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=\...
- 17
0
votes
1
answer
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 ...
- 103
2
votes
1
answer
514
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 ...
- 23
5
votes
1
answer
90
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
1
answer
223
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
22
votes
2
answers
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
0
answers
32
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
0
votes
1
answer
135
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
1
answer
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 ...
- 115
0
votes
1
answer
91
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
1
answer
63
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 ...
- 121
3
votes
1
answer
305
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 ...
- 31