A sharper loss-of-orthogonality bound for MGS-HA

At least 8 years old · documented by

Let AA be the symmetric positive-definite matrix defining the non-standard inner product, let ZZ be the input matrix with mm rows, let nn be the number of columns, and let u{\bf u} denote the unit roundoff. Write Q^\widehat Q for the computed AA-orthogonal factor and let κ(⋅)\kappa(\cdot) denote the condition number. The loss of AA-orthogonality is measured by ∥Q^TAQ^−In∥\|\widehat Q^{\rm T}A\widehat Q-I_n\|. MGS-HA orthogonality-bound conjecture. The loss of AA-orthogonality of MGS-HA can be bounded as

∥Q^TAQ^−In∥≤O(m3/2)u(κ(A)+κ(A1/2Z))1−O(m3/2)u(κ(A)+κ(A1/2Z))≈O(m3/2)u(κ(A)+κ(A1/2Z)).\|\widehat Q^{\rm T} A \widehat{Q} - I_n \| \leq \frac{\mathcal{O}(m^{3/2}) {\bf u} \left( \kappa(A) + \kappa(A^{1/2}Z) \right)}{1-\mathcal{O}(m^{3/2}) {\bf u} \left( \kappa(A) + \kappa(A^{1/2}Z)\right)} \approx \mathcal{O}(m^{3/2}) {\bf u} \left( \kappa(A) + \kappa(A^{1/2}Z) \right).

The quantity on the right is motivated by numerical experiments, where it describes the observed loss of AA-orthogonality for MGS-HA more sharply than the earlier bound, although the paper states that it has no theoretical background yet.

References

Primary source

Akira Imakura and Yusaku Yamamoto, “Efficient implementations of the modified Gram-Schmidt orthogonalization with a non-standard inner product”, arXiv:1703.10440 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.