Backward error analysis of the Lanczos bidiagonalization with reorthogonalization

doi:10.1016/j.cam.2024.116414

	Backward error analysis of the Lanczos bidiagonalization with reorthogonalization
	Li, Haibo 1,2; Tan, Guangming 2; Zhao, Tong 2
	2025-05-01
发表期刊	JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
ISSN	0377-0427
卷号	460 页码:17
摘要	The -step Lanczos bidiagonalization reduces a matrix E R x into a bidiagonal form E R ( +1)x while generating two orthonormal matrices +1 E R x( +1) and +1 E R x( +1) . However, any practical implementation of the algorithm suffers from loss of orthogonality of +1 and +1 due to the presence of rounding errors, and several reorthogonalization strategies are proposed to maintain some level of orthogonality. In this paper, we make a backward error analysis of the Lanczos bidiagonalization with reorthogonalization (LBRO) by writing various reorthogonalization strategies in a general form. Our results show that the computed by the -step LBRO of with starting vector is the exact one generated by the -step Lanczos bidiagonalization of + with starting vector + (denoted by LB( + , + )), where the 2-norm of perturbation vector/matrix and depend on the roundoff unit and orthogonality levels of +1 and +1. The results also show that the 2-norm of +1 - +1 and +1 - +1 are controlled by the orthogonality levels of +1 and +1, respectively, where +1 and +1are the two orthonormal matrices generated by the -step LB( + , +) in exact arithmetic. Thus, the -step LBRO is mixed forward-backward stable as long as the orthogonality of +1 and +1 are good enough. We use this result to investigate the backward stability of LBRO based SVD computation algorithm and LSQR algorithm. Numerical experiments confirm our results.
关键词	Lanczos bidiagonalization Rounding error Reorthogonalization Backward error analysis Householder transformation Singular value decomposition LSQR
DOI	10.1016/j.cam.2024.116414
收录类别	SCI
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:001372675600001
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/41113
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Haibo
作者单位	1.Huawei Technol, Comp Syst Optimizat Lab, Beijing 100094, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Li, Haibo,Tan, Guangming,Zhao, Tong. Backward error analysis of the Lanczos bidiagonalization with reorthogonalization[J]. JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS,2025,460:17.
APA	Li, Haibo,Tan, Guangming,&Zhao, Tong.(2025).Backward error analysis of the Lanczos bidiagonalization with reorthogonalization.JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS,460,17.
MLA	Li, Haibo,et al."Backward error analysis of the Lanczos bidiagonalization with reorthogonalization".JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 460(2025):17.