CENTER FOR COMPUTATIONAL MATHEMATICS COLLOQUIUM

                  UNIVERSITY OF COLORADO AT DENVER



TITLE:   On High Relative Accuracy in Matrix Singular Value and 
         Symmetric Eigenvalue Problems -- from Perturbation Theory to 
         Accurate Algorithms
 

SPEAKER: Zlatko Drmac
         
DATE:    Monday, December 15, 1997  


PLACE:   Mathematics Conference Room 626 
         UCD Building, 1250 14th St., Denver


TIME:    noon (Refreshments served at 11:45 am) 



ABSTRACT

We present a unified approach to accurate floating--point computation 
of the singular value decomposition (SVD) of products and quotients of 
matrices and related spectral decompositions of positive definite matrix 
pencils. The list of problems of interest includes:
(i)   the generalized SVD of two full rank matrices;
(ii)  the product induced SVD of matrix pairs and triplets;
(iii) the positive definite generalized eigenvalue problems
      $ H x = \lambda M x $, $ H M x = \lambda x $
      ($H$, $M$ symmetric positive definite);
(iv) the $(H,K)$--SVD and $(H^{-1},K)$--SVD of general matrices with
     applications to weighted least squares and canonical correlations. 
We develop perturbation analysis and new algorithms which are capable 
of achieving optimal theoretical accuracy. For example, in the symmetric 
positive definite $n\times n$ eigenvalue problems $Hx=\lambda Mx$ and  
$HMx=\lambda x$, each eigenvalue $\lambda$ is computed with high relative 
accuracy. More precisely, the relative error $|\delta\lambda|/\lambda$ 
is, up to a factor of $n$, of the order 

$\varepsilon \{  \min_{D\in{\cal D}}\kappa_2(D H D) +  
                 \min_{D\in{\cal D}}\kappa_2(D M D) \}$, 

where ${\cal D}$ denotes diagonal nonsingular matrices, $\kappa_2(\cdot)$ 
is the spectral condition number and $\varepsilon$ is the roundoff unit. 
Furthermore, the backward errors $\delta H$, $\delta M$ are element--wise 
small: 
$|\delta H_{ij}|/\sqrt{H_{ii}H_{jj}}$ and $|\delta M_{ij}|/\sqrt{M_{ii}M_{jj}}$ 
are $O(n\varepsilon)$ for all $i$, $j$.