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 507

Raf Vandebril, Marc Van Barel and Nicola Mastronardi
A new iteration for computing the eigenvalues of semiseparable (plus diagonal) matrices

Abstract

This paper proposes a new type of iteration based on a structured rank factorization for computing eigenvalues of semiseparable and semiseparable plus diagonal matrices. Also the case of higher order semiseparability ranks is included. More precisely, instead of the traditional QR-iteration, a QH-iteration will be used. The QH-factorization is characterized by a unitary matrix Q and a Hessenberg-like matrix (often called lower semiseparable matrix) H, having the lower triangular part of semiseparable form. The Q factor of this factorization determines the similarity transformation of the QH-method.

It will be shown that this iteration is extremely useful for computing the eigenvalues of structured rank matrices. Whereas the traditional QR-method applied onto semiseparable (plus diagonal) and Hessenberg-like matrices uses similarity transformations involving 2p(n-1) Givens transformations (where p denotes the semiseparability rank), this iteration only needs p(n-1) iterations, which is comparable to the tridiagonal and Hessenberg situation in case of p = 1. It will also be shown that this method can in some sense be interpreted as an extension of the traditional QR-method for Hessenberg matrices, i.e., the traditional case also fits into this framework.

Based on results in another paper, it will be shown that this iteration also exhibits an extra type of convergence behavior, w.r.t. the traditional QR-method.