GPU Accelerated Newton for Taylor Series Solutions of Polynomial Homotopies in Multiple Double Precision
Pages 328 - 348
Abstract
A polynomial homotopy is a family of polynomial systems, typically in one parameter t. Our problem is to compute power series expansions of the coordinates of the solutions in the parameter t, accurately, using multiple double arithmetic. One application of this problem is the location of the nearest singular solution in a polynomial homotopy, via the theorem of Fabry. Power series serve as input to construct Padé approximations.
Exploiting the massive parallelism of Graphics Processing Units (GPUs) capable of performing several trillions floating-point operations per second, the objective is to compensate for the cost overhead caused by arithmetic with power series in multiple double precision. The application of Newton’s method for this problem requires the evaluation and differentiation of polynomials, followed by solving a blocked lower triangular linear system. Experimental results are obtained on NVIDIA GPUs, in particular the RTX 2080, RTX 4080, P100, V100, and A100.
Code generated by the CAMPARY software is used to obtain results in double double, quad double, and octo double precision. The programs in this study are self contained, available in a public github repository under the GPL-v3.0 License.
References
[1]
Abdelfattah A et al. A survey of numerical linear algebra methods utilizing mixed-precision arithmetic Int. J. High Perform. Comput. Appl. 2021 35 4 344-369
[2]
Agullo, E., Augonnet, C., Dongarra, J., Faverge, M.: QR factorization on a multicore node enhanced with multiple GPU accelerators. In: 2011 IEEE International Parallel and Distributed Processing Symposium, pp. 932–943. IEEE (2011)
[3]
Alexander JC and Yorke JA The homotopy continuation method: numerically implementable topological procedures Trans. Am. Math. Soc. 1978 242 271-284
[4]
Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods, Classics in Applied Mathematics, vol. 45. SIAM (2003)
[5]
Anderson, M., Ballard, G., Demmel, J., Kreutzer, K.: Communication-avoiding QR decomposition for GPUs. In: 2011 IEEE International Parallel and Distributed Processing Symposium, pp. 48–58. IEEE (2011)
[6]
Baboulin, M., Dongarra, J., Tomov, S.: Some issues in dense linear algebra for multicore and special purpose architectures. Technical Report UT-CS-08-200, University of Tennessee (2008)
[7]
Baker, Jr, G. A., Graves-Morris, P.: Padé Approximants. Cambridge University Press, Cambridge (1996)
[8]
Bischof C and Van Loan CF The WY representation for products of Householder matrices SIAM J. Sci. Stat. Comput. 1987 8 1 s1-s13
[9]
Bliss N and Verschelde J The method of Gauss-Newton to compute power series solutions of polynomial homotopies Linear Algebra Appl. 2018 542 569-588
[10]
Brezinski, C., Redivo Zaglia, M.: Extrapolation Methods. Studies in Computational Mathematics, vol. 2. North-Holland (1991)
[11]
Dronamraju A et al. Implications of Stahl’s theorems to holomorphic embedding part II: numerical convergence CSEE J. Power Energy Syst. 2021 7 4 773-784
[12]
Fabry E Sur les points singuliers d’une fonction donnée par son développement en série et l’impossibilité du prolongement analytique dans des cas très généraux Annales scientifiques de l’École Normale Supérieure 1896 13 367-399
[13]
Fornberg B Numerical differentiation of analytic functions ACM Trans. Math. Softw. 1981 7 4 512-526
[14]
Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2 edn. SIAM (2008)
[15]
Heller DH A survey of parallel algorithms in numerical linear algebra SIAM Rev. 1978 20 4 740-777
[16]
Henrici P An algorithm for analytic continuation SIAM J. Numer. Anal. 1966 3 1 67-78
[17]
Hida, Y., Li, X.S., Bailey, D.H.: Algorithms for quad-double precision floating point arithmetic. In: 15th IEEE Symposium on Computer Arithmetic (Arith-15 2001), pp. 155–162. IEEE Computer Society (2001)
[18]
Higham, N.J., Mary, T.: Mixed precision algorithms in numerical linear algebra. Acta Numerica 347–414 (2022)
[19]
Isupov K and Knyazkov V Multiple-precision matrix-vector multiplication on graphics processing units Program Syst. Theory Appl. 2020 11 3 62-84
[20]
Joldes M, Muller J-M, Popescu V, and Tucker W Greuel G-M, Koch T, Paule P, and Sommese A CAMPARY: Cuda multiple precision arithmetic library and applications Mathematical Software – ICMS 2016 2016 Cham Springer 232-240
[21]
Kelley CT Newton’s method in mixed precision SIAM Rev. 2022 64 1 191-211
[22]
Kerr, A., Campbell, D., Richards, M.: QR decomposition on GPUs. In: Kaeli, D., Leeser, M. (eds.) Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units (GPGPU 2009), pp. 71–78. ACM (2009)
[23]
Kirk, D.B., Hwu, W.W.: Programming Massively Parallel Processors. A Hands-on Approach. Morgan Kaufmann (2010)
[24]
Kouya, T.: Acceleration of complex matrix multiplication using arbitrary precision floating-point arithmetic, arXiv:2307.06072v1 (2023)
[25]
Kurzak J, Nath R, Du P, and Dongarra J Jónasson K An implementation of the tile QR factorization for a GPU and multiple CPUs Applied Parallel and Scientific Computing 2012 Heidelberg Springer 248-257
[26]
LLC: Multiprecision computing toolbox for MATLAB. www.advanpix.com
[27]
Lu, M., He, B., Luo, Q.: Supporting extended precision on graphics processors. In: Proceedings of the Sixth International Workshop on Data Management on New Hardware (DaMoN 2010), pp. 19–26 (2010)
[28]
Maho, N.: MPLAPACK version 2.0.1. user manual, arXiv:2109.13406v2 (2022)
[29]
Morgan, A.: Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, Classics in Applied Mathematics, vol. 57. SIAM (2009)
[30]
Muller JM et al. Handbook of Floating-Point Arithmetic 2018 2 Cham Springer
[31]
Nasri W and Mahjoub Z Optimal parallelization of a recursive algorithm for triangular matrix inversion on MIMD computers Parallel Comput. 2001 27 1767-1782
[32]
Sidi, A.: Practical Extrapolation Methods. Theory and Applications. Cambridge Monographs on Applied and Computational Mathematics, vol. 10. Cambridge University Press, Cambridge (2003)
[33]
Telen S, Van Barel M, and Verschelde J A robust numerical path tracking algorithm for polynomial homotopy continuation SIAM J. Sci. Comput. 2020 42 6 3610-A3637
[34]
Telen S, Van Barel M, and Verschelde J Boulier F, England M, Sadykov TM, and Vorozhtsov EV Robust numerical tracking of one path of a polynomial homotopy on parallel shared memory computers Computer Algebra in Scientific Computing 2020 Cham Springer 563-582
[35]
Tomov S, Dongarra J, and Baboulin M Towards dense linear algebra for hybrid GPU accelerated manycore systems Parallel Comput. 2010 36 5 232-240
[36]
Tomov, S., Nath, R., Ltaief, H., Dongarra, J.: Dense linear algebra solvers for multicore with GPU accelerators. In: The 2010 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1–8. IEEE (2010)
[37]
Trefethen, L.N.: Approximation Theory and Approximation Practice. SIAM (2013)
[38]
Trefethen LN Quantifying the ill-conditioning of analytic continuation BIT Numer. Math. 2020 60 4 901-915
[39]
Utsugiri, T., Kouya, T.: Acceleration of multiple precision matrix multiplication using Ozaki scheme, arXiv:2301.09960v2 (2023)
[40]
Verschelde J Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation ACM Trans. Math. Softw. 1999 25 2 251-276
[41]
Verschelde J Parallel software to offset the cost of higher precision ACM SIGAda Ada Lett. 2020 40 2 59-64
[42]
Verschelde, J.: Accelerated polynomial evaluation and differentiation at power series in multiple double precision. In: The 2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 740–749. IEEE (2021)
[43]
Verschelde, J.: Least squares on GPUs in multiple double precision. In: The 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 828–837. IEEE (2022)
[44]
Verschelde J and Viswanathan K Boulier F, England M, Sadykov TM, and Vorozhtsov EV Locating the closest singularity in a polynomial homotopy CASC 2022 2022 Cham Springer 333-352
[45]
Volkov, V., Demmel, J.: Benchmarking GPUs to tune dense linear algebra. In: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing. IEEE Press (2008). Article No. 31
[46]
Williams S, Waterman A, and Patterson D Roofline: an insightful visual performance model for multicore architectures Commun. ACM 2009 52 4 65-76
Index Terms
- GPU Accelerated Newton for Taylor Series Solutions of Polynomial Homotopies in Multiple Double Precision
Index terms have been assigned to the content through auto-classification.
Recommendations
Application of Taylor series in obtaining the orthogonal operational matrix
In this research first we explicitly obtain the relation between the coefficients of the Taylor series and Jacobi polynomial expansions. Then we present a new method for computing classical operational matrices (derivative, integral and product) for ...
On truncated Taylor series and the position of their spurious zeros
A truncated Taylor series, or a Taylor polynomial, which may appear when treating the motion of gravity water waves, is obtained by truncating an infinite Taylor series for a complex, analytical function. For such a polynomial the position of the ...
Tracking Many Solution Paths of a Polynomial Homotopy on a Graphics Processing Unit in Double Double and Quad Double Arithmetic
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and SystemsPolynomial systems occur in many areas of science and engineering. Unlike general nonlinear systems, the algebraic structure enablesto compute all solutions of a polynomial system. We describe our massively parallel predictor-corrector algorithmsto ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
406 pages
ISBN:978-3-031-69069-3
DOI:10.1007/978-3-031-69070-9
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 September 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024