Parallel implementation of a randomized regularized Kaczmarz's algorithm
A.I. Zhdanov, Y.V. Sidorov

 

Samara State Technical University (SamSTU),

PIHE the Samara Institute of Management

Full text of article: Russian language.

 PDF

Abstract:
The article describes the parallel implementation of a randomized regularized Kaczmarz's algorithm. By way of illustration, the randomized parallel version of the algorithm is used for solving the Fredholm integral equation of the first kind with a perturbed right-hand side, showing that in this way the computation speed can be increased up to 4 times as compared to the sequential randomized version.

Keywords:
iterative methods, regularized solutions, parallel computing, signal processing.

Citation:
Zhdanov AI, Sidorov YV. Parallel implementation of a randomized regularized Kaczmarz's algorithm. Computer Optics 2015; 39(4): 536-41. DOI: 10.18287/0134-2452-2015-39-4-536-541.

References:

  1. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen. Bulletin International de l'Académie Polonaise des Sciences et des Lettres 1937; 35: 355-57.
  2. Zouzias A, Freris NM. Randomized Extended Kaczmarz for Solving Least Squares. SIAM Journal on Matrix Analysis and Applications 2013; 34(2): 773-93.
  3. Thoppe G, Borkar V, Manjunath D. A stochastic Kaczmarz algorithm for network tomography. Automatica 2014; 50(3): 910-14.
  4. Needell D. Randomized Kaczmarz solver for noisy linear systems. BIT Numerical Mathematics 2010; 50(2): 395-403.
  5. Popa C, Zdunek R. Kaczmarz extended algorithm for topographic image reconstruction from limited-data. Mathematics and Computers in Simulation 2004; 65(6): 579-98.
  6. Natterer F. The Mathematics of Computerized Tomography. Society for Industrial and Applied Mathematics;2001.
  7. Feichtinger HG, Cenker C, Mayer M, Steier H, Strohmer T. New Variants of the POCS Method using Affine Subspaces of Finite Codimension with Applications to Irregular Sampling. Source:  <https://www.math.ucdavis.edu/~strohmer/papers/1992/cfm1292.pdf>.
  8. Åström K. Theory and applications of adaptive control–A survey. Automatica 1983; 19(5): 471-86.
  9. Parks PC., Militzer J. Model predictive heuristic control: Applications to industrial processes. Automatica 1978; 14(5): 413-28.
  10.  Richalet J, Rault A, Testud JL, Papon J. Model predictive heuristic control: Applications to industrial processes. Automatica 1992; 28(5): 1027-103.
  11.  Strohmer T, Vershynin R. A Randomized Kaczmarz Algorithm with Exponential Convergence. Journal of Fourier Analysis and Applications 2009; 15(2): 262-78.
  12. Zhdanov AI, Ivanov AA. Projection regularization algorithm for solving linear algebraic system of large dimension. “Vestnic Samarskogo gosudarstvennogo tehnicheskogo Universiteta” Publisher 2010; 5(21): 309-12.
  13. Ivanov AA, Zhdanov AI. Kaczmarz Algorithm For Tikhonov Regularization. Problem. Appl. Math. E-Notes 2013; 13: 270-6.
  14. Sinha L, Wang Yu, Yang C, Khan Al, Brankov JG, Jonathan T, Liu C, Tichauer K.M. Quantification of the binding potential of cell-surface receptors in fresh excised specimens via dual-probe modeling of SERS nanoparticles. Source: <http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4341215/>
  15. Ortega JM. Introduction to Parallel and Vector Solution of Linear Systems. New York: Plenum Press; 1988.
  16. Alekseev PY, Golovashkin DL. Vectoring propagating beam method and its realization technology cuda [In Russian]. Computer Optics 2010; 34(2): 225-230.
  17. Yakimov PY. Pre-processing of digital images in the systems of localization and recognition of road signs. Computer Optics 2013; 37(3): 401-405.
  18. Izotov PY, Sukhanov SV, Golovashkin DL. Technology implementation of neural network algorithm in an environment cuda an example of recognition of handwritten digits [In Russian]. Computer Optics 2010; 34(2): 243-251.
  19. Elble JM, Sahinidis NV, Vouzisb P. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems. Source: <http://www.ncbi.nlm.nih.gov/pmc/articles/ PMC2879082/>.
  20. Liu Ji, Wright SJ, Sridhar S. An Asynchronous Parallel Randomized Kaczmarz Algorithm. Source:  <http://ar­xiv.org/pdf/1401.4780v2.pdf>.
  21. Phillips DL. A technique for the numerical solution of certain integral equations of the first kind. Journal of the ACM 1962; 9(1): 84-97.
  22. Intel® MKL. Source: < https://software.intel.com/en-us/intel-mkl>
  23. Ilyin VP. On issues of parallelizing Krylov iterative methods. [In Russian]. Bulletin of the South Ural State University. Series: Computational Mathematics and Informatics 2013; 2(3): 48-62.
  24. Hansen PC. Regularization Tools Version 4.0 for Matlab 7.3. Numerical Algorithms 2007. 46(2): 189-194.
  25. H. Stark, ed. Image Recovery, Theory and Application. N.Y.: Academic Press; 1987.
  26. NVIDIA CUDA®. Source: <http://www.nvidia.ru/object/cuda-parallelcomputing-ru.html>.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail:journal@computeroptics.ru; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20