A mathematical report on Cimmino's algorithm for solving linear systems. Completed as part of the unit SIT292 Linear Algebra for Data Analysis at Deakin University. For a practical implementation of Cimmino's algorithm for phantom reconstruction in Metal/C++, see GPU Phantom Reconstruction.
Cimmino's method is a row-action iterative algorithm that is used to solve and approximate solutions to high-dimensional and sparse linear systems, both consistent and inconsistent, where direct methods such as Gaussian elimination are computationally expensive or infeasible. Direct methods are slow for large systems, and often have substantial and impractical memory requirements. Cimmino's method offers an efficient alternative, capable of finding sufficiently accurate solutions at a viable computational cost. Its inherent parallelisability and low memory requirements make it particularly suitable for large-scale problems, such as those encountered in Computed Tomography (CT) image reconstruction.
This report provides an in-depth exploration of the theoretical foundations of Cimmino's algorithm. We present a formal proof of convergence, demonstrating that the iterative sequence converges to a solution of the system if it is consistent, or to the weighted least squares solution if it is inconsistent. The analysis is grounded in the orthogonal decomposition of
- Further explore non-expansive mappings, including firmly non-expansive mappings, strictly non-expansive mappings, and fixed point theory, to deepen understanding of the convergence properties of Cimmino's algorithm.
- Investigate Cimmino's algorithm as belonging to a broader family of projection algorithms for solving convex feasibility problems.