Theoretical results needed to design implicit -algorithms for semiseparable matrices

In a first section of this chapter we will investigate ``a
type'' of -factorization of Hessenberg-like plus diagonal
matrices. We say a type of because we will show in the next section,
that the -factorization is not necessarily unique. The
factorization we propose is based on the paper [178]. In the
factorization presented in this paper, the orthogonal matrix is
constructed as a product of Givens transformations, with
the dimension of the matrix. Suppose we have a Hessenberg-like plus
diagonal matrix . It will be shown that a first sequence of
Givens transformations will transform the matrix
into an upper triangular matrix . These Givens
transformations will transform the matrix into a Hessenberg
matrix. Our resulting matrix
will therefore be
Hessenberg. The second sequence of Givens transformations will reduce
the Hessenberg matrix to upper triangular form.

The concept of irreducibility is an important topic for the construction of implicit -algorithms. We define what is meant with an unreduced Hessenberg-like matrix. It will be shown later on that this unreducedness demand plays a very important role in the implicit -theorem and in the construction of the implicit -algorithm. Moreover, using the definition of an unreduced Hessenberg-like matrix, it is rather easy to prove the essential uniqueness of the -factorization for Hessenberg-like matrices. With essentially unique we mean that two -factorizations only differ for the sign of the elements.

In the third section we will investigate the structure of a Hessenberg-like matrix after having applied a step of the -algorithm with shift. First we show that the choice of the -factorization is essential to obtain again a Hessenberg-like matrix after a -step. This fact is illustrated by an example in the Hessenberg and in the Hessenberg-like case. Using the -factorization for Hessenberg-like matrices as explained in Section 7.1, we will prove the following theorems: The structure of a Hessenberg-like matrix is maintained after a step of without shift; The weakly lower triangular structure of a matrix is maintained after a -step with shift; The Hessenberg-like structure is maintained after a -step with shift; The diagonal in a Hessenberg-like plus diagonal matrix is maintained after applying a step of with shift. Note that for these theorems, no assumptions concerning the singularity of the matrices are made.

In the second section we defined unreduced Hessenberg-like matrices and in Section 7.5 we will prove an implicit -theorem for Hessenberg-like matrices. This implicit -theorem strongly depends on the unreducedness of the Hessenberg-like matrix. Therefore we will provide in Section 7.4 an easy way of transforming a Hessenberg-like matrix to unreduced form. The algorithm provided performs in fact a special -step without shift on the Hessenberg-like matrix. This results in an algorithm, revealing immediately the singularities of the corresponding Hessenberg-like matrix.

In Section 7.5 of this chapter we will provide an implicit -theorem for Hessenberg-like matrices. The theorem is quite similar to the theorem for Hessenberg matrices. It will prove to be very powerful in the next chapter when we start with the construction of the different -algorithms.

- The -factorization of Hessenberg-like plus diagonal matrices
- Unreduced Hessenberg-like matrices
- A -step maintains the Hessenberg-like structure
- The reduction to unreduced Hessenberg-like form
- The implicit -theorem
- Conclusions