Suppose I have a set of sources U and a set of sinks V and a set of directed edges E going from elements of U to elements of V.
I want to find a vector z of size |E| (each value of z is assigned to an edge) such that, for each node in U and V, the sum of the values assigned to its adjacent edges is zero.
What I have done up to now :
Define A of size (|U|+|V|)x(|E|) with A(i,j)=1 if edge j is adjacent to node i, 0 otherwise.
All elements of the nullspace of A (i.e. z s.t. Az=0) fit the bill.
But computing the nullspace of a large (even sparse) matrix is expensive. (I have done it through QR factorization using suitesparseQR).
Any suggestion as to a whole different way to do this of a faster way to calculate a random element of the nullspace of a large sparse rectangular matrix is welcome.