GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR III: APPROXIMATE RITZ VALUES VIA SHIFTED INVERSE ITERATION

Jess Banks; Jorge Garza-Vargas; Nikhil Srivastava

doi:10.1137/23M1557556

GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR III: APPROXIMATE RITZ VALUES VIA SHIFTED INVERSE ITERATION

Jess Banks
, Jorge Garza-Vargas
, Nikhil Srivastava

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix (Equation presented) up to backward error delta||M|| in (Equation presented) floating point operations using O(log²(n/delta)) bits of precision. While the O(n⁴) complexity is prohibitive for large matrices, the algorithm is simple and may be useful for computing the eigenvalues of small matrices using a controlled amount of precision, in particular, for computing Ritz values in shifted QR algorithms as in [BGVS22b].

Original language	English (US)
Pages (from-to)	1212-1246
Number of pages	35
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	46
Issue number	2
DOIs	https://doi.org/10.1137/23M1557556
State	Published - 2025
Externally published	Yes

All Science Journal Classification (ASJC) codes

Analysis

Keywords

Ritz values
inverse iteration
nonnormality
numerical linear algebra
shifted QR

Access to Document

10.1137/23M1557556

Cite this

@article{c1f969b4acbe4685a4b754e2cb44676f,

title = "GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR III: APPROXIMATE RITZ VALUES VIA SHIFTED INVERSE ITERATION",

abstract = "We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix (Equation presented) up to backward error delta||M|| in (Equation presented) floating point operations using O(log2(n/delta)) bits of precision. While the O(n4) complexity is prohibitive for large matrices, the algorithm is simple and may be useful for computing the eigenvalues of small matrices using a controlled amount of precision, in particular, for computing Ritz values in shifted QR algorithms as in [BGVS22b].",

keywords = "Ritz values, inverse iteration, nonnormality, numerical linear algebra, shifted QR",

author = "Jess Banks and Jorge Garza-Vargas and Nikhil Srivastava",

note = "Publisher Copyright: {\textcopyright} 2025 Society for Industrial and Applied Mathematics.",

year = "2025",

doi = "10.1137/23M1557556",

language = "English (US)",

volume = "46",

pages = "1212--1246",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR III

T2 - APPROXIMATE RITZ VALUES VIA SHIFTED INVERSE ITERATION

AU - Banks, Jess

AU - Garza-Vargas, Jorge

AU - Srivastava, Nikhil

PY - 2025

Y1 - 2025

N2 - We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix (Equation presented) up to backward error delta||M|| in (Equation presented) floating point operations using O(log2(n/delta)) bits of precision. While the O(n4) complexity is prohibitive for large matrices, the algorithm is simple and may be useful for computing the eigenvalues of small matrices using a controlled amount of precision, in particular, for computing Ritz values in shifted QR algorithms as in [BGVS22b].

AB - We give a self-contained randomized algorithm based on shifted inverse iteration which provably computes the eigenvalues of an arbitrary matrix (Equation presented) up to backward error delta||M|| in (Equation presented) floating point operations using O(log2(n/delta)) bits of precision. While the O(n4) complexity is prohibitive for large matrices, the algorithm is simple and may be useful for computing the eigenvalues of small matrices using a controlled amount of precision, in particular, for computing Ritz values in shifted QR algorithms as in [BGVS22b].

KW - Ritz values

KW - inverse iteration

KW - nonnormality

KW - numerical linear algebra

KW - shifted QR

UR - https://www.scopus.com/pages/publications/105004056570

UR - https://www.scopus.com/pages/publications/105004056570#tab=citedBy

U2 - 10.1137/23M1557556

DO - 10.1137/23M1557556

M3 - Article

AN - SCOPUS:105004056570

SN - 0895-4798

VL - 46

SP - 1212

EP - 1246

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -

GLOBAL CONVERGENCE OF HESSENBERG SHIFTED QR III: APPROXIMATE RITZ VALUES VIA SHIFTED INVERSE ITERATION

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this