# Questions tagged [matrix-multiplication]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
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 ...
17 views

• 187
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 ...
1k 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 ...
• 173
204 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
19 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
71 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 ...
123 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 ...
• 7,088
49 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
135 views

• 411
828 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
256 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 ...
• 652
1 vote