jeudi 5 juin 15h00, à Calais.
Intervenant:
-----------
David S. Watkins
Department of Mathematics
Washington State University
Pullman, WA, 99164-3113, USA
Titre: «Fast, Stable, Computation of the Eigenvalues of Unitary-plus-rank-one Matrices »
------
Résumé:
-------
This is joint work with Jared L. Aurentz, Thomas Mach, and Raf Vandebril
Resume : We consider upper Hessenberg unitary-plus-rank-one matrices,
that is, matrices of the form $A = \tilde{U} + \tilde{x}\tilde{y}^{T}$,
where $\tilde{U}$ is unitary, and $A$ is upper Hessenberg. This includes
the class of Frobenius companion matrices, so methods for this type of
matrix can be applied to the problem of finding the zeros of a polynomial.
The unitary-plus-rank-one structure is preserved by any method that
performs unitary similarity transformations, including Francis's
implicitly-shifted $QR$ algorithm. We present a new implementation of
Francis's algorithm that acts on a data structure that stores the matrix
in $O(n)$ space and performs each iteration in $O(n)$ time.
We store $A$ in the form $A = QR$, where $Q$ is unitary and $R$ is upper
triangular. In this sense our method is similar to one proposed by
Chandrasekaran, Gu, Xia, and Zhu (Oper.\ Theory Adv.\ Appl.\ 179 (2007),
pp. 111--143), but our method stores $R$ differently. Since $Q$ is a
unitary upper-Hessenberg matrix, it can be stored as a product $Q =
Q_{1}Q_{2}\cdots Q_{n-1}$, where each $Q_j$ is a Givens-like unitary
tranformation that acts only on rows $j$ and $j+1$. We call these $Q_j$
\emph{core transformations}. Both our algorithm and that of Chandrasekaran
et.\ al.\ use this representation of $Q$. For $R$, they use a
quasiseparable generator representation. Our representation scheme
factors $R$ in the form $$R = C_{n-1}\cdots C_{1}(B_{1}\cdots B_{n-1} +
e_1 y^T),$$
where the $C_j$ and $B_j$ are unitary core transformations. This ispossible because $R$ is also unitary-plus-rank-one.
Performing Francis iterations on an upper Hessenberg matrix $A$ of the
form $$A = QR= Q_{1}\cdots Q_{n-1}C_{n-1}\cdots C_{1}(B_{1}\cdots B_{n-1} +
e_1 y^T)$$ is largely a matter of manipulating core transformations. We
will show how to do this.
We will compare our algorithm to other fast (and slow) algorithms in
terms of speed and accuracy.