Аннотация:
В статье рассмотрена параллельная реализация рандомизированного регуляризованного алгоритма Качмажа. Приведён пример использования параллельной рандомизированной версии алгоритма для решения интегрального уравнения Фредгольма первого рода с возмущённой правой частью, и показано, что в этом случае удаётся ускорить вычисления до 4 раз по сравнению с последовательной рандомизированной версией.

Ключевые слова :
итерационные методы, регуляризованные решения, параллельные вычисления, обработка сигналов.

Цитирование:
Жданов, А.И. Параллельная реализация рандомизированного регуляризированного алгоритма Качмажа / А.И. Жданов, Ю.В. Сидоров // Компьютерная оптика. – 2015. – Т. 39, № 4. – С. 536-541. – DOI: 10.18287/0134-2452-2015-39-4-536-541.

Литература:

1. Kaczmarz, S. Angenäherte Auflösung von Systemen linearer Gleichungen / S. Kaczmarz // Bulletin International de l'Académie Polonaise des Sciences et des Lettres. – 1937. – Vol. 35. – P. 355-257.
2. Zouzias, A. Randomized Extended Kaczmarz for Solving Least Squares / A. Zouzias, N.M. Freris // SIAM Journal on Matrix Analysis and Applications. – 2013. – Vol. 34, N 2. – P. 773-793. – ISSN 0895-4798.
3. Thoppe, G.A. Stochastic Kaczmarz algorithm for network tomography / G.A. Thoppe, V. Borkar, D. Manjunath // Automatica. – 2014. – Vol. 50, N 3. – P. 910-914.
4. Needell, D. Randomized Kaczmarz solver for noisy linear systems / D. Needell // BIT Numerical Mathematics. – 2010. – Vol. 50, N 2. – P. 395-403. – ISSN 0005-1098.
5. Popa, C. Kaczmarz extended algorithm for tomographic image reconstruction from limited-data / C. Popa, R. Zdunek // Mathematics and Computers in Simulation. – 2004. – Vol. 65, N 6. – P. 579-598. – ISSN: 0378-4754
6. Natterer, F. The Mathematics of Computerized Tomography / F. Natterer. – Society for Industrial and Applied Mathematics, 2001. – 226 p.
7.  Feichtinger, H.G. New Variants of the POCS Method using Affine Subspaces of Finite Codimension with Applications to Irregular Sampling / H.G. Feichtinger, C. Cenker, M. Mayer, H. Steier, T. Strohmer [Электронный ресурс]. – URL: https://www.math.ucdavis.edu/~strohmer/papers/1992/cfm1292.pdf (дата обращения 05.07.2015).
8. Åström, K. Theory and applications of adaptive control – A survey / K. Åström // Automatica. – 1983. – Vol. 19, N 5. – P. 471-486. – ISSN 0005-1098.
9. Parks, P.C. A comparison of five algorithms for the training of CMAC memories for learning control systems / P.C. Parks, J. Militzer // Automatica. – 1992. – Vol. 28, N 5. – P. 1027-1035. – ISSN 0005-1098.
10. Richalet, J. Model predictive heuristic control: Applications to industrial processes / J. Richalet, A. Rault, J.L. Testud, J. Papon // Automatica. – 1978. – Vol. 14, N 5. – P. 413-428. – ISSN 0005-1098.
11. Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. – 2009. – Vol. 15, N 2. – P. 262-278. – ISSN 1069-5869.
12. Жданов, А.И. Проекционный регуляризирующий алгоритм для решения некорректных линейных алгебраических систем большой размерности / А.И. Жданов, А.А. Иванов // Вестник Самарского государственного технического университетата. Серия Физ.-мат. науки. –2010. – Т. 5, № 21. – С. 309-312.
13. Ivanov, A.A. Kaczmarz Algorithm For Tikhonov Regularization Problem / A.A. Ivanov, A.I. Zhdanov // Applied Mathematics. E-Notes. – 2013. – Vol. 13. – P. 270-276.
14. Sinha, L. Quantification of the binding potential of cell-surface receptors in fresh excised specimens via dual-probe modeling of SERS nanoparticles / L. Sinha, Y. Wang, C. Yang, Al. Khan, J.G. Brankov, JT.C. Liu, K.M. Tichauer [Электронный ресурс]. – 2015. – URL: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4341215/ (дата обращения 05.07.2015).
15. Ортега, Дж.М. Введение в параллельные и векторные методы решения линейных систем / Дж. Ортега; пер. с анг. – М.: Мир, 1991. – 367 с. (J.M. Ortega. Introduction to Parallel and Vector Solution of Linear Systems. – N.Y.: Plenum Press, 1988).
16. Алексеев, В.А. Векторизация метода распространяющегося пучка и его реализация по технологии cuda / В.А. Алексеев, Д.Л. Головашкин // Компьютерная оптика. – 2010. – Т. 34, № 2. – С. 225-230.
17. Якимов, П.Ю. Предварительная обработка цифровых изображений в системах локализации и распознавания дорожных знаков / П.Ю. Якимов // Компьютерная оптика. – 2013. – Т. 37, № 3. – С. 401-405.
18. Изотов, П.Ю. Технология реализации нейросетевого алгоритма в среде cuda на примере распознавания рукописных цифр / П.Ю. Изотов, С.В. Суханов, Д.Л. Головашкин // Компьютерная оптика. – 2010. – Т. 34, № 2. – С. 243-251.
19. Elble, J.M. GPU computing with Kaczmarz’s and other ite­rative algorithms for linear systems / J.M. Elble, N.V. Sahi­nidis, Panagiotis Vouzisb [Электронный ресурс]. – 2010. – URL: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2879082/ (дата обращения 05.07.2015).
20. Liu, Ji. An Asynchronous Parallel Randomized Kaczmarz Algorithm / Ji. Liu, S.J. Wright, S. Sridhar [Электронный ресурс]. – 2014. –  URL: http://arxiv.org/pdf/1401.4780v2.pdf (дата обращения 05.07.2015).
21. Phillips, D.L. A technique for the numerical solution of certain integral equations of the first kind / D.L. Phillips // Journal of the ACM. – 1962. – Vol. 9, Issue 1. – P. 84-97.
22. Intel® MKL [Электронный ресурс]. – URL: https://software.intel.com/en-us/intel-mkl (дата обращения 05.07.2015).
23. Ильин, В.П. О вопросах распараллеливания крыловских итерационных методов / В.П. Ильин // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. – 2013. – Т. 2, № 3. – С. 48-62.
24. Regularization Tools Version 4.0 for Matlab 7.3 / P.Ch. Hansen // Numerical Algorithms. – 2007. – Vol. 46, Issue 2. – P. 189-194.
25. Старк, Г. Реконструкция изображений/ Г. Старк; пер. с англ. – М.: Мир, 1992. – 336 с. (H. Stark, ed. Image Recovery, Theory and Application . – N.Y.: Academic Press, 1987).
26. NVIDIA CUDA® [Электронный ресурс]. – URL: http://www.nvidia.ru/object/cuda-parallelcomputing-ru.html (дата обращения 05.07.2015).

---

© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20