A Fast Sparse Block Circulant Matrix Vector Product

摘要: In the context of computed tomography (CT), iterative image reconstruction techniques are gaining attention because high-quality images becoming computationally feasible. They involve solution large systems equations, whose cost is dominated by sparse matrix vector product (SpMV). Our work considers case matrices being block circulant, which arises when taking advantage rotational symmetry in tomographic system. Besides straightforward storage saving, we exploit circulant structure to rewrite poor-performance SpMVs into a high-performance between and dense matrices. This paper describes implementations developed for multi-core CPUs GPUs, presents experimental results with typical CT The presented approach up ten times faster than without exploiting structure.