# Engineering a Combinatorial Laplacian Solver: Lessons Learned +
## 4 Evaluation
### Results
#### 4.2.5 Smoothing  
One way of combining the good qualities of two different solvers is smoothing. Smoothing means to dampen the high-frequency components of the error, which is usually done in combination with another solver that dampens the low-frequency error components. It is known that in CG and most other solvers, the low-frequency components of the error converge very quickly, while the high-frequency components converge slowly. Thus, we are interested in finding an algorithm that dampens the high-frequency components, a good smoother. This smoother does not necessarily need to reducing the error, it just needs to make its frequency distribution more favorable. Smoothers are particularly often applied at each level of multigrid or multilevel schemes [44] that turn a good smoother into a good solver by applying it at different levels of a matrix hierarchy.  
To test whether the Laplacian solver is a good smoother, we start with a fixed \(x\) with \(Lx=b\) and add white uniform noise in \([-1,1]\) to each of its entries in order to get an initial vector \(x_{0}\). Then, we execute a few iterations of our Laplacian solver and check whether the high-frequency components of the error have been reduced. Unfortunately, we cannot directly start at the vector \(x_{0}\) in the solver. Our solution is to use Richardson iteration. That is, we transform the residual \(r=b-Lx_{0}\) back to the source space by computing \(L^{-1}r\) with the Laplacian solver, get the error \(e=x-x_{0}=L^{-1}r\) and then the output solution \(x_{1}=x_{0}+L^{-1}r\).  
Figure 6: Convergence of the residual when using the Laplacian solver as a preconditioner on an unweighted \(100\times 100\) grid.  
Figure 7 shows the error vectors of the solver for a 32 \(\times\) 32 grid together with their transformations into the frequency domain for different numbers of iterations of our solver. We see that the solver may indeed be useful as a smoother since the energies for the large frequencies (on the periphery) decrease rapidly, while small frequencies (in the middle) in the error remain.  
In the solver, we start with a flow that is nonzero only on the ST. Therefore, the flow values on the ST are generally larger at the start than in later iterations, where the flow will be distributed among the other edges. Since we construct the output vector by taking potentials on the tree, after one iteration, \(x_{1}\) will, thus, have large entries compared to the entries of \(b\). In Subplot (c) of Figure 7, we see that the start vector of the solver has the same structure as the special ST and that its error is very large. For the 32 \(\times\) 32 grid, we, therefore, need about 10,000 iterations (\(\approx\)150 SpMVs in running time comparison) to get an error of \(x_{1}\) similar to \(x_{0}\), even though the frequency distribution is favorable. Note that the number of SpMVs to which the 10,000 iterations correspond depends on the graph size, e.g., for an 100 \(\times\) 100 grid, the 10,000 iterations correspond to 20 SpMVs.  
While testing the Laplacian solver in a multigrid scheme could be worthwhile, the bad initial vector creates robustness problems when applying the Richardson iteration multiple times with a fixed number of iterations of our solver. In informal tests, multiple Richardson steps lead to ever increasing errors without improved frequency behavior unless our solver already yields an almost perfect vector in a single run.