Skip to main content
Share Your Experience: Take the 2024 Developer Survey
12 votes

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-...
chausies's user avatar
  • 532
3 votes
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 ...
Thomas Ahle's user avatar
2 votes
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 ...
user555045's user avatar
  • 2,053
2 votes
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 ...
Apiwat Chantawibul's user avatar
2 votes
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. ...
Yuval Filmus's user avatar
2 votes
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} ...
John L.'s user avatar
  • 39k
2 votes
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 ...
barakugav's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
DirkT's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
John L.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
pcpthm's user avatar
  • 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 ...
Justin Shenk's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Romantic Electron's user avatar
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? ...
gnasher729's user avatar
  • 30.4k

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