Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа

Автор: Жданов Александр Иванович, Сидоров Юрий Вячеславович

Журнал: Компьютерная оптика @computer-optics

Статья в выпуске: 4 т.39, 2015 года.

Бесплатный доступ

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

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

Короткий адрес: https://sciup.org/14059591

IDR: 14059591 | DOI: 10.18287/0134-2452-2015-39-4-536-541

Список литературы Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа

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.
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.
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.
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.
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
Natterer, F. The Mathematics of Computerized Tomography/F. Natterer. -Society for Industrial and Applied Mathematics, 2001. -226 p.
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).
Å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.
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.
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.
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.
Жданов, А.И. Проекционный регуляризирующий алгоритм для решения некорректных линейных алгебраических систем большой размерности/А.И. Жданов, А.А. Иванов//Вестник Самарского государственного технического университетата. Серия Физ.-мат. науки. -2010. -Т. 5, № 21. -С. 309-312.
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.
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).
Ортега, Дж.М. Введение в параллельные и векторные методы решения линейных систем/Дж. Ортега; пер. с анг. -М.: Мир, 1991. -367 с. (J.M. Ortega. Introduction to Parallel and Vector Solution of Linear Systems. -N.Y.: Plenum Press, 1988).
Алексеев, В.А. Векторизация метода распространяющегося пучка и его реализация по технологии cuda/В.А. Алексеев, Д.Л. Головашкин//Компьютерная оптика. -2010. -Т. 34, № 2. -С. 225-230.
Якимов, П.Ю. Предварительная обработка цифровых изображений в системах локализации и распознавания дорожных знаков/П.Ю. Якимов//Компьютерная оптика. -2013. -Т. 37, № 3. -С. 401-405.
Изотов, П.Ю. Технология реализации нейросетевого алгоритма в среде cuda на примере распознавания рукописных цифр/П.Ю. Изотов, С.В. Суханов, Д.Л. Головашкин//Компьютерная оптика. -2010. -Т. 34, № 2. -С. 243-251.
Elble, J.M. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems/J.M. Elble, N.V. Sahinidis, Panagiotis Vouzisb . -2010. -URL: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2879082/(дата обращения 05.07.2015).
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).
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.
Intel® MKL . -URL: https://software.intel.com/en-us/intel-mkl (дата обращения 05.07.2015).
Ильин, В.П. О вопросах распараллеливания крыловских итерационных методов/В.П. Ильин//Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. -2013. -Т. 2, № 3. -С. 48-62.
Regularization Tools Version 4.0 for Matlab 7.3/P.Ch. Hansen//Numerical Algorithms. -2007. -Vol. 46, Issue 2. -P. 189-194.
Старк, Г. Реконструкция изображений/Г. Старк; пер. с англ. -М.: Мир, 1992. -336 с. (H. Stark, ed. Image Recovery, Theory and Application. -N.Y.: Academic Press, 1987).
NVIDIA CUDA® . -URL: http://www.nvidia.ru/object/cuda-parallelcomputing-ru.html (дата обращения 05.07.2015).

Еще

Статья научная