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 435

Raf Vandebril, Nicola Mastronardi, Marc Van Barel
Solving linear systems with a Levinson-like solver

Abstract

In this paper we will present a general framework for solving linear systems of equations. The solver is based on the Levinson-idea for solving Toeplitz systems of equations.

We will consider a general class of matrices, defined as the class of (p₁,p,sub>2)-Levinson conform matrices. This class incorporates for instance semiseparable, band, companion, arrowhead and many other matrices. For this class of we will derive a solver of complexity O(p₁,p₂).

The system solver is written inductively, and uses in every step k, the solutions of so called k-th order Yule-Walker-like equation. The first obtained algorithm has complexity O(p₁,p₂). Based, however on the specific structure of the simple (p₁,p₂)-Levinson conform matrices, we will be able to further reduce the complexity of the presented method, and get an order O(p₁,p₂) algorithm.

Different examples of matrices are given admitting this algorithm. Examples are presented for: general dense matrices, upper triangular matrices, higher order generator semiseparable matrices, quasiseparable matrices, Givens-Vector representable semiseparable matrices, band matrices, companion matrices, confederate matrices, arrowhead matrices, fellow and many more.

Finally, the relation between this method and an upper triangular factorization of the original matrix are given and also details concerning possible look ahead methods are presented.