... Matrices

The research of the first two authors, was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), CoE EF/05/006 Optimization in Engineering (OPTEC), by the Fund for Scientific Research-Flanders (Belgium), G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), G.0423.05 (RAM: Rational modelling: optimal conditioning and stable algorithms), and by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office, Belgian Network DYSCO (Dynamical Systems, Control, and Optimization). The first author has a grant as ``Postdoctoraal Onderzoeker''from the Fund for Scientific Research-Flanders (Belgium). The work of the third author was partially supported by MIUR, grant number 2004015437. The scientific responsibility rests with the authors.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...$satisfied$

With $Z(i:j,k:l)$ the submatrix with rows from $i$ up to $j$ and $k$ up to $l$ is meant.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... representation

There is of course no loss in generality, as this representation covers the complete set.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... matrix.

Givens transformations can equal the identity, without loss of generalization.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... transformations

Combining two Givens transformations leads to $2n-1$ transformations.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....

The performance of $k$ steps of the $QR$-algorithm without shift do not dramatically increase the complexity of the multishift w.r.t. single shift strategy, also in the single shift strategy a $QR$-step without shift is needed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... procedure.

In some sense the initialization is not needed, see a remark later on.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...MATLAB

MATLABR2006a, is a registred trademark of the Mathworks inc.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.