# Questions tagged [matrices]

For questions about construction and modification of matrices, objects represented by 2-dimensional arrays that are used to define linear operators within linear algebra.

192 questions
Filter by
Sorted by
Tagged with
638 views

### Proof: Sum of weights of paths in a network

I was given problem 6.7 out of the book "Networks: An Introduction" as a question. The problem is defined as follows: Consider the set of all paths from node $s$ to node $t$ on an undirected ...
329 views

Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example, person 1 has item A, C, D, and wants item F person 2 has item B, C, and wants E ...
389 views

### Quadratic algorithm for Matrix Chain Multiplication [closed]

I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct. By no means, am I a ...
53 views

### Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
550 views

### Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...
29 views

143 views

### Find all sets of n unique rows in matrix

I am looking for an efficient method to find all unique combinations of $n$ rows in a matrix. For example, if $n=6$, then I want to find all sets of 6 rows from the input set C in which the columns ...
228 views

### Are there any non-naive parallel sparse matrix multiplication algorithms?

I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
388 views

### Calculate the computational complexity of multiplication AxAT

I need to implement an algorithm that calculates the symmetric matrix obtained by performing $A A^t$ being $A^t$ the transpose of $A$. I did my analysis from two perspectives: The first thing I ...
1k views

### Number of submatrices with a particular sum- Answer Explantion

I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix. ...
2k views

### What is the complexity of multiplying a matrix by a scalar?

I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$? In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like ...
69 views

### Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
867 views

### Shortest path in a matrix

I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each ...
255 views

### Efficient (sublinear) approximation algorithms for matrix-vector multiplication?

Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the mean matrix-vector product: $$v = \frac{1}{n} Ax$$ If I did this using ...
460 views

### Implementing the Schur decomposition of a matrix

I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?
453 views

### Fine-Grain parallel algorithm for LU-decomposition

How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the min(i; j) - 1, because I have no idea, what ...
52 views

### How to find (real-valued) roots of matrix polynomial

Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial $$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$ Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
137 views

### How does “do in parallel” work

currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense ...
Consider the low-rank matrix completion problem: Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at ...