The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
22 views

Solving a modulo 3 matrix system, with a constraint on the domain of the solution

All calculations below are integer calculations under modulo 3. I am trying to solve an integer linear system of equations: $$\begin{align*} a_{0,0} x_0 + a_{1,0} x_1 + a_{2,0} x_2 + .. + a_{n,0} x_n ...
-1
votes
2answers
35 views

Parallel Algorithms for matrix multiplication

Are there any parallel algorithms designed for fast matrix multiplication? If so, can someone suggest me some online sources to read about them or could possibly brief it out here in their answer.
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
24 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
46 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
76 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 ...
3
votes
0answers
21 views

Calculating determinant of sparse matrix

I have a large square n x n matrix with less than a constant c nonzero columns in each row. Is it possible to calculate the determinant of this matrix in O(n)? If not, what's the best algorithm and ...
0
votes
0answers
47 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
39 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
113 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
27 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
85 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
36 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
57 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
45 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
17 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
63 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
116 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
32 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
58 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
195 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), ...
0
votes
0answers
40 views

Efficient Power of Square Symmetric Matrix

It is known that computing the nth power of a matrix can be done in $O(D(n)+n \log(n))$ time, where where $D(n)$ is the time needed for diagonalization. What is known about square symmetric matrices? ...
0
votes
1answer
1k 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 ...
4
votes
3answers
214 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
79 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
128 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
88 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 ...
2
votes
2answers
176 views

Algorithm: Dimension increase in 1D representation of Square Matrix

Consider the matrix with dimension $m \times m$: $$ M = \begin{array}{cc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} $$ Its 1-D representation: $$ M^* = ...
3
votes
1answer
393 views

Fast algorithm for matrix chain multiplication in special case

An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying $n$ matrices $A_1 \times A_2 \times \ldots ...
5
votes
0answers
78 views

A matrix rank problem over finite fields

I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here. Let $M|\mathbf w$, where $M$ is a matrix and ...
0
votes
1answer
83 views

How to use different size features in SVM?

I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector. ...
3
votes
1answer
131 views

Why linear transformation can improve classification accuracy when the dimensionality of data is high?

Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset. When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more ...
1
vote
0answers
18 views

Approximation scheme for finding best product of matrices that minimizes $||Ax - y||$ for given $x,y$

Given a set of $N$ $n \times n$ matrices $A_1,\ldots,A_N$, and two vectors $x,y$, the problem is to find a product of up to $K$ matrices $A = A_{j_1}A_{j_2}\cdots A_{j_k}$ so that $Ax$ is as close to ...
2
votes
1answer
130 views

Power method to calculate eigenvectors

I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, ...
2
votes
1answer
30 views

Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.
4
votes
1answer
159 views

Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...
0
votes
1answer
94 views

Updating maximum sum subrectangle in a sparse matrix when one element is changed

I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional ...
-1
votes
1answer
96 views

How to determine the address of an element in a square matrix given the base address? [closed]

I was asked this question in examination. A square matrix $M$ of size $10 \times 10$ is stored in memory with each element requiring 4 bytes of storage. If the base address at $M[0][0]$ is $1840$, ...
3
votes
1answer
53 views

A canonical representative, for this equivalence relation on matrices

This question is inspired by Constructing inequivalent binary matrices. Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), ...
3
votes
3answers
1k views

Number of submatrices with a particular sum

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
2
votes
1answer
505 views

Which algorithms are usable for heatmaps and what are their pros and cons

This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove ...
5
votes
1answer
120 views

Undergrad resources for identifying regular languages with Myhill-Nerode matrices

I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure ...
4
votes
1answer
177 views

What are some applications of computing the permanent of a matrix?

What are some applications that require computing the permanent of a matrix? One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a ...
1
vote
1answer
120 views

Count elements of a sorted matrix that fall into a given interval

I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$. Each row and each column of M is sorted in the increasing order. I would like to know if there is way I can count the ...
1
vote
0answers
35 views

Laplace's Approximation for graphical models

A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ...
1
vote
1answer
151 views

Significance of parameters in Tiny Mersenne Twister algorithm

I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ...
0
votes
1answer
142 views

Number of permutation cycles in matrix transposition

I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/ The matrix can be thought of as a permutation and its transposition as another ...
2
votes
1answer
242 views

How to enumerate combinations in parallel

I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried ...
3
votes
1answer
100 views

Complexity of transposing matrices represented as list of row or column vectors

Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix |1, 2, 3| |4, 5, 6| |7, 8, 9| is $ \Omega(n^2) $ a lower bound for transposing? ...
1
vote
1answer
508 views

How do convolution matrices work?

How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work ...