# Engineering a Combinatorial Laplacian Solver: Lessons Learned +
## 3 Implementation
### Spanning Trees  
As suggested by the convergence result in Theorem 1, the KOSZ solver crucially depends on low-stretch spanning trees. The notion of stretch was introduced by [PERSON] et al. [20] along with an algorithm to compute a spanning tree with low stretch. Unfortunately, the stretch guaranteed by their algorithm is super-polynomial. [PERSON] et al. [21] presented an algorithm requiring nearly-linear time and yielding nearly-linear average stretch. The basic idea is to recursively form a spanning tree using a star of balls in each recursion step. We use [PERSON] with binary heaps for growing the balls and take care not to need more work than necessary to grow the ball. In particular, ball growing is output-sensitive, and growing a ball \(B(x,r):=\{v\in V:\text{distance from }x\text{ to }v\text{ is }\leq r\}\) should require \(\mathcal{O}(d\log n)\) time where \(d\) is the sum of the degrees of the nodes in \(B(x,r)\). The exponents of the logarithmic factors of the stretch of this algorithm were improved by subsequent papers, but [24] showed experimentally that these improvements do not yield better stretch in practice. In fact, his experiments suggest that the stretch of the provably good algorithms is usually not better than just taking a minimum-weight spanning tree. Therefore, we additionally use two simpler spanning trees without stretch guarantees: a minimum-distance spanning tree with [PERSON]'s algorithm (the tree built implicitly during the search) using binary heaps; as well as a minimum-weight spanning tree with [PERSON]'s algorithm using union-find with union-by-size and path compression. To test how dependent the algorithm is on the stretch of the spanning tree (ST), we also look at a special ST for \(n_{1}\times n_{2}\) grids. As depicted in Figure 2, we construct this spanning tree by subdividing the \(n_{1}\times n_{2}\) grid into four subgrids as evenly as possible (the subgrid sizes are shown in Figure 1(a)), recursively building the STs in the subgrids (the termination of the recursion is shown in Figure 1(b)) and connecting the subgrids by a U-shape in the middle. **Proposition 1**: _Let \(G\) be an \(n_{1}\times n_{2}\) grid with \(n_{1},n_{2}\geq 4\). Then, the special ST has \(\mathcal{O}\big{(}\frac{(n_{1}+n_{2})^{2}\log(n_{1}+n_{2})}{n_{1}n_{2}}\big{)}\) average stretch on \(G\)._  
First note that, by the recursive construction, the total stretch of the four subgrids remains the same if such a subgrid is treated separately. Moreover, the stretches of the \(\mathcal{O}(n_{1}+n_{2})\) off-tree edges between the rows \(\lfloor n_{1}/2\rfloor\) and \(\lfloor n_{1}/2\rfloor+1\), as well as the columns \(\lfloor n_{2}/2\rfloor\) and \(\lfloor n_{2}/2\rfloor+1\) arein \(\mathcal{O}(n_{1}+n_{2})\) each. To see this, let \(s\) and \(t\) be the source and target vertices of such an off-tree edge, respectively. Then, by construction, it is possible to reach the center from \(s\) in \(\mathcal{O}(n_{1}+n_{2})\) steps and \(t\) from the center likewise. Consequently, \(S\big{(}n_{1},n_{2}\big{)}=4\cdot S\big{(}n_{1}/2,n_{2}/2\big{)}+\mathcal{O} \big{(}n_{1}+n_{2}\big{)}^{2}\) when disregarding rounding. After solving, this recurrence (note that \(S(n_{1}/2,n_{2}/2)\) is essentially one fourth in size compared to \(S(n_{1},n_{2})\) as long as \(n_{1},n_{2}\geq 4\)); we get:  
\[S\big{(}n_{1},n_{2}\big{)}=\mathcal{O}\big{(}(n_{1}+n_{2})^{2}\log(n_{1}+n_{2}) \big{)}.\]  
Since the number of edges is \(\Theta(n_{1}n_{2})\), the claim for the average stretch follows. In case of a square grid (\(n_{1}=n_{2}\)) with \(N=n_{1}\times n_{2}\) vertices, we get \(S(N)=4S(N/4)+\mathcal{O}(N)=\mathcal{O}(N\log N)=\mathcal{O}(n_{1}^{2}\log(n_{ 1}))\) and, thus, \(\mathcal{O}(\log n_{1})\) average stretch. A logarithmic average stretch (and thus, detour) is noteworthy since the average distance between a random pair of nodes in the square grid is \(\Omega(n_{1})\). Furthermore, for this special case, our result slightly improves on the general low-stretch spanning tree algorithms.