11 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-...
  • 453
4 votes
Accepted

SimRank on a weighted directed graph (how to calculate node similarity)

The paper "SimRank++: Query Rewriting through Link Analysis of the Click Graph" describes a weighted SimRank algorithm that is similar to my attempt. It uses this formula to update similarity scores: ...
  • 81
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 ...
3 votes

Data structure for sparse matrices for an online problem

The state-of-the art for any MILP like you describe, is complicated software like CPLEX (or some other expensive proprietary package). Such packages do take into account issues of sparse linear ...
3 votes

Data structure for sparse matrices for an online problem

In low dimension, Seidel's algorithm can be useful: if we have the optimal solution to $m$ constraints in $d$ dimensions, and you add one more constraint, then the amortized cost to find the optimal ...
  • 144k
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 ...
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. ...
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} ...
  • 35.3k
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 ...
  • 1,838
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 ...
  • 144k
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 ...
  • 144k
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 ...
  • 1,446
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 ...
  • 35.3k
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? ...
  • 25.9k

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