Navigation

• Education
  • International programmes
  • Faculties
  • ECTS
  • Vision and policy
• Research
  • Research at KU Leuven
  • Support and funding
  • Industry and Society
  • Phd
  • Postdoc researcher
  • Output and impact
  • Networking
  • Vision and policy
• Admissions
  • How to apply
  • Scholarships
  • Degree seeking students
  • Non-degree seeking students
  • Doctoral students
  • Reseachers
  • Short term study visits
  • Prepare your stay
• Living in Leuven
  • Welcome activities
  • News and agenda
  • Student Services
  • Housing
  • Insurance
  • Sports and culture
  • Student organisations
• About KU Leuven
  • Mission statement
  • Facts and figures
  • International networks
  • Development Cooperation
  • Academic Calendar
  • Alumni
  • Fundraising
  • Services and support
  • Boards and councils
  • News and press
  • Jobs

TW 577

Abstract

The QR-algorithm is a renowned method for computing all eigenvalues of an arbitrary matrix. A preliminary unitary similarity transformation to Hessenberg form is indispensible for keeping the computational complexity of the QR-algorithm applied on the resulting Hessenberg matrix under control. The unitary factor Q in the QR-factorization of the Hessenberg matrix H = QR is composed of n − 1 rotations ordered from top to bottom. The ordering of these n − 1 rotations is precisely determined by the Hessenberg structure and uniquely specifies the unitary matrix Q. In this article it will be shown that for any matrix there exists a unitary similar matrix A = QR, where any type of ordering of the n − 1 rotations in the factorization of the unitary matrix Q are admitted. Classic examples of rotational factorizations of a unitary matrix Q are sequences from bottom to top (lower unitary Hessenberg) or for instance the CMV -decomposition of a pentadiagonal unitary matrix. An important consequence of these alternative formats is the loss of the Hessenberg structure. The resulting matrix is, however, still representable by the same order of parameters. A constructive procedure to compute the unitary similar matrix in factored form A = QR, as well as proof of unicity of the reduction are given. Based on the factorization of the unitary matrix Q in n − 1 rotations an iterative procedure for computing the eigenvalues is presented. The QR-like iteration takes advantage of the specific ordering of the rotations and based on the unicity of the rotational factorization an implicit version is designed. The computational cost of the implicit version is again comparable to the cost of the QR-algorithm for Hessenberg matrices. A first numerical experiment investigates to Ritz-value convergence behavior of some variants of the unitary similarity trans- formation. A second test investigates the speed of convergence and the accuracy of the new iterative method for some variants of rotational factorizations.