Perturbation Analysis for Preconditioned Normal Equations in Mixed Precision
This work addresses the problem of improving computational efficiency and accuracy in solving linear systems for researchers and practitioners in numerical linear algebra, though it is incremental as it builds on existing preconditioning techniques.
The paper analyzes the conditioning of various preconditioned normal equations using randomized preconditioners computed in lower precision, showing that conditioning depends mildly on preconditioner quality but significantly on the least squares residual size. It demonstrates that such preconditioners can achieve solution accuracy comparable to Matlab's mldivide, are efficient, and suitable for GPU implementations, with an automatic precision selection method based on fast condition number estimation.
For real matrices of full column-rank, we analyze the conditioning of several types of normal equations that are preconditioned by a randomized preconditioner computed in lower precision. These include symmetrically preconditioned normal equations, half-preconditioned normal equations, seminormal equations and not-normal equations. Our perturbation bounds are realistic and informative, and suggest that the conditioning depends only mildly on the quality of the preconditioner; however, it does depend on the size of the least squares residual -- even if the normal equations do not originate from a least squares problem. We illustrate that a randomized preconditioner can deliver a solution accuracy comparable to that of Matlab's mldivide command, is efficient in practice, and well-suited to GPU implementations. For the computation of the preconditioner, we propose an automatic selection of the precision, based on a fast condition number estimation in lower precision.