Questions tagged [matrix]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
15 views

Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
1
vote
1answer
41 views

Min-plus matrix multiplication implementation

I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication: One method for doing this is to ...
2
votes
1answer
33 views

Numerical issues in solving linear systems

There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows: Consider the linear system $$ \begin{bmatrix} a & b \\ ...
-1
votes
2answers
41 views

Time complexity of matrix subtraction

If I have (I-Z) where I is a 3x3 identity matrix while Z is a 3x3 lower triangular matrix, how many subtractions that I should count from this process? Is it costs K subtractions or (K^2+K)/2 ...
1
vote
1answer
27 views

Coloring book. Finding region by point

Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D ...
0
votes
0answers
12 views

Complexity of Inserting an element in a sorted matrix [duplicate]

If in a matrix (m*n) having sorted rows and sorted columns then time complexity to insert new element?
1
vote
1answer
75 views

Select K columns from matrix and one element from each row that has maximum sum

Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each ...
1
vote
3answers
50 views

In O(1) get the coordinate i,j of a diagonally ordered matrix

Say you have a matrix like this: [][]int{ {0, 2, 5, 9, 14}, {1, 4, 8, 13, 18}, {3, 7, 12, 17, 21}, {6, 11, 16, 20, 23}, {10, 15, 19, 22, 24}, } ...
4
votes
0answers
75 views

Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
0
votes
0answers
32 views

How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
0
votes
0answers
37 views

Computational Complexity of a Matrix Multiplication

I am computing a matrix multiplication with inverse operation $AB^{-1}C$ $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times o}$. So the inverse operation takes $...
2
votes
1answer
27 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
1
vote
0answers
29 views

Finding the linear mapping between homogeneous coordinates of affine camera

If I have an affine camera with a projection relationship governed by: \begin{equation} \begin{bmatrix} x & y \end{bmatrix}^T = A \begin{bmatrix} X & Y & Z \end{bmatrix}^T + b \end{...
2
votes
1answer
249 views

Lexicographically smallest down-right path in matrix

Here is the problem which I thought was simple dynamic programming, which is however not the case. Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
1
vote
1answer
70 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
0
votes
0answers
25 views

Computing $A^{-2}BA^{-3}b$

Let $A,B$ be matrices of $\mathbb{R}^n$ space and $b \in \mathbb{R}^n$. Describe a fast algorithm to compute $A^{-2}BA^{-3}b$. How many computations will the algorithm make? This is an exam question ...
1
vote
1answer
30 views

Expectation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $. I need to ...
1
vote
0answers
26 views

Partitioning the columns of a matrix

I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here: Suppose you have a matrix $A\in\...
1
vote
1answer
56 views

Replace 1's with -1's and vice versa in a matix

Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an ...
8
votes
3answers
1k views

Strassen algorithm for matrix multiplication complexity analysis

I see everywhere that the recursive equation for the complexity of Strassen alg is: $$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me. The parameter $n$ is supposed to be the size of the ...
0
votes
1answer
24 views

How to count stores in cache analysis of matrix multiplication

I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out. For ijk iteration, my slides say that there are 2 loads and 0 stores. ...
0
votes
0answers
355 views

Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times

A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s. for eg, n=3, m=3, ...
2
votes
1answer
28 views

What's the connection between the two “Fast Walsh Transform”?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
0
votes
1answer
70 views

Verify Matrix multiplication

Let s say we have an algorithm that takes as input 3 matrix A,B and C $$ Input :A,B,C \in Mat(n\times n)$$ $$Question :\text{is } A*B=C$$ the algorith works as follow ; $$ \text{if }(A*B)_{ij}=C_{...
0
votes
0answers
46 views

Count submatrices with only zeros for each element of the matrix

Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...
2
votes
1answer
1k views

Strassen's matrix multiplication algorithm when $n$ is not a power of 2

The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The algorithm multiplies two square ...