Mixed Precision Rayleigh Quotient Iteration for Total Least Squares Problems

With the recent emergence of mixed precision hardware, there has been a renewed interest in its use for solving numerical linear algebra problems fast and accurately. The solution of total least squares problems, i.e., solving $\min_{E,f} \| [E, f]\|_F$ subject to $(A+E)x=b+f$, arises in numerous application areas. The solution of this problem requires finding the smallest singular value and corresponding right singular vector of $[A,b]$, which is challenging when $A$ is large and sparse. An efficient algorithm for this case due to Bj\"{o}rck et al., called RQI-PCGTLS, is based on Rayleigh quotient iteration coupled with the conjugate gradient method preconditioned via Cholesky factors. We develop a mixed precision variant of this algorithm, called RQI-PCGTLS-MP, in which up to three different precisions can be used. We assume that the lowest precision is used in the computation of the preconditioner, and give theoretical constraints on how this precision must be chosen to ensure stability. In contrast to the standard least squares case, for total least squares problems, the constraint on this precision depends not only on the matrix $A$, but also on the right-hand side $b$. We perform a number of numerical experiments on model total least squares problems used in the literature, which demonstrate that our algorithm can attain the same accuracy as RQI-PCGTLS albeit with a potential convergence delay due to the use of low precision. Performance modeling shows that the mixed precision approach can achieve up to a $4\times$ speedup depending on the size of the matrix and the number of Rayleigh quotient iterations performed.