I need to solve many small Toeplitz systems that fit entirely in cache, meaning the computation is compute bound. Are there vectorizable algorithms for this?

I found a few older articles: (https://www.sciencedirect.com/science/article/pii/S0377042702009111) but they parallelise in a strided way, which is not suitable for modern processors, or increase the number of flops to $O(n log n)$ (several examples in https://www.math.uni-kiel.de/scicom/de/absolventinnen-und-absolventen/tim-wichelmann-bachelorarbeit).

  • 3
    $\begingroup$ It is critical to know if your systems are independent and can be solved concurrently or if you need to solve them one-by-one. In the first case, the problems can be solved trivially using SIMD operations. In the second case, we can adapt the Arbenz-Heglund partitioning used by the ScaLAPACK solver for diagonally dominant systems and do a SIMD parallel implementation of single step of cyclic reduction using a sequential solver to handle the Schur complement. $\endgroup$ Commented Nov 2, 2023 at 15:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.