The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
34 views

Calculate the computational complexity of multiplication AxAT

I need to implement an algorithm that calculates the symmetric matrix obtained by performing AXAt being At the transpose of A. I did my analysis from two perspectives: (1) The first thing I notice ...
0
votes
1answer
29 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
98 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
24 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
36 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
24 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
40 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
43 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
59 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
65 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
28 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
52 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
120 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
33 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
836 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
182 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
2answers
70 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
115 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
82 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
170 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
359 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
74 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
63 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
111 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
114 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
29 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
142 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
84 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
73 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
52 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
910 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
402 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
119 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
164 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
117 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
32 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
135 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
138 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
208 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
98 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
481 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 ...
4
votes
1answer
1k views

Algorithm for generating heat maps

I am looking to generate a heat map from some data. I have a value and a location (longitude and latitude). I understand generating a colour from the value, however I'm not sure how I would go about ...
7
votes
1answer
239 views

2-D peak finding complexity (MIT OCW 6.006)

In a recitation video for MIT OCW 6.006 at 43:30, Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to ...
2
votes
1answer
91 views

LU decomposition with pivoting

I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero. How to solve this problem? Iterational methods are ...
2
votes
1answer
74 views

How to correlate a matrix of values to get a coordinated point?

I got a n*m matrix updated in realtime (i.e. about every 10ms) with values between 0 and 1024, and I want to work out from that matrix a multitouch trackpad behaviour, which is: generate one or more ...
3
votes
1answer
176 views

How do you go about designing a vector processor architecture for the sum of matrix products?

The following equation is a matrix expression where $B_i$ and $C_i^T$ are $n\times n$ matrices and k is a positive integer: $$P = \sum_{i=1}^k B_i C_i^T $$ So $P = B_1 C_1^T + B_2 C_2^T + \cdots ...
2
votes
2answers
2k views

Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order

I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested ...
6
votes
1answer
180 views

What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can ...