The use of iterative algebraic methods applied to the reconstruction of computed tomography (CT) medical images is proliferating to reconstruct high-quality CT images using far fewer views than through analytical methods. This would imply reducing the dose of X-rays applied to patients who require this medical test. Least-squares methods are a promising approach to reconstruct the images with few projections obtaining high quality. In addition, since these techniques involve a high computational load, it is necessary to develop efficient methods that make use of high-performance-computing tools to accelerate reconstructions. In this paper, three least-squares methods are analyzed—Least-Squares Model Based (LSMB), Least-Squares QR (LSQR), and Least-Squares Minimal Residual (LSMR)—to determine whether the LSMB method provides faster convergence and thus lower computational times. Moreover, a block version of both the LSQR method and the LSMR method was implemented. With them, multiple right-hand sides (multiple slices) can be solved at the same time, taking advantage of the parallelism obtained with the implementation of the methods using the Intel Math Kernel Library. The two implementations are compared in terms of convergence, time, and quality of the images obtained, reducing the number of projections and combining them with a regularization and acceleration technique. The experiments show how the implementations are scalable and obtain images of good quality from a reduced number of views, with the LSQR method being better suited for this application.