## 4 Algorithm for Minimization of Second-derivative-based 5-point-window Spline Functional
### Stop. **5. Analysis-based Algorithm** _vs._ **Primal Affine Algorithm for 5-point Windows**  
In this section, we compare computational results generated by the analysis-based algorithm introduced in Section 4 and the widely used primal affine algorithm described in Section 2. These results differ significantly (by more than \(10^{-4}\)) at a number of nodes as shown in Table 2. It was confirmed by hand calculation that the results for the analysis-based algorithm are accurate for the original nondiscretized \(L_{1}\) spline functional (a confirmation of both the analysis-based algorithm and the code). The differences in the results produced by the primal affine algorithm and the analysis-based algorithm are due mainly to the discretization (midpoint rule with 100 subintervals, as described in Section 2). **Remark** On 5-point windows, the primal affine algorithm converges well. However, for global \(L_{1}\) splines on large data sets, the primal affine algorithm can converge slowly or not at all, especially in bivariate situations, as indicated in Section 6 of [9], a conclusion supported by additional unpublished computational experience of the authors. In such situations, the \(L_{1}\) spline functional may result in a nearly degenerate nonlinear program and this near degeneracy is retained in the discretized version. The analysis-based algorithm introduced in this paper does not require discretization of the \(L_{1}\) spline functional and does not require regularization terms to be added to this functional. The algorithm is simple, accurate and inherently parallelizable. Moreover, it is computationally much cheaper than the primal affine algorithm. Both of the algorithms were implemented in C++ 6.0. Computational results for the data set of Section 1 were generated on an IBM laptop running under the Windows XP operating system at 1.66 GHz CPU with 1.50 GB RAM and were presented in Section 3. The computing times of the primal affine algorithm were  
* 177.7 milliseconds for a 5-point window (sequential calculations),
* 335.2 milliseconds for a 7-point window (sequential calculations),
* 94.9 milliseconds for global  
for the second-derivative-based \(L_{1}\) splines of Figures 2, 3 and 4, respectively. The computing time of the analysis-based algorithm was  
* 0.0531 milliseconds for a 5-point window (sequential calculations)  
for the second-derivative-based \(L_{1}\) spline that corresponds to Figure 2. In these computational experiments, the sequential analysis-based algorithm is thus \(177.7/0.0531=3347\) times faster than the sequential primal affine algorithm. The speed-up for the parallel versions of these algorithms would be roughly the same, since each parallel version would be faster than the corresponding sequential version by a factor roughly equal to the number of points in the data set (56 in this case). The sequential analysis-based algorithm is faster than the global primal affine algorithm by a factor of \(94.9/0.0531=1787\). The speed-up of the parallel analysis-based algorithm vs. the global primal affine algorithm would, therefore, be roughly a factor of \(1787.2\times 56\approx 10^{5}\), an impressive amount. For larger data sets, the speed-up is correspondingly larger. **Remark** The computing time for the primal affine algorithm could be reduced by decreasing the number of subintervals \(K\) for discretization (via the midpoint rule) of the spline functional from 100, as was used for the results generated for this paper, to, say, 10, or less. However, since the degree to which \begin{table}
\begin{tabular}{|c|c|c|c|} \hline \(i\) & \(x_{i}\) & \(b_{i}^{*}\) from primal affine algorithm & \(b_{i}^{*}\) from analysis-based algorithm \\ \hline
7 & 6.01 & 3.4096 & 3.3874 \\
29 & 27.2 & 20.9698 & 20.9729 \\
30 & 27.3 & 19.5166 & 19.5250 \\
31 & 34.7 & -19.5166 & -19.5250 \\
32 & 34.8 & -20.9698 & -20.9729 \\
38 & 37.2 & 27.5971 & 27.6099 \\
39 & 37.3 & 18.4160 & 18.4667 \\
40 & 44.7 & 18.4160 & 18.4667 \\
41 & 44.8 & 27.5971 & 27.6099 \\ \hline \end{tabular}
\end{table}