The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
11 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
47 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
0answers
13 views

Write out a simplified SOP expression for a function

$0 \space 1 \space 2\space 3\space 4\space 5\space 6\space 7 \\ 15\space 14\space 13\space 12\space 11\space 10\space 9\space 8\space \\ 16\space 17\space 18\space 19\space 20\space ...
4
votes
3answers
83 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
59 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
99 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
79 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
154 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
126 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
63 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
32 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
78 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
15 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 ...
1
vote
1answer
61 views

Clustering a matrix into similar groups

I'm working on a problem where I have a matrix of values which I know will be in groups of similarly-valued elements. I am trying to find these groups of similarly-valued elements. I'm going to ...
2
votes
1answer
81 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
112 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
64 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
48 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
47 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
441 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
197 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
103 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
119 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
107 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
31 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
97 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
120 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
142 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
91 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
335 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 ...
3
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
202 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
83 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
73 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
166 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
1k 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
174 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 ...
5
votes
2answers
545 views

Matrix powering in $O(\log n)$ time?

Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time? I have been searching online, but have been unsuccessful thus far.
1
vote
1answer
517 views

Using Funk SVD with SGD?

I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here). However the framework that we are trying to integrate doesn't ...
10
votes
1answer
290 views

Common idea in Karatsuba, Gauss and Strassen multiplication

The identities used in multiplication algorithms by Karatsuba (integers) Gauss (complex numbers) Strassen (matrices) seem very closely related. Is there a common abstract framework/generalization? ...
7
votes
1answer
271 views

Probabilistic test of matrix multiplication with one-sided error

Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from ...
7
votes
1answer
133 views

Find minimum number 1's so the matrix consist of 1 connected region of 1's

Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ ...