English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Rapid convergence of the shifted QR algorithm on symmetric matrices was shownmore than fifty years ago. Since then, despite significant interest and itspractical relevance, an understanding of the dynamics and convergenceproperties of the shifted QR algorithm on nonsymmetric matrices has remainedelusive.  We introduce a new family of shifting strategies for the Hessenberg shiftedQR algorithm. We prove that when the input is a diagonalizable Hessenbergmatrix $H$ of bounded eigenvector condition number $\kappa_V(H)$ -- defined asthe minimum condition number of $V$ over all diagonalizations $VDV^{-1}$ of $H$-- then the shifted QR algorithm with a certain strategy from our family isguaranteed to converge rapidly to a Hessenberg matrix with a zero subdiagonalentry, in exact arithmetic. Our convergence result is nonasymptotic, showingthat the geometric mean of certain subdiagonal entries of $H$ decays by a fixedconstant in every $QR$ iteration. The arithmetic cost of implementing eachiteration of our strategy scales roughly logarithmically in the eigenvectorcondition number $\kappa_V(H)$, which is a measure of the nonnormality of $H$.  The key ideas in the design and analysis of our strategy are: (1) We are ableto precisely characterize when a certain shifting strategy based on Ritz valuesstagnates. We use this information to design certain ``exceptional shifts''which are guaranteed to escape stagnation whenever it occurs. (2) We use higherdegree shifts (of degree roughly $\log \kappa_V(H)$) to dampen transienteffects due to nonnormality, allowing us to treat nonnormal matrices in amanner similar to normal matrices.

Global Convergence of Hessenberg Shifted QR I: Exact Arithmetic