An efficient implementation of the block Gram--Schmidt method

Abstract

The block Gram--Schmidt method computes the QR factorisation rapidly, but this is dependent on block size $m$. We endeavor to determine the optimal $m$ automatically during one execution. Our algorithm determines $m$ through observing the relationship between computation time and complexity. Numerical experiments show that our proposed algorithms compute approximately twice as fast as the block Gram--Schmidt method for some block sizes, and is a viable option for computing the QR factorisation in a more stable and rapid manner. References

• Bjorck, A., Numerical Methods for Least Squares Problems, SIAM, (1996).
• Elden, L., and Park, H., Block Downdating of Least Squares Solutions, SIAM J. Matrix Anal. Appl., 15:1018--1034 (1994). doi:10.1137/S089547989223691X
• Runger, G., and Schwind, M., Comparison of Different Parallel Modified Gram--Schmidt Algorithms, Euro-Par 2005, LNCS 3648:826--836 (2005). doi:10.1007/11549468_90
• Katagiri, T., Performance Evaluation of Parallel Gram--Schmidt Re-orthogonalization Methods, VECPAR 2002, LNCS 2565:302--314 (2003). doi:10.1007/3-540-36569-9_19
• Matrix Market, Mathematical and Computational Sciences Division, Information Technology Laboratory of the National Institute of Standards and Technology, USA. http://math.nist.gov/MatrixMarket/
• Matsuo, Y. and Nodera, T., The Optimal Block-Size for the Block Gram--Schmidt Orthogonalization, J. Sci. Tech, 49:348--354 (2011).
• Moriya, K. and Nodera, T., The DEFLATED-GMRES(m, k) Method with Switching the Restart Frequency Dynamically, Numer. Linear Alg. Appl., 7:569--584 (2000). doi:10.1002/1099-1506(200010/12)7:7/8<569::AID-NLA213>3.0.CO;2-8
• Moriya, K. and Nodera, T., Usage of the convergence test of the residual norm in the Tsuno--Nodera version of the GMRES algorithm, ANZIAM J., 49:293--308 (2007). doi:10.1017/S1446181100012852
• Liu, Q., Modified Gram--Schmidt-based Methods for Block Downdating the Cholesky Factorization, J. Comput. Appl. Math., 235:1897--1905 (2011). doi:10.1016/j.cam.2010.09.003
• Saad, Y. and Schultz, M. H., GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems, SIAM J. Sci. Stat. Comput., 7:856--869 (1986). doi:10.1137/0907058
• Shiroishi, J. and Nodera, T., A GMRES($m$) Method with Two Stage Deflated Preconditioners, ANZIAM J., 52:C222--C236 (2011). http://journal.austms.org.au/ojs/index.php/ANZIAMJ/article/view/3984
• Leon, S. J., Bjorck, A., and Gander, W., Gram--Schmidt Orthogonalization: 100 years and more, Numer. Linear Algebra Appl., 20:492--532 (2013). doi:10.1002/nla.1839
• Stewart, G. W., Block Gram--Schmidt Orthogonalization, SIAM J. Sci. Comput., 31:761--775 (2008). doi:10.1137/070682563
• Vanderstraeten, D., An Accurate Parallel Block Gram-Schmidt Algorithm without Reorthogonalization, Numer. Lin. Alg. Appl., 7:219--236 (2000). doi:10.1002/1099-1506(200005)7:4<219::AID-NLA196>3.0.CO;2-L
• Yokozawa, T., Takahashi, T., Boku, T. and Sato, M., Efficient Parallel Implementation of Classical Gram-Schmidt Orthogonalization Using Matrix Multiplication, (in Japanese) Information Processing Society of Japan (IPSJ), Computing System, 1:61--72 (2008).