# Questions tagged [matrix]

The tag has no usage guidance.

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

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 \\ ... 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 ... 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 ... 1answer 30 views ### How can i solve this problem using recursion? [closed] ... 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? 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 ... 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}, } ... 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 ... 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 ... 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 ... 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 ... 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{... 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 ... 1answer 70 views ### Looking for algorithm to iterate over matrix I have such a product example: ... 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 ... 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 ... 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\... 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 ... 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 ... 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. ... 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, ... 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 \oplusrepresents any boolean operation. And we are able to evaluate C... 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_{...
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. ...