4

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-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve ...


3

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: $s_{k+1}(a, b) = \text{evidence}(a, b) \cdot C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b) \cdot \text{spread}(i) \cdot \...


3

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 algebra, but this is a problem of numerical stability just as much as efficiency. See for example: (http://www.gurobi.com/resources/getting-started/lp-basics). Those ...


3

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 solution to those $m+1$ constraints is $O(d!)$, assuming the constraints are being presented in a random order. (It is usually presented in the following form: ...


2

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 rose tree's edge to always be directed consistently either from parent to child or child to parent. Questions about rose tree in this encoding thus can be ...


2

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. For example: Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$. What this really means is: For every $C > 0$ ...


2

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 most) $\sqrt{k}$ disjoint sets of elements $S_i\subseteq\{(i,j)\in[n]\times[n] \mid A_{i,j}=1\}$ of size at most $n$ such that any every element in each set has ...


2

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 matching has size n, every row is matched up with a corresponding column and the matching gives the order. The index of the column that a row is matched up ...


1

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 N, use the minimal power of 2 that is not less than N. For example, if N = 10000, use $2^{14}=16348$. So we can have #define COMPARE(ia,ja,ib,jb) ((ia << 14) + ja < (ib << 14) + jb ? -1 : (ia << 14) + ...


1

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 context whether that seems correct.


1

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 reason for the increased time cost for finding bandwidth in your case. In your case if you have a matrix $M$ of size $n * m$ then you'll be using a 2 dimensional ...


1

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? That's the first thing you need to do: Specify an algorithm how you calculate the product. The next step: Assuming that many array elements are zero, can you ...


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