We will next present a fast method for computing the smaller 1D problems \(Q^{(k)} {\bf z}\)  and \(\hat{Q}^{(k)} {\bf z}\) 
obtained in step 1.
We will show that, thanks to
assumption A2, the hierarchical matrix technique
[1]} can be employed to compute each one-dimensional
problem with a near-linear complexity \({\mathcal {O}}(n_k \, \log ^2n_k)\) .
