The matrices tag has no wiki summary.
2
votes
1answer
63 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
64 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
82 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 ...
2
votes
1answer
83 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 ...
6
votes
1answer
91 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 ...
0
votes
0answers
28 views
multigrid method to solve PDE [closed]
I need explanation of the Multigrid Method or some literature.
I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with multigrid method.
...
2
votes
1answer
49 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
64 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
112 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
538 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
160 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
223 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
113 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
176 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?
...
6
votes
1answer
124 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
121 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$ ...
