Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Inverting a band matrix

Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did). Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-...
• 532
Accepted

### Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix

Okay, here is a full answer. We will use the fact, that any bipartite graph of maximum degree $d$ can be broken into (at most) $d$ matchings. In our case, this means that we can split $A$ into (at ...
• 206
Accepted

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

You can use bipartite matching for that. Nodes corresponding to rows in one set, nodes corresponding to columns in the other set. A row has an edge to every column in which it has a 1. If the maximum ...
• 2,053
Accepted

### What is the literature on a sparse matrix encoding of rose trees?

In view of rose tree being just a special case of a graph, the matrix representation you mentioned is simply the adjacency matrix representation of directed graph. Your particular encoding takes the ...
• 1,205
Accepted

### Need clarification about the use of Big-O to describe matrix sparsity

What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. ...
• 277k
Accepted

### Product of sparse polynomials with FFT

Let $n>0$. Let $f(X)=X^{n^2} + X^{n(n-1)} + X^{n(n-2)}+\cdots + X^n + 1$. Let $g(X) =X^{n^2} + X^{n-1} + X^{n-2} + \cdots + 1$. \begin{aligned} f(X)g(X)&=f(X)X^{n^2} + f(X)(X^{n-1} + X^{n-2} ...
• 39k
Accepted

### Max flow algorithm for floating-point weights and E~=10*V

Push-relabel with 'highest label first' heuristic is considered state of the art for a long time. It has a theoretical running time of $O(n^2 \sqrt{m})$, but runs very fast in practice. As far as I ...
1 vote

### Mathematical operation for removing duplicate rows in a matrix

A more efficient approach is to hash each row, insert them into a hash table, and find duplicates in that way. The running time will be $O(n^2)$. You can implement something like this using only ...
• 160k
1 vote

### Classifying vectors that only contains 1001110101 numbers - Is Support Vector Machine the solution?

If I understand your question correctly, the features in your case are exclusively categorical. Support Vector Machines might work, but they would not be my model of choice for such data. SVMs try to ...
• 991
1 vote
Accepted

### Combining chunks on an infinite grid into regions

I think you've gotten yourself on the wrong path by trying to use PNG, splitting up into multiple chunks so the PNG files aren't too big, etc. Instead, store your data using any sparse matrix ...
• 160k
1 vote

### Max flow algorithm for floating-point weights and E~=10*V

Orlin's algorithm can solve max flow in sparse graphs in $O(|V| |E|)$ time. See Max flows in O(nm) time, or better. James B. Orlin. STOC 2013. You'll have to decide whether the potential speedup ...
• 160k
1 vote

### Optimize sorting matrix entries by row and column

Option 2: Compare full linear index #define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb) Instead of ...
• 39k
1 vote

### Data structure to efficiently add zero-rows to a sparse matrix

You can achieve $O(\log n)$ time for all operations, by using a balanced binary search tree for the index that maps from a row index to the row. Such a tree can support $O(\log n)$ time lookup of any ...
• 160k
1 vote

### Data structure to efficiently add zero-rows to a sparse matrix

An easy but probably undesired way is doing the operation lazily. The list of lists representation can be modified slightly to support "add row" in $O(1)$ time. When you add a row, you don't ...
• 2,393
1 vote

### Matrix-vector multiplication using only lower triangular of matrix

Answer by Clayton Gotberg [1], modified: If $\textbf{A}$ is a symmetric matrix and $\textbf{A}_{LT}$ is the lower triangular part of the matrix and $\textbf{A}_{UT}$ is the upper triangular part of ...
• 1,035
1 vote

### GraphSlam Doubt

Often we use $0$ to represent the all-zeros matrix, so the instruction to set $\Omega = 0$ might mean to set it to the all-zeros matrix (with a zero in every entry). You'll have to figure out from ...
• 160k
1 vote
Accepted

### Finding the bandwidth of a band matrix

As a sparse matrix is mostly made of zeros. Using a 2-dimensional array for all elements will be an inefficient way to represent such data as more than half of the array will be zeroes which is the ...
1 vote

### Running time of sparse matrix multiplication

The question doesn't make any sense. It doesn't make sense to ask for the running time of a computation, unless you specify an algorithm for that computation. So how would you calculate this product? ...
• 30.4k

Only top scored, non community-wiki answers of a minimum length are eligible