I am working on a problem, and for testing purposes, I want to do the following.
Let be given a sparse graph $G(V,E)$ with edge weight matrix $W$, and $|V|$ large (anywhere from $10^3$ to $10^6$). We are looking for a function $f: V \to \mathbb{R}$, such that
$$f(i)=0, \quad f(j)=1, \quad f(k) -\sum_{l} W_{kl} f(l) = 0 \quad \forall k\neq i,j$$
That is, we are looking for a discrete harmonic function with boundary conditions as above. To my best knowledge there are two approaches when solving problems like this:
- Solve the linear system arising from the problem using some direct method. This could be done for $|V|$ small, but no chance for large $|V|$s.
- Iterate over the vertices, and set $f(k)=\sum_{l}W_{kl}f(l)$, i.e. modify the function to be locally harmonic, and repeat until convergence. Again, this method might be feasible for toy problems, but definitely not for many vertices.
I'll also explain what I need this for, maybe that helps. In one interpretation, the problem I am solving is equivalent to applying a voltage of 1 volts to two arbitrary junctions in a massive resistor network, and trying to calculate the voltages at each point of the network.