The Hari-Zimmermann Algorithm for the Computation of the Generalized SVD

Sanja Singer (The University of Zagreb)

Frank Adams 1,

In the talk we describe how to modify the two-sided Hari-Zimmermann
algorithm for computation of the generalized eigenvalues of a matrix pair
(A;B), where B is positive de nite, to an implicit algorithm that computes
the generalized singular values of a pair (F;G). In addition, we present
blocking and parallelization techniques for speedup of the computation.

For triangular matrix pairs of a moderate size, numerical tests show that
the double precision sequential pointwise algorithm is several times faster
than the LAPACK DTGSJA algorithm, while the accuracy is slightly better,
especially for small generalized singular values.

Cache-aware algorithms, implemented either as the block-oriented, or as
the full block algorithm, are several times faster than the pointwise algo-
rithm. The algorithm is almost perfectly parallelizable, so parallel shared
memory versions of the algorithm are perfectly scalable, and their speedup
almost solely depends on the number of cores used.

We also show the backward stability of the implicit Hari-Zimmermann
algorithm for the GSVD, by using a new columnwise technique. This bound
provides a bound for the relative accuracy of the computed generalized sin-
gular values.

This is a joint work with Vedran Novakovic and Sasa Singer.

Import this event to your Outlook calendar
▲ Up to the top