×

Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications. (English) Zbl 1244.65062

The authors develop a fast and accurate method to evaluate matrix products error free. An error free splitting of floating point numbers with regards to number product is generalized to accurate dot products of vectors and error free matrix products. Floating point numbers, vectors and matrices are split into a sum of numbers, vectors and matrices, respectively, with a limited small number of nonzero leading bits and their products are expressed as non-evaluated sums of accurate floating point products until the matrix product stage is reached. There 3rd level BLAS are used to give fast and accurate matrix products. This method uses the more memory the deeper (shorter nonzero bit length) the splittings become.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A24 Matrix equations and identities
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] IEEE Standard for Floating-Point Arithmetic, Std 754–2008 (2008)
[2] Bailey, D.H.: A Fortran-90 based multiprecision system. ACM Trans. Math. Softw. 21(4), 379–387 (1995) · Zbl 0883.68017 · doi:10.1145/212066.212075
[3] Dekker, T.J.: A floating-point technique for extending the available precision. Numer. Math. 18(3), 224–242 (1971) · Zbl 0226.65034 · doi:10.1007/BF01397083
[4] Demmel, J., Hida, Y.: Accurate and efficient floating point summation. SIAM J. Sci. Comput. 25(4), 1214–1248 (2003) · Zbl 1061.65039 · doi:10.1137/S1064827502407627
[5] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[6] Goto, K., Geijn, R.V.D.: High-performance implementation of the level-3 BLAS. ACM Trans. Math. Softw. 35(1), Article no. 4 (2008) · Zbl 05458505 · doi:10.1145/1377603.1377607
[7] Li, X., Demmel, J., Bailey, D., Henry, G., Hida, Y., Iskandar, J., Kahan, W., Kang, S., Kapur, A., Martin, M., Thompson, B., Tung, T., Yoo, D.: Design, implementation and testing of extended and mixed precision BLAS. ACM Trans. Math. Softw. 28(2), 152–205 (2002) · Zbl 1070.65523 · doi:10.1145/567806.567808
[8] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM Publications, Philadelphia (2002) · Zbl 1011.65010
[9] Ogita, T., Rump, S.M., Oishi, S.: Accurate sum and dot product. SIAM J. Sci. Comput. 26, 1955–1988 (2005) · Zbl 1084.65041 · doi:10.1137/030601818
[10] Rump, S.M.: Ultimately fast accurate summation. SIAM J. Sci. Comput. 31(5), 3466–3502 (2009) · Zbl 1202.65033 · doi:10.1137/080738490
[11] Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part I: faithful rounding. SIAM J. Sci. Comput. 31(1), 189–224 (2008) · Zbl 1185.65082 · doi:10.1137/050645671
[12] Rump, S.M., Ogita, T., Oishi, S.: Accurate floating-point summation part II: sign, K-fold faithful and rounding to nearest. SIAM J. Sci. Comput. 31(2), 1269–1302 (2008) · Zbl 1190.65074 · doi:10.1137/07068816X
[13] Whaley, C.R., Petitet, A., Dongarra, J.J.: Automated empirical optimizations of software and the ATLAS project. Parallel Comput. 27, 3–35 (2001) · Zbl 0971.68033 · doi:10.1016/S0167-8191(00)00087-9
[14] The MPFR Library: http://www.mpfr.org/ . Accessed 7 Feb 2010
[15] exflib–extend precision floating-point arithmetic library: http://www-an.acs.i.kyoto-u.ac.jp/\(\sim\)fujiwara/exflib/exflib-index.html . Accessed 7 Feb 2010
[16] http://www.eecs.berkeley.edu/\(\sim\)yozo/ . Accessed 25 Dec 2009
[17] The NIST Sparse BLAS: http://math.nist.gov/spblas/original.html . Accessed 7 Feb 2010
[18] http://www.cise.ufl.edu/research/sparse/umfpack/ . Accessed 7 Feb 2010
[19] MATLAB Programming Version 7, The MathWorks (2005)
[20] Rump, S.M.: INTLAB–INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp. 77–104. Kluwer Academic, Dordrecht (1999) · Zbl 0949.65046
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.