| Title:
|
Verified numerical computations for large-scale linear systems (English) |
| Author:
|
Ozaki, Katsuhisa |
| Author:
|
Terao, Takeshi |
| Author:
|
Ogita, Takeshi |
| Author:
|
Katagiri, Takahiro |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
66 |
| Issue:
|
2 |
| Year:
|
2021 |
| Pages:
|
269-285 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
verified numerical computation |
| Keyword:
|
floating-point arithmetic |
| Keyword:
|
high-performance computing |
| Keyword:
|
large-scale linear system |
| MSC:
|
65G20 |
| MSC:
|
65G50 |
| MSC:
|
65Y05 |
| idZBL:
|
07332698 |
| idMR:
|
MR4226459 |
| DOI:
|
10.21136/AM.2021.0318-19 |
| . |
| Date available:
|
2021-03-05T10:38:37Z |
| Last updated:
|
2023-05-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148723 |
| . |
| Reference:
|
[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). |
| Reference:
|
[2] Castaldo, A. M., Whaley, R. C., Chronopoulos, A. T.: Reducing floating point error in dot product using the superblock family of algorithms.SIAM J. Sci. Comput. 31 (2008), 1156-1174. Zbl 1189.65076, MR 2466152, 10.1137/070679946 |
| Reference:
|
[3] FUJITSU: FUJITSU Supercomputer PRIMEHPC FX100.Available at {\def{ }\let \relax\brokenlink{https://www.fujitsu.com/global/products/computing/servers/}{supercomputer/primehpc-fx100/}} (2020). |
| Reference:
|
[4] Higham, N. J.: Accuracy and Stability of Numerical Algorithms.Society for Industrial and Applied Mathematics, Philadelphia (2002). Zbl 1011.65010, MR 1927606, 10.1137/1.9780898718027 |
| Reference:
|
[5] Higham, N. J., Mary, T.: A new approach to probabilistic rounding error analysis.SIAM J. Sci. Comput. 41 (2019), A2815--A2835. Zbl 07123205, MR 4002728, 10.1137/18M1226312 |
| Reference:
|
[6] Society, IEEE Computer: IEEE Standard for Floating-Point Arithmetic: IEEE Std 754-2008.IEEE, NewYork (2008). 10.1109/IEEESTD.2008.4610935 |
| Reference:
|
[7] Jeannerod, C.-P., Rump, S. M.: Improved error bounds for inner products in floating-point arithmetic.SIAM J. Matrix Anal. Appl. 34 (2013), 338-344. Zbl 1279.65052, MR 3038111, 10.1137/120894488 |
| Reference:
|
[8] Kolberg, M., Bohlender, G., Fernandes, L. G.: An efficient approach to solve very large dense linear systems with verified computing on clusters.Numer. Linear Algebra Appl. 22 (2015), 299-316. Zbl 1363.65088, MR 3313260, 10.1002/nla.1950 |
| Reference:
|
[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). |
| Reference:
|
[10] Minamihata, A., Sekine, K., Ogita, T., Rump, S. M., Oishi, S.: Improved error bounds for linear systems with $H$-matrices.Nonlinear Theory Appl., IEICE 6 (2015), 377-382. 10.1587/nolta.6.377 |
| Reference:
|
[11] Morikura, Y., Ozaki, K., Oishi, S.: Verification methods for linear systems using ufp estimation with rounding-to-nearest.Nonlinear Theory Appl., IEICE 4 (2013), 12-22. 10.1587/nolta.4.12 |
| Reference:
|
[12] Nakata, M.: The MPACK: Multiple Precision Arithmetic BLAS (MBLAS) and LAPACK (MLAPACK).Available at http://mplapack.sourceforge.net/ (2011). |
| Reference:
|
[13] Neumaier, A.: A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations.Reliab. Comput. 5 (1999), 131-136. Zbl 0936.65055, MR 1702530, 10.1023/A:1009997221089 |
| Reference:
|
[14] Ogita, T., Oishi, S.: Fast verification for large-scale systems of linear equations.IPSJ Trans. 46 (2005), 10-18 Japanese. |
| Reference:
|
[15] Ogita, T., Oishi, S., Ushiro, Y.: Computation of sharp rigorous componentwise error bounds for the approximate solutions of systems of linear equations.Reliab. Comput. 9 (2003), 229-239. Zbl 1029.65045, MR 1984561, 10.1023/A:1024655416554 |
| Reference:
|
[16] Ogita, T., Rump, S. M., Oishi, S.: Accurate sum and dot product.SIAM J. Sci. Comput. 26 (2005), 1955-1988. Zbl 1084.65041, MR 2196584, 10.1137/030601818 |
| Reference:
|
[17] Ogita, T., Rump, S. M., Oishi, S.: Verified Solution of Linear Systems Without Directed Rounding: Technical Report No. 2005-04.Advanced Research Institute for Science and Engineering, Waseda University, Tokyo (2005). |
| Reference:
|
[18] Oishi, S., Rump, S. M.: Fast verification of solutions of matrix equations.Numer. Math. 90 (2002), 755-773. Zbl 0999.65015, MR 1888837, 10.1007/s002110100310 |
| Reference:
|
[19] Ozaki, K., Ogita, T.: Generation of linear systems with specified solutions for numerical experiments.Reliab. Comput. 25 (2017), 148-167. MR 3693809 |
| Reference:
|
[20] Ozaki, K., Ogita, T., Miyajima, S., Oishi, S., Rump, S. M.: A method of obtaining verified solutions for linear systems suited for Java.J. Comput. Appl. Math. 199 (2007), 337-344. Zbl 1108.65019, MR 2269516, 10.1016/j.cam.2005.08.034 |
| Reference:
|
[21] Ozaki, K., Ogita, T., Oishi, S.: An algorithm for automatically selecting a suitable verification method for linear systems.Numer. Algorithms 56 (2011), 363-382. Zbl 1209.65051, MR 2774120, 10.1007/s11075-010-9389-6 |
| Reference:
|
[22] Petitet, A.: PBLAS - Parallel Basic Linear Algebra Subprograms.Available at \brokenlink{http://www.netlib.org/scalapack/{pblas_qref.html}}. |
| Reference:
|
[23] Science, RIKEN Center for Computational: What is K?.Available at https://www.r-ccs.riken.jp/en/k-computer/about/ (2019). |
| Reference:
|
[24] Rump, S. M.: Kleine Fehlerschranken bei Matrixproblemen: PhD Thesis.Universität Karlsruhe, Karlsruhe (1980), German. Zbl 0437.65036, 10.15480/882.321 |
| Reference:
|
[25] Rump, S. M.: Accurate solution of dense linear systems I: Algorithms in rounding to nearest.J. Comput. Appl. Math. 242 (2013), 157-184. Zbl 1255.65084, MR 2997436, 10.1016/j.cam.2012.10.010 |
| Reference:
|
[26] Rump, S. M.: Accurate solution of dense linear systems II: Algorithms using directed rounding.J. Comput. Appl. Math. 242 (2013), 185-212. Zbl 1260.65034, MR 2997437, 10.1016/j.cam.2012.09.024 |
| Reference:
|
[27] Skeel, R. D.: Iterative refinement implies numerical stability for Gaussian elimination.Math. Comput. 35 (1980), 817-832. Zbl 0441.65027, MR 0572859, 10.2307/2006197 |
| Reference:
|
[28] Strassen, V.: Gaussian elimination is not optimal.Numer. Math. 13 (1969), 354-356. Zbl 0185.40101, MR 0248973, 10.1007/BF02165411 |
| Reference:
|
[29] Yamanaka, N., Ogita, T., Rump, S. M., Oishi, S.: A parallel algorithm for accurate dot product.Parallel Comput. 34 (2008), 392-410 \99999DOI99999 10.1016/j.parco.2008.02.002 \goodbreak. MR 2428885, 10.1016/j.parco.2008.02.002 |
| . |
