×

Backward error analysis of the AllReduce algorithm for Householder QR decomposition. (English) Zbl 1260.65036

The authors give an error analysis of the AllReduce algorithm for the Householder QR decomposition of tall and skinny matrices. They derive bounds on the backward error and the deviation from orthogonality of the computed Q factor. It is shown that the bounds are smaller than in other QR algorithms and they decrease as the level of recursion increases. Computational results are given in support of the theoretical results. Thus the authors have shown that the all reduce algorithm can be used reliably in a parallel environment.

MSC:

65F25 Orthogonalization in numerical linear algebra
65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai Z., Day D., Ye Q.: ABLE: an adaptive Block Lanczos method for non-Hermitian eigenvalue problems. SIAM J. Matrix Anal. Appl. 20, 1060–1082 (1999) · Zbl 0932.65045 · doi:10.1137/S0895479897317806
[2] Bai, Z., Demmel, J.W., Dongarra, J.J., Ruhe, A., van der Vorst, H. (eds.): Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia (2000) · Zbl 0965.65058
[3] Bischof C., Lang B.: Algorithm 807: the SBR Toolbox–software for successive band reduction. ACM Trans. Math. Softw. 26(4), 602–616 (2000) · Zbl 1365.65104 · doi:10.1145/365723.365736
[4] Demmel, J.W., Grigori, L., Hoemmen, M.F., Langou, J.: Communication-optimal parallel and sequential QR and LU factorizations. LAPACK Working Notes, No. 204 (2008) · Zbl 1241.65028
[5] Freund R.W., Malhotra M.: A Block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides. Linear Algebra Appl. 254, 119–157 (1997) · Zbl 0873.65021 · doi:10.1016/S0024-3795(96)00529-0
[6] Golub G.H., Van Loan C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[7] Higham N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (1996) · Zbl 0847.65010
[8] Langou, J.: AllReduce Algorithms: Application to Householder QR Factorization. Presentation at Preconditioning 2007, Toulouse, France, July 9–12, 2007. http://www.precond07.enseeiht.fr/Talks/langou/langou.pdf
[9] Mori, D., Yamamoto, Y., Zhang, S.-L.: Performance and accuracy of the AllReduce algorithm for the householder QR factorization (in Japanese). IPSJ SIG Technical Report, 2008-HPC-117, pp. 25–29 (2008)
[10] Murakami, H.: A multi-staged Block algorithm of householder-type orthogonal transformation for distributed parallel processing (in Japanese). IPSJ SIG Technical Report, 2008-HPC-117, pp. 19–24 (2008)
[11] O’Leary D.P.: The Block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29, 293–322 (1980) · Zbl 0426.65011 · doi:10.1016/0024-3795(80)90247-5
[12] Toledo S., Rabani E.: Very large electronic structure calculations using an out-of-core filter diagonalization method. J. Comput. Phys. 180(1), 256–269 (2002) · Zbl 0995.81549 · doi:10.1006/jcph.2002.7090
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.