Questions tagged [matrix]

The tag has no usage guidance.

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

Are My Answers to This Hamming Code Example Correct?

I have attempted to answer this question on Hamming code but i am very new to it and would appreciate feedback on my answers, Thank you! Question My Answers
1
vote
1answer
36 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 ...
1
vote
0answers
17 views

How to predict the time complexity of matrix multiplication and inverse on a GPU?

Nvidia GPU can speed up the matrix manipulation greatly. I want to have a basic idea to predict the consumed time for matrix manipulation. How can I analyze the time complexity of matrix ...
1
vote
1answer
49 views

How to shift a matrix by x rows and y columns in the most efficient way?

My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ...
-1
votes
1answer
17 views

Find specific position in matrix

Consider a binary (i.e. over $\{0, 1\}$) matrix $A = (a_{ij})$ of size $n \times n$. It is known that there is exactly one $r \in [1; n]$ such that $a_{rj} = 0$ for all $j \in [1; n]$ and $a_{ir} = 1$ ...
3
votes
1answer
84 views

Applying SVD compression to integral point images

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular ...
2
votes
1answer
65 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 ...
-1
votes
1answer
34 views

Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview). Sub-matrix ...
4
votes
1answer
127 views

Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after ...
2
votes
0answers
32 views

Find sub-matrix containing the maximum number of elements consisting only of 1's [closed]

I am trying to get help on it here, originally posted first at: https://stackoverflow.com/questions/59446920/find-sub-matrix-containing-the-maximum-number-of-elements-consisting-only-of-1s Basically ...
1
vote
0answers
42 views

Algorithm to find a all valid matrix permutations [closed]

I have an array of $N^2$ numbers like $ a = \{ a_1,a_2, ..., a_{N^2} \}$ where all $a_i < F$ where $F$ is a fixed number. I am looking for all permutations where if I put values in $A$ in order (...
3
votes
1answer
133 views

Matrix chain multiplication: Greedy approach

some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section. The ...
1
vote
0answers
18 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
122 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
74 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
66 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
32 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
23 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
185 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
67 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
78 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
33 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
42 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
32 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
32 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
372 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
91 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
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
36 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
57 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
2k 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
32 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
406 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
32 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$...
1
vote
2answers
91 views

Matrix multiplication randomised verification - error probability

Let s say we have an algorithm that takes as input 3 matrix A,B and C $$ \text{Input} :A,B,C \in Mat(n\times n)$$ $$\text{Question} :\text{is } A\cdot B=C$$ the algorith works as follow ; $$ \...
0
votes
0answers
120 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. ...
3
votes
1answer
2k 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 ...