Design and Implementation of Compensated Gram-Schmidt Algorithm

Due to the cumulative effect of rounding errors, the Gram-Schmidt orthogonalization algorithm and its variants often exhibit numerical instability phenomena. Therefore, we analyze the data dependencies of the Modified Gram-Schmidt algorithm (MGS), and propose the compensated MGS algorithm (CompMGS) based on the idea of error-free transformation (EFT) technology and compensated algorithms. The theoretical analysis demonstrates that our algorithm has
$\mathcal{O}(u)$
loss of orthogonality(in double working precision,
$u=10^{-16}$
) with the relaxed conditions
$(\kappa_{2}(A) < 1^{-}0^{16})$
. A range of numerical experiments illustrate that CompMGS has similar effects to the double-double precision Modified Gram-Schmidt orthog-onalization algorithm (DDMGS) and is more accurate than the algorithms proposed in [1] and [2], which verifies the correctness of the theoretical analysis and proves the accuracy of our algorithm. While satisfying the same loss of orthogonality, the CompMGS is faster than DDMGS on both ARM and Intel processors by about 1.5 times and 2.3 times on average respectively, showing the high efficiency of our algorithm.