Applications of Mathematics, Vol. 66, No. 2, pp. 269-285, 2021


Verified numerical computations for large-scale linear systems

Katsuhisa Ozaki, Takeshi Terao, Takeshi Ogita, Takahiro Katagiri

Received November 25, 2019.   Published online January 15, 2021.

Abstract:  This paper concerns accuracy-guaranteed numerical computations for linear systems. Due to the rapid progress of supercomputers, the treatable problem size is getting larger. The larger the problem size, the more rounding errors in floating-point arithmetic can accumulate in general, and the more inaccurate numerical solutions are obtained. Therefore, it is important to verify the accuracy of numerical solutions. Verified numerical computations are used to produce error bounds on numerical solutions. We report the implementation of a verification method for large-scale linear systems and some numerical results using the RIKEN K computer and the Fujitsu PRIMEHPC FX100, which show the high performance of the verified numerical computations.
Keywords:  verified numerical computation; floating-point arithmetic; high-performance computing; large-scale linear system
Classification MSC:  65G20, 65G50, 65Y05
DOI:  10.21136/AM.2021.0318-19

PDF available at:  Springer   Institute of Mathematics CAS

References:
[1] L. S. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, R. C. Whaley: ScaLAPACK - Scalable Linear Algebra PACKage. Available at http://www.netlib.org/scalapack/ (2019). SW 00830
[2] A. M. Castaldo, R. C. Whaley, A. T. Chronopoulos: Reducing floating point error in dot product using the superblock family of algorithms. SIAM J. Sci. Comput. 31 (2008), 1156-1174. DOI 10.1137/070679946 | MR 2466152 | Zbl 1189.65076
[3] FUJITSU: FUJITSU Supercomputer PRIMEHPC FX100. Available at https://www.fujitsu.com/global/products/computing/servers/supercomputer/primehpc-fx100/ (2020).
[4] N. J. Higham: Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (2002). DOI 10.1137/1.9780898718027 | MR 1927606 | Zbl 1011.65010
[5] N. J. Higham, T. Mary: A new approach to probabilistic rounding error analysis. SIAM J. Sci. Comput. 41 (2019), A2815-A2835. DOI 10.1137/18M1226312 | MR 4002728 | Zbl 07123205
[6] IEEE Computer Society: IEEE Standard for Floating-Point Arithmetic: IEEE Std 754-2008. IEEE, NewYork (2008). DOI 10.1109/IEEESTD.2008.4610935
[7] C.-P. Jeannerod, S. M. Rump: Improved error bounds for inner products in floating-point arithmetic. SIAM J. Matrix Anal. Appl. 34 (2013), 338-344. DOI 10.1137/120894488 | MR 3038111 | Zbl 1279.65052
[8] M. Kolberg, G. Bohlender, L. G. Fernandes: An efficient approach to solve very large dense linear systems with verified computing on clusters. Numer. Linear Algebra Appl. 22 (2015), 299-316. DOI 10.1002/nla.1950 | MR 3313260 | Zbl 1363.65088
[9] X. Li, J. Demmel, D. Bailey, Y. Hida, J. Iskandar, A. Kapur, M. Martin, B. Thompson, T. Tung, D. Yoo: XBLAS - Extra Precise Basic Linear Algebra Subroutines. Available at https://www.netlib.org/xblas/ (2008). SW 11672
[10] A. Minamihata, K. Sekine, T. Ogita, S. M. Rump, S. Oishi: Improved error bounds for linear systems with $H$-matrices. Nonlinear Theory Appl., IEICE 6 (2015), 377-382. DOI 10.1587/nolta.6.377
[11] Y. Morikura, K. Ozaki, S. Oishi: Verification methods for linear systems using ufp estimation with rounding-to-nearest. Nonlinear Theory Appl., IEICE 4 (2013), 12-22. DOI 10.1587/nolta.4.12
[12] M. Nakata: The MPACK: Multiple Precision Arithmetic BLAS (MBLAS) and LAPACK (MLAPACK). Available at http://mplapack.sourceforge.net/ (2011). SW 12855
[13] A. Neumaier: A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations. Reliab. Comput. 5 (1999), 131-136. DOI 10.1023/A:1009997221089 | MR 1702530 | Zbl 0936.65055
[14] T. Ogita, S. Oishi: Fast verification for large-scale systems of linear equations. IPSJ Trans. 46 (2005), 10-18. (In Japanese.)
[15] T. Ogita, S. Oishi, Y. Ushiro: Computation of sharp rigorous componentwise error bounds for the approximate solutions of systems of linear equations. Reliab. Comput. 9 (2003), 229-239. DOI 10.1023/A:1024655416554 | MR 1984561 | Zbl 1029.65045
[16] T. Ogita, S. M. Rump, S. Oishi: Accurate sum and dot product. SIAM J. Sci. Comput. 26 (2005), 1955-1988. DOI 10.1137/030601818 | MR 2196584 | Zbl 1084.65041
[17] T. Ogita, S. M. Rump, S. Oishi: Verified Solution of Linear Systems Without Directed Rounding: Technical Report No. 2005-04. Advanced Research Institute for Science and Engineering, Waseda University, Tokyo (2005).
[18] S. Oishi, S. M. Rump: Fast verification of solutions of matrix equations. Numer. Math. 90 (2002), 755-773. DOI 10.1007/s002110100310 | MR 1888837 | Zbl 0999.65015
[19] K. Ozaki, T. Ogita: Generation of linear systems with specified solutions for numerical experiments. Reliab. Comput. 25 (2017), 148-167. MR 3693809
[20] K. Ozaki, T. Ogita, S. Miyajima, S. Oishi, S. M. Rump: A method of obtaining verified solutions for linear systems suited for Java. J. Comput. Appl. Math. 199 (2007), 337-344. DOI 10.1016/j.cam.2005.08.034 | MR 2269516 | Zbl 1108.65019
[21] K. Ozaki, T. Ogita, S. Oishi: An algorithm for automatically selecting a suitable verification method for linear systems. Numer. Algorithms 56 (2011), 363-382. DOI 10.1007/s11075-010-9389-6 | MR 2774120 | Zbl 1209.65051
[22] A. Petitet: PBLAS - Parallel Basic Linear Algebra Subprograms. Available at http://www.netlib.org/scalapack/pblas_qref.html. SW 19577
[23] RIKEN Center for Computational Science: What is K? Available at https://www.r-ccs.riken.jp/en/k-computer/about/ (2019).
[24] S. M. Rump: Kleine Fehlerschranken bei Matrixproblemen: PhD Thesis. Universität Karlsruhe, Karlsruhe, 1980. (In German.) DOI 10.15480/882.321 | Zbl 0437.65036
[25] S. M. Rump: Accurate solution of dense linear systems I: Algorithms in rounding to nearest. J. Comput. Appl. Math. 242 (2013), 157-184. DOI 10.1016/j.cam.2012.10.010 | MR 2997436 | Zbl 1255.65084
[26] S. M. Rump: Accurate solution of dense linear systems II: Algorithms using directed rounding. J. Comput. Appl. Math. 242 (2013), 185-212. DOI 10.1016/j.cam.2012.09.024 | MR 2997437 | Zbl 1260.65034
[27] R. D. Skeel: Iterative refinement implies numerical stability for Gaussian elimination. Math. Comput. 35 (1980), 817-832. DOI 10.2307/2006197 | MR 0572859 | Zbl 0441.65027
[28] V. Strassen: Gaussian elimination is not optimal. Numer. Math. 13 (1969), 354-356. DOI 10.1007/BF02165411 | MR 0248973 | Zbl 0185.40101
[29] N. Yamanaka, T. Ogita, S. M. Rump, S. Oishi: A parallel algorithm for accurate dot product. Parallel Comput. 34 (2008), 392-410. DOI 10.1016/j.parco.2008.02.002  | MR 2428885

Affiliations:   Katsuhisa Ozaki (corresponding author), Takeshi Terao, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama-shi, Saitama 337-8570, Japan, e-mail: ozaki@sic.shibaura-it.ac.jp, nb17105@shibaura-it.ac.jp; Takeshi Ogita, Tokyo Woman's Christian University, 2-6-1 Zempukuji, Suginami-ku, Tokyo 167-8585, Japan, e-mail: ogita@lab.twcu.ac.jp; Takahiro Katagiri, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, Aichi 464-8601, Japan, e-mail: katagiri@cc.nagoya-u.ac.jp


 
PDF available at: