Реализация и оценка сходимости итерационных CG и PCG решателей многократной точности для графических процессоров
Автор: Исупов Константин Сергеевич, Князьков Владимир Сергеевич, Коржавина Анастасия Сергеевна
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 1 (54), 2022 года.
Бесплатный доступ
Для решения систем линейных алгебраических уравнений с разреженными матрицами коэффициентов широко применяются итерационные методы подпространства Крылова. Однако сходимость этих методов может ухудшаться из-за ошибок округления, возникающих при выполнении вычислений в арифметике фиксированной разрядности. Снизить влияние ошибок округления позволяет использование арифметики многократной точности, обеспечивающей выполнение операций с числами повышенной разрядности. В статье представлены реализации итерационных решателей многократной точности на базе метода сопряженных градиентов без предобуславливания и с диагональным предобуславливанием для графических процессоров видеокарт. Для поддержки вычислений с числами повышенной разрядности используется система остаточных классов. Матрично-векторное произведение реализовано в виде гибридного ядра, в котором матрица двойной точности, представленная в формате CSR, умножается на вектор многократной точности. Параллельное скалярное произведение вычисляется с использованием двухэтапного алгоритма. Результаты экспериментов с разреженными матрицами различных размеров показывают, что повышенная точность арифметики позволяет ускорить сходимость итерационных методов.
Разреженная линейная алгебра, метод сопряженных градиентов, арифметика многократной точности, система остаточных классов, cuda
Короткий адрес: https://sciup.org/143179062
IDR: 143179062 | DOI: 10.24412/2073-0667-2022-1-17-27
Список литературы Реализация и оценка сходимости итерационных CG и PCG решателей многократной точности для графических процессоров
- Saad Y. Iterative Methods for Sparse Linear Systems, 2nd ed. Philadelphia: SIAM, 2003. 547 p.
- Barrett R. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (2nd Edition) / R. Barrett et al. Philadelphia: SIAM, 1994. 107 p.
- Saito Т., Ishiwata E., Hasegawa H. Analysis of the GCR method with mixed precision arithmetic using QuPAT // Journal of Computational Science. 2012. Vol. 3, N 3. P. 87-91. DOI: 10.1016/j.joes.2011.05.001.
- Cools S., Yetkin E.F., Agullo E., Giraud L., Vanroose W. Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method // SIAM Journal on Matrix Analysis and Applications. 2018. Vol. 39, N 1. P. 426-450. DOI: 10.1137/17M1117872.
- Kouva T. A highly efficient implementation of multiple precision sparse matrix-vector multiplication and its application to product-type Krvlov subspace methods // International Journal of Numerical Methods and Applications. 2012. Vol. 7, N 2. P. 107-119.
- Hishinuma Т., Hasegawa H., Tanaka T. SIMD Parallel Sparse Matrix-Vector and Transposed-Matrix-Vector Multiplication in DD Precision // Lecture Notes in Computer Science. 2017. Vol. 10150. P. 21-34.
- Hasegawa H. Utilizing the quadruple-precision floating-point arithmetic operation for the Krvlov subspace methods. 2003. [Electron. Res.]: http://www.slis.tsukuba.ac.jp/~hasegawa.hidehiko. ga/GYOSEKI/hhasegaw.pdf (accessed 17 January 2022).
- Masui K. Ogino M. Research on the Convergence of Iterative Method Using Mixed Precision Calculation Solving Complex Symmetric Linear Equation // IEEE Transactions on Magnetics. 2020. Vol. 56, N 1. Article no. 7503604. DOI: 10.1109/TMAG.2019.2951280.
- Mukunoki D., Takahashi D. Using Quadruple Precision Arithmetic to Accelerate Krvlov Subspace Methods on GPUs // Lecture Notes in Computer Science. 2014. Vol. 8384. P. 632-642. DOI: 10.1007/978-3-642-55224-3^59.
- Isupov K., Knvazkov V. Multiple-Precision BLAS Library for Graphics Processing Units // Communications in Computer and Information Science. 2020. Vol. 1331. P. 37-49. DOI: 10.1007/978-3-030-64616-5^4.
- Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. Imperial College Press, 2007. 402 p.
