On the estimation of numerical error bounds in linear algebra based on discrete stochastic arithmetic. (English) Zbl 1272.65040
A method to estimate error bounds of algorithms in linear algebra is proposed. The method is based on discrete stochastic arithmetic (DSA). In order to extend the DSA concept to algorithms in linear algebra, estimations of numerical error bounds are derived based on DSA. These estimations are applied to the linear algebra library LAPACK providing tighter error bounds compared to the error bounds of the library itself.
Reviewer: Jiří Rohn (Praha)
MSC:
| 65G50 | Roundoff error |
References:
| [1] | Abdelmalek, N., Round off error analysis for Gram-Schmidt method and solution of linear least squares problems, BIT Numerical Mathematics, 11, 345-367 (1971) · Zbl 0236.65031 |
| [2] | Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables (1964), Courier Dover Publications: Courier Dover Publications New York, USA · Zbl 0171.38503 |
| [3] | Arioli, M.; Laratta, A., Error analysis of an algorithm for solving an underdetermined linear system, Numerische Mathematik, 46, 255-268 (1985) · Zbl 0543.65012 |
| [4] | Arioli, M.; Laratta, A., Error analysis of algorithms for computing the projection of a point onto a linear manifold, Linear Algebra and Its Applications, 82, 1-26 (1986) · Zbl 0629.65042 |
| [5] | Z. Bai, J. Demmel, A. McKenney, On floating point errors in Cholesky, Technical report, Knoxville, TN, USA, 1989.; Z. Bai, J. Demmel, A. McKenney, On floating point errors in Cholesky, Technical report, Knoxville, TN, USA, 1989. |
| [6] | Å. Björck, Pivoting and stability in the augmented system method, in: Numerical Analysis, Proceedings of the 14th Dundee Conference, pp. 1-16.; Å. Björck, Pivoting and stability in the augmented system method, in: Numerical Analysis, Proceedings of the 14th Dundee Conference, pp. 1-16. · Zbl 0796.65056 |
| [7] | Buckland, S. T., Monte Carlo confidence intervals, Biometrics, 40, 811-817 (1984) · Zbl 0558.62040 |
| [8] | J.M. Chesneaux, Etude theorique et implementation en ada de la methode CESTAC, Ph.D. thesis, Universite Pierre et Marie Curie, Paris, 1988.; J.M. Chesneaux, Etude theorique et implementation en ada de la methode CESTAC, Ph.D. thesis, Universite Pierre et Marie Curie, Paris, 1988. |
| [9] | Chesneaux, J. M., Study of the computing accuracy by using probabilistic approach, Contribution to Computer Arithmetic and Self Validating Numerical Methods, 19-30 (1990) · Zbl 0784.65037 |
| [10] | Chesneaux, J. M.; Vignes, J., On the robustness of the CESTAC method, C. R. Academy of Sciences, 307, 855-860 (1988) · Zbl 0657.65061 |
| [11] | Demmel, J.; Hida, Y.; Kahan, W.; Li, X. S.; Mukherjee, S.; Riedy, E. J., Error bounds from extra-precise iterative refinement, ACM Transactions on Mathematical Software, 32, 325-351 (2006) · Zbl 1365.65082 |
| [12] | Demmel, J. W.; Higham, N. J., Improved error bounds for underdetermined system solvers, SIAM Journal on Matrix Analysis and Applications, 14, 1-14 (1993) · Zbl 0770.65025 |
| [13] | A. Ghaneme, J.L. Lamotte, On the performance of a parallel implementation of the CESTAC method with self-validation on several parallel machines, in: 11th International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN2004), Fukuoka, Japan.; A. Ghaneme, J.L. Lamotte, On the performance of a parallel implementation of the CESTAC method with self-validation on several parallel machines, in: 11th International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN2004), Fukuoka, Japan. |
| [14] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, USA · Zbl 0865.65009 |
| [15] | Gray, R. M., Toeplitz and Circulant Matrices: A Review (2006), Now Publishers Inc. · Zbl 1115.15021 |
| [16] | Hager, W., Condition estimates, SIAM Journal on Scientific and Statistical Computing, 5, 311-316 (1984) · Zbl 0542.65023 |
| [17] | Higham, D. J.; Higham, N. J., Structured backward error and condition of generalized eigenvalue problems, SIAM Journal on Matrix Analysis and Applications, 20, 493-512 (1998) · Zbl 0935.65032 |
| [18] | Higham, N. J., Experience with a matrix norm estimator, SIAM Journal on Scientific and Statistical Computing, 11, 804-809 (1990) · Zbl 0752.65036 |
| [19] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1011.65010 |
| [20] | Higham, N. J.; Eprint, M.; Highamf, N. J., A survey of condition number estimation for triangular matrices, SIAM Review, 29, 575-596 (1987) · Zbl 0635.65049 |
| [21] | Hogg, R. V.; Craig, A., Introduction to Mathematical Statistics (1994), Prentice-Hall, pp. 181-182 |
| [22] | Hotelling, H., Some new methods in matrix calculation, The Annals of Mathematical Statistics, 14, 1-34 (1943) · Zbl 0061.27007 |
| [23] | Jezequel, F.; Chesneaux, J. M., CADNA: A library for estimating round-off error propagation, Computer Physics Communications, 178, 933-955 (2008) · Zbl 1196.65020 |
| [24] | F. Jezequel, J.L. Lamotte, Numerical validation of Slater integrals computation on GPU, in: 14th International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2010), Lyon, France.; F. Jezequel, J.L. Lamotte, Numerical validation of Slater integrals computation on GPU, in: 14th International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2010), Lyon, France. |
| [25] | J.L. Lamotte, Parallelization of the CESTAC method on shared memory and distributed memory computers, in: 10th International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN2002), Paris, France.; J.L. Lamotte, Parallelization of the CESTAC method on shared memory and distributed memory computers, in: 10th International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN2002), Paris, France. |
| [26] | W. Li, S. Simon, Numerical error analysis for statistical software on multi-core systems, in: Proceedings of Compstat ʼ2010, France, pp. 1287-1294.; W. Li, S. Simon, Numerical error analysis for statistical software on multi-core systems, in: Proceedings of Compstat ʼ2010, France, pp. 1287-1294. |
| [27] | Moler, C. B., Three research problems in numerical linear algebra, (Golub, G. H.; Oliger, J., Numerical Analysis. Numerical Analysis, Proceedings of Symposia in Applied Mathematics, vol. 22 (1978)), 1-18 · Zbl 0397.65021 |
| [28] | Montgomery, D. C.; Runger, G. C., Applied Statistics and Probability for Engineers (2002), John Wiley & Sons, Inc. |
| [29] | Nakata, M., The MPACK (MBLAS/MLAPACK): A multiple precision arithmetic version of BLAS and LAPACK, version 0.6.7 |
| [30] | Olver, F. W.J.; Wilkinson, J. H., A Posteriori Error Bounds for Gaussian Elimination, vol. 2 (1982) · Zbl 0527.65018 |
| [31] | Paige, C. C., An error analysis of a method for solving matrix equations, Mathematics of Computation, 27, 355-359 (1973) · Zbl 0282.65027 |
| [32] | H. Ren, On the error analysis and implementation of some eigenvalue decomposition and singular value decomposition algorithms, Technical Report UCB/CSD-96-904, EECS Department, University of California, Berkeley, 1996.; H. Ren, On the error analysis and implementation of some eigenvalue decomposition and singular value decomposition algorithms, Technical Report UCB/CSD-96-904, EECS Department, University of California, Berkeley, 1996. |
| [33] | Satterthwaite, F., Synthesis of variance, Psychometrika, 6, 309-316 (1941) · Zbl 0063.06742 |
| [34] | Stewart, G. W., On the perturbation of LU and Cholesky factors, IMA Journal of Numerical Analysis, 17, 1-6 (1997) · Zbl 0876.65016 |
| [35] | Sun, J. G., Componentwise perturbation bounds for some matrix decompositions, BIT Numerical Mathematics, 32, 702-714 (1992) · Zbl 0764.65016 |
| [36] | Sun, J. G., Rounding-error and perturbation bounds for the Cholesky and LDLT factorizations, Linear Algebra and Its Applications, 173, 77-97 (1992) · Zbl 0808.65018 |
| [37] | Sun, J. G., A note on backward perturbations for the Hermitian eigenvalue problem, BIT Numerical Mathematics, 35, 385-393 (1995) · Zbl 0841.65023 |
| [38] | Sun, J. G.; Sun, Z., Optimal backward perturbation bounds for underdetermined systems, SIAM Journal on Matrix Analysis and Applications, 18, 393-402 (1997) · Zbl 0876.15003 |
| [39] | Tao, P. D., Convergence of a subgradient method for computing the bound norm of matrices, Linear Algebra and Its Applications, 62, 163-182 (1984) · Zbl 0563.65029 |
| [40] | Turing, A., Rounding-off errors in matrix processes, Quarterly Journal of Mechanics and Applied Mathematics, 287-308 (1948) · Zbl 0033.28501 |
| [41] | Vignes, J., Review on stochastic approach to round-off error analysis and its applications, Mathematics and Computers in Simulation, 30, 481-491 (1988) · Zbl 0665.65044 |
| [42] | Vignes, J., Discrete stochastic arithmetic for validating results of numerical software, Numerical Algorithms, 37, 377-390 (2004) · Zbl 1074.65055 |
| [43] | J. Vignes, M. La Porte, Error analysis in computing, in: IFIP Congress, 1974, pp. 610-614.; J. Vignes, M. La Porte, Error analysis in computing, in: IFIP Congress, 1974, pp. 610-614. · Zbl 0295.65035 |
| [44] | Vignes, J., Zéro mathématique et zéro informatique, C. R. Acad. Sci. Paris Sér. I Math., 303, 997-1000 (1986) · Zbl 0624.68047 |
| [45] | Wilkinson, J. H., Error analysis of direct methods of matrix inversion, Journal of the ACM, 8, 281-330 (1961) · Zbl 0109.09005 |
| [46] | Wilkinson, J. H., Rounding Errors in Algebraic Processes (1994), Dover Publications, Inc. · Zbl 0868.65027 |
| [47] | Yuan, K. H.; Bentler, P. M., Two simple approximations to the distributions of quadratic forms, British Journal of Mathematical and Statistical Psychology, 63, 273-291 (2010) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
