The tag has no usage guidance.

learn more… | top users | synonyms

-1
votes
0answers
36 views

SVD of a sum of two matrices when one is diagonal

I have an $n\times n$ rank-$k$ matrix $A$, and a diagonal $n\times n$ matrix $D$, and I have the svd of A, $$[U, S, V] = \mathrm{svd}(A)\,.$$ I want to compute the singular value decomposition (SVD) ...
2
votes
1answer
37 views

Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
3
votes
1answer
113 views

is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance! Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( ...
0
votes
0answers
19 views

How do Perwitt and Sobel detect edges?

I read up on the Perwitt operator and it detects two types of edges (vertical and horizontal). The Sobel operator on the other hand does the same as the Perwitt except that the masks are not constant ...
3
votes
0answers
32 views

Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m << D $ dimensional columns ...
0
votes
0answers
24 views

Where is pivoting done in the Crout decomposition algorithm?

Consider the following code, found on wikipedia, that implements the Crout decomposition algorithm: ...
3
votes
0answers
64 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. Since,...
2
votes
0answers
23 views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called ...
1
vote
0answers
27 views

Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...
0
votes
1answer
57 views

Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix? Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?
2
votes
1answer
42 views

How does RAID-5 algorithm locate the right device?

Please consider the following diagram of a RAID-5 array (Ignore the gray background): Now, given a logical address, how can one return the device number (0-3)? For example, DeviceByLogicalSector(50)...
2
votes
0answers
50 views

Computational complexity of Doolittle's algorithm

I could not find a big-oh cost for Doolittle's algorithm for LU decomposition of a matrix online, so I took a pseudocode implementation from here and analyzed it to get $$\frac13n^3+\frac32n^2+\...
1
vote
0answers
31 views

Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
0
votes
1answer
72 views

NP-completeness proof via reduction

I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x ...
1
vote
1answer
33 views

Matrix of Matrices in Python [closed]

I want to create a matrix where each entry itself is a random matrix. What would be a good way to represent this? It is not necessary but some hints on how to implement your proposed solution in ...
1
vote
2answers
72 views

Time complexity of comparing two $N \times N$ Matrices?

So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of ...
8
votes
1answer
307 views

Minimal basis for set of binary vectors using XOR

I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to ...
-1
votes
1answer
70 views

Maximum frequency in any row and column

I have been given 2D matrix with some elements. I want to find out what is maximum frequency in any row and column. Example: 1 2 1 2 3 4 1 2 1 1 1 1 2 2 2 2 Maximum frequency is 6 which occurs in last ...
1
vote
1answer
81 views

Number of submatrices, of a base matrix derived from an array, with a particular sum

Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its ...
3
votes
1answer
69 views

Is matrix “adjoint-squaring” faster than general matrix multiplication?

The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are ...
3
votes
0answers
320 views

What can I do with this algorithm?

Problem Statement The problem is to calculate the coefficients $A_{j_1\cdots j_n}$, of a square matrix A with size $N$ by $N$ of complex double elements, whose weighted sum with $N^2$ irreducible ...
3
votes
2answers
70 views

Choosing nonzero entries from an array so no pair in same row or column

Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$. We want to find $n$ entries of the array $(x_1,y_1), \dots, (...
6
votes
1answer
142 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
0
votes
0answers
35 views

3D Column Sort (Leighton) Algorithm

Suppose you have a matrix A (9x3) of Real numbers and want to sort in columnwise. In this case we can use Leighton ColumnSort algorithms to achieve this. But question is, how can I sort 3 dimensional ...
6
votes
2answers
91 views

Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability. The algorithm choose a random $r$ n-...
2
votes
2answers
40 views

Arden's rule expressed as matrix algebra

The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and which ...
1
vote
1answer
101 views

Looking for an algorithm to iterate over essentially different solutions

I'll explain my problem with an analogy to Sudoku-grids. Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However ...
1
vote
0answers
28 views

Find all paths of length k [duplicate]

I have an adjacency matrix, call it A, representing a directed graph. I want to find all paths of length k. I know that A^k ...
0
votes
0answers
25 views

How to calculate a specific time complexity of inverse calculation of matrix? [duplicate]

I am a green-hand in calculating the time complexity. Given a calculation as follows: \begin{equation} \mathbf{x}=\mathbf{A^T}(\mathbf{AA^T}+\lambda\mathbf{I}_n)^{-1}\mathbf{b} \end{equation} where $\...
0
votes
0answers
59 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 ...
6
votes
1answer
104 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 ...
0
votes
0answers
72 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 ...
0
votes
1answer
200 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. ...
0
votes
2answers
197 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 ...
0
votes
0answers
37 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. ...
0
votes
1answer
304 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 ...
1
vote
2answers
73 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 ...
0
votes
1answer
137 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?
0
votes
1answer
66 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 ...
1
vote
0answers
26 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. ...
1
vote
1answer
72 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 ...
1
vote
1answer
282 views

Parallel algorithm for LU-decomposition

I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets. So, could you, please, recommend me some parallel algorithms ...
2
votes
0answers
50 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
0
votes
0answers
104 views

Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
2
votes
1answer
791 views

Relations and Zero One Matrices

I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices. For example if I have a set A = {1,2,3} and a relation R = {(1,1), (1,2), (2,3)...
0
votes
1answer
4k views

Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times r$)?...
4
votes
3answers
362 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
1
vote
1answer
95 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
3
votes
0answers
164 views

computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
-1
votes
1answer
93 views

Matrix usage in CS [closed]

I'm studying a major in CS. I'm interested in taking a few extra courses, specifically math to improve my knowledge as future computer scientist. Right now I'm thinking to take Matrix Fundamentals ...