\documentclass[landscape,12pt]{article}
\newcommand{\bmat}{\left[ \begin{array}}
\newcommand{\emat}{\end{array} \right]}
\newcommand{\bff}{\bf }

\pagestyle{empty}
% \newcommand{\ignore}[1]{}
\newcommand{\IGNORE}[1]{}
\newcommand{\ignore}[1]{#1}
\newcommand{\bits}{{\rm \# bits}}
\newcommand{\size}{{\rm size}}
\newcommand{\diag}{{\rm diag}}
% \newcommand{\det}{{\rm det}}
\usepackage{color}
\usepackage{graphics}
% \usepackage{amstex}
% \usepackage{lscape}
% \input{psfig.sty}
\newcommand{\slide}[1]
{
\newpage
\begin{center}
#1
\end{center}
\hrule
\bigskip
}


\textwidth9.5in
\oddsidemargin-0.5in
\evensidemargin-0.5in
\textheight7in
\topmargin-1in

\newcommand{\cond}{{\rm cond}}
\newcommand{\tb}{\textcolor{blue}}
\newcommand{\tr}{\textcolor{red}}
% \newcommand{\det}{{\rm det}}
\begin{document}


\def\boxtext#1{%
\vbox{%
\hrule
\hbox{\strut \vrule{} #1 \vrule}%
\hrule
}%
}


\boldmath

\LARGE\bf


%-----------------------------------------------------------
% Page 1

%\begin{landscape}


\phantom{X}
\vskip0.5in

\bigskip

\bigskip

\begin{center}
{\huge\bf  Accurate Computations with
\\
\bigskip
 Totally Positive Matrices}

\end{center}

\bigskip
\bigskip

\hrule
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip

{\Large \bf
\begin{center}
{\LARGE\bf  Plamen Koev}
\\
 Massachusetts Institute of Technology

\vspace*{1in}

\sf

{\Large\bf  Joint work with James Demmel (Berkeley), Froil\'an Dopico (Madrid)}

\vspace*{.3in}
{\large\bf  Supported by NSF}
\vspace*{.5in}


{\rm \large \bf  LAPACK Seminar, University of California, Berkeley,
September 21, 2005}
\end{center}
}



\def\boxtext#1{%
\vbox{%
\hrule
\hbox{\strut \vrule{} #1 \vrule}%
\hrule
}%
}




%-----------------------------------------------------------
\slide{What is Total Positivity? }


\vskip3in

\centerline{\tr{$A$ is TP $\Longleftrightarrow$ All minors $>0$}}



%-----------------------------------------------------------
% Page 1


\newpage
\begin{center}
{\LARGE \bff  Applications Abound }
\end{center}
\hrule
\bigskip

{\LARGE \bff


\begin{itemize}

\item Vibrations of mechanical systems (Gantmacher, Krein)
\item Corner cutting algorithms (Cutting corners from polytopes)
\item Electrical Impedance Tomography (Y.\ Chen)
\item Stochastic analysis

\vskip 1in

\item Books by Karlin, Gantmacher--Krein, Gasca--Micchelli
\item Motivated by work of Whitney, Bj\"orck, Pereyra,
Higham, Gasca, Pe\~na, Kahan, C.\ Johnson, Fallat,...
\end{itemize}

}



% ----------------------------------------
% Page 3

\newpage
\begin{center}
{\LARGE \bf  Examples }
\end{center}
\hrule
\bigskip

{\huge \bff


\vskip1in




$$
\begin{array}{ccc}
\quad
\bmat{ccccc}
1 & 1 & 1 & 1        \\
1 & 2 & 2^2 & 2^3  \\
1 & 3 & 3^2 & 3^3 \\
1 & 4 & 4^2 & 4^3
\emat
\quad
&
\quad
\bmat{cccc}
1         & ^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4  \\
^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5  \\
^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6  \\
^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6 & ^1\!/\!_7
\emat
\quad
&
\quad
\bmat{cccc}
1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4  \\
1 & 3 & 6 & 10  \\
1 & 4 & 10 & 20
\emat
\quad
\\
\mbox{Vandermonde} & \mbox{Hilbert} & \mbox{Pascal}\\
& \mbox{(Cauchy)} &
\end{array}
$$

\vskip1.5in
\centerline{\LARGE\bf Notoriously illconditioned $\Rightarrow$ conventional algorithms
fail}

}




% ----------------------------------------
% Page 2

\newpage
\begin{center}
{\LARGE \bff  Computed Eigenvalues of Pascal(40)}
\end{center}
\hrule
\bigskip

{\LARGE \bff
\centerline{\resizebox{8.5in}{!}{
\includegraphics*{pascal40.pdf}
}}

}



% ---------------------------------------------------------

\slide{ Properties of TP matrices }

\begin{itemize}

\item Eigenvalues are real, distinct, positive
\item TP preserved by
\begin{itemize}
\item multiplication
\item Schur complementation
\item Taking and inverse and resigning ($|A^{-1}|$)
\item Taking a {\em converse}
\item Taking a submatrix
\item $R$ in $A=QR$ is TP
\item One step of QR iteration, if $A$ is symmetric
\end{itemize}

% -------------------------------------------------------------------------

\slide{GOALS}

\item Accurate computations within the class of TP matrices
\item In particular:
\begin{itemize}

\item $\lambda_i,\sigma_i$, entries of $A^{-1}$, LDU, to high \tb{relative} accuracy


$$
|\hat\lambda_i - \lambda_i|\le O(\epsilon)|\textcolor{blue}{\lambda_i}|
\hskip2cm
|\hat\sigma_i - \sigma_i|\le O(\epsilon)\textcolor{blue}{\sigma_i}
$$


\item Contrast: \tr{Conventional abs error bounds:}
$$
|\hat\lambda_i - \lambda_i|\le
O(\epsilon)\textcolor{red}{\frac{||A||}{|y^*x|}} \hskip2cm
|\hat\sigma_i - \sigma_i|\le O(\epsilon)\textcolor{red}{\sigma_1}
$$

\end{itemize}

\item More complicated computations, e.g.,
$$
\lambda_i(\mbox{SchurComplement(Hilbert$\times$Pascal)})
$$
\end{itemize}


%-----------------------------------------------------------
\slide{ Main Result }

\vskip2.7in

\centerline{\tr{Virtually all TP linear algebra possible accurately}}
\vskip1in






% ------------------------------------------------------------------

\slide{First Issue: Proper Representation}

\begin{itemize}


\item Matrix entries are a \tr{bad} choice of parameters:


\begin{itemize}
\item $\epsilon$ perturbation in $(2,2)$ entry of the TP matrix

\begin{eqnarray*}
\bmat{cc} 1 & 1\\ 1 & 1+\tb{\varepsilon}
\emat & = \bmat{cc}1 \\1& 1\emat \cdot\bmat{cc}1\\&\tb{\varepsilon}\emat
\cdot\bmat{cc}1& 1\\ & 1\emat
\\
\\
\downarrow \mbox{~~~~} \\
\\
 \bmat{cc} 1 & 1\\ 1 & 1+\tr{2\varepsilon}
\emat &=\bmat{cc}1 \\1& 1\emat \cdot\bmat{cc}1\\&\tr{2\varepsilon}\emat
\cdot\bmat{cc}1& 1\\ & 1\emat
\end{eqnarray*}

\item Leads to 100\% relative perturbation in $\lambda_{\min}$

\end{itemize}

\item How do we know if a matrix is TP?

Clue: Factorizations: If Cholesky is real $\Rightarrow$ s.p.d.

\item If Neville elimination succeeds with
positive pivots $\Rightarrow$ TP

\end{itemize}



%
%-----------------------------------------------------------
% Page 12
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 1}
\end{center}
\hrule
\bigskip

{\LARGE \bf


Neville Elimination -- eliminate using adjacent rows

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1  & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
\tr 1 & \tr 3 & \tr 9  & \tr {27}   \\
\tr 1 & \tr 4  & \tr {16} & \tr {64}
\emat
=$

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&& 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27   \\
1 & 4 & 16 & 64
\emat
$


}




%
%-----------------------------------------------------------
% Page 13
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination - 2}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
\tr 1 & \tr 2 & \tr 4  & \tr 8    \\
\tr 1 & \tr 3 & \tr 9  & \tr{27}   \\
0 & 1  & 7  & 37
\emat
$



}



%
%-----------------------------------------------------------
% Page 14
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 3}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr 1& 1\\
&&& 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
1 & 2 & 4 & 8    \\
0 & \tr 1 & \tr 5  & \tr {19} \\
0 & \tr 1  & \tr 7  & \tr {37}
\emat
$

}

%
%-----------------------------------------------------------
% Page 15
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 4}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
\tr 1  & \tr 1 & \tr 1  & \tr 1    \\
\tr 1 & \tr 2 & \tr 4 & \tr 8    \\
0 & 1 & 5  & {19} \\
0 &  0   &  2  & 18
\emat
$
}

%
%-----------------------------------------------------------
% Page 16
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 5}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination -- We can choose the pattern

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
\tr 1& 1 \\
&& 1\\
&&& 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
0 & \tr 1 & \tr 3 & \tr 7    \\
0 & \tr 1 & \tr 5  & \tr {19} \\
0 &  0   &  2  & 18
\emat
$
}

%
%-----------------------------------------------------------
% Page 17
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 6}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
1& 1 \\
&\tr 1& 1\\
&&& 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
0 & 1 & 3 & 7    \\
0 & 0  & \tr 2  & \tr {12} \\
0 &  0   &  \tr 2  & \tr {18}
\emat
$
}

%
%-----------------------------------------------------------
% Page 18
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 7}
\end{center}
\hrule
\bigskip

{\LARGE \bf
Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
1& 1 \\
& 1& 1\\
&&\tr 1 & 1
\emat
\bmat{cccc}
1  & 1 & 1  & 1    \\
0 & 1 & 3 & 7    \\
0 & 0  & 2  & {12} \\
0 &  0   &  0   & \tr 6
\emat
$
}

%
%-----------------------------------------------------------
% Page 19
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 8}
\end{center}
\hrule
\bigskip

{\LARGE \bf

Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
1& 1 \\
& 1& 1\\
&& 1 & 1
\emat
\bmat{cccc}
1 \\
& 1 \\
& & 2 \\
&&  & 6
\emat
\bmat{cccc}
1 & 1 & 1  & 1    \\
0 & 1 & 3 & 7    \\
0 & 0  & 1  & 6 \\
0 & 0   &  0   & 1
\emat
$
}


%
%-----------------------------------------------------------
% Page 20
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 9}
\end{center}
\hrule
\bigskip

{\LARGE \bf

Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 & 1 & 1  & 1    \\
1 & 2 & 4  & 8    \\
1 & 3 & 9  & 27 \\
1 & 4 & 16 & 64
\emat
=
$


\bigskip
\bigskip

\noindent
$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&1& 1\\
&&1& 1
\emat
\bmat{cccc}
1 \\
1& 1 \\
& 1& 1\\
&& 1 & 1
\emat
\bmat{cccc}
1 \\
& 1 \\
& & 2 \\
&&  & 6
\emat
\bmat{cccc}
1 & 1 & 1  & 0    \\
0 & 1 & 3 & 4    \\
0 & 0  & 1  & 5 \\
0 & 0   &  0   & 1
\emat
\bmat{cccc}
1 \\
& 1 \\
& & 1 & 1\\
&&  & 1
\emat
$
}


%
%-----------------------------------------------------------
% Page 21
\newpage
\begin{center}
{\LARGE \bf Total Nonnegativity and Neville Elimination -- 10}
\end{center}
\hrule
\bigskip

{\LARGE \bf

Neville Elimination

\bigskip
\bigskip

\noindent
$
\bmat{cccc}
\tr 1 & \tr 1 & \tr 1  & \tr 1    \\
\tr 1 & \tr 2 & \tr 4  & \tr 8    \\
\tr 1 & \tr 3 & \tr 9  & \tr {27}   \\
\tr 1 & \tr 4 & \tr {16} & \tr{ 64}
\emat
=
$


\bigskip
\bigskip

\noindent
$
\underbrace{
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr 1& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
\tr 1& 1 \\
& \tr 1& 1\\
&& \tr 1 & 1
\emat
}_{\mbox{\Huge $L$}}
\underbrace{
\bmat{cccc}
\tr 1 \\
& \tr 1 \\
& & \tr 2 \\
&&  & \tr 6
\emat
}_{\mbox{\Huge $D$}}
\underbrace{
\bmat{cccc}
1 & \tr 1 \\
& 1 & \tr 2\\
& & 1 & \tr 3\\
&&  & 1
\emat
\bmat{cccc}
1 \\
& 1 & \tr 1\\
& & 1 & \tr 2\\
&&  & 1
\emat\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr 1\\
&&  & 1
\emat
}_{\mbox{\Huge $U$}}
$

\bigskip
\bigskip
\bigskip
\bigskip

Thm: $A$ is TP $\Leftrightarrow$ \tr{Red entries} $>0$

}

% ------------------------------------------------------------

\slide{ Pascal matrices are all of a sudden just ones }

\bigskip

{ \Large
\noindent
{\LARGE PASCAL(4)}
$
= \bmat{cccc}
\tr 1 & \tr 1 & \tr 1  & \tr 1 \\
\tr 1 & \tr 2 & \tr 3  & \tr 4 \\
\tr 1 & \tr 3 & \tr 6  & \tr {10} \\
\tr 1 & \tr 4 & \tr {10} & \tr {20}
\emat
$




\bigskip
\bigskip


\noindent$
=
\underbrace{
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr 1& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
\tr 1& 1 \\
& \tr 1& 1\\
&& \tr 1 & 1
\emat
}_{\mbox{\Huge $L$}}
\underbrace{
\bmat{cccc}
\tr 1 \\
& \tr 1 \\
& & \tr 1 \\
&&  & \tr 1
\emat
}_{\mbox{\Huge $D$}}
\underbrace{
\bmat{cccc}
1 & \tr 1 \\
& 1 & \tr 1\\
& & 1 & \tr 1\\
&&  & 1
\emat
\bmat{cccc}
1 \\
& 1 & \tr 1\\
& & 1 & \tr 1\\
&&  & 1
\emat\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr 1\\
&&  & 1
\emat
}_{\mbox{\Huge $U$}}
$

}




%-----------------------------------------------------------
\slide{ Any TP $=$ Product of Nonnegative Bidiagonals }

\bigskip

{\large
\noindent
$
\bmat{cccc}
\tr{a_{11}} & \tr {a_{12}} & \tr {a_{13}}  & \tr {a_{14}} \\
\tr{a_{21}} & \tr {a_{22}} & \tr {a_{23}} & \tr {a_{24}} \\
\tr{a_{31}} & \tr {a_{32}} & \tr {a_{33}}  & \tr {a_{34}} \\
\tr{a_{41}} & \tr {a_{42}} & \tr {a_{43}}  & \tr {a_{44}}
\emat
$

\bigskip
\bigskip


\noindent$=
\underbrace{
\bmat{cccc}
1 \\
& 1 \\
&&\!\! 1\\
&&\!\!\tr {l_{41}}& 1
\emat
\!\!
\bmat{cccc}
1 \\
&\!\! 1 \\
&\!\!\tr{l_{31}} &\!\! 1\\
&\!\!&\!\!\tr{l_{42}}& 1
\emat
\!\!
\bmat{cccc}
1 \\
\tr{l_{21}}& \!\!1 \\
&\!\! \tr{l_{32}}& \!\!1\\
&\!\!& \!\!\tr{l_{43}} &\!\! 1
\emat
\!\!
}_{\mbox{\Huge $L$}}
\underbrace{
\bmat{cccc}
\tr {d_1} \\
&\!\! \tr {d_2} \\
&\!\! &\!\! \tr {d_3} \\
&\!\! &\!\!  &\!\! \tr {d_4}
\emat
}_{\mbox{\Huge $D$}}
\!\!
\underbrace{
\bmat{cccc}
1 & \!\!\tr {u_{12}} \\
& 1 & \!\!\tr {u_{23}}\\
& & 1 & \!\!\tr {u_{34}}\\
&&  & 1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 &\!\! \tr {u_{13}}\\
&   &\!\! 1 & \!\!\tr {u_{24}}\\
&   &\!\!   & \!\! 1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 \\
& & 1 & \!\!\tr {u_{14}}\\
&&  & 1
\emat
}_{\mbox{\Huge $U$}}
$
}

\bigskip
\bigskip


\begin{itemize}

\item Theorem: $A$ is TP $\Longleftrightarrow$ $\tr{l_{ij}, d_i, u_{ij}}> 0$

\item This representation reveals the TP structure

\item Thm (K.): ${\cal BD}(A)$
determines $\lambda_i, \sigma_i, A^{-1}_{ij},\ldots $ accurately


\item \tr{Red entries} $=
\frac{\det A(1:k,i-k+2:i+1)}{\det A(1:k-1,i-k+2:i)}\cdot
\frac{\det A(1:k-1,i-k+1:i-1)}{\det A(1:k,i-k+1:i)}
$

$\Rightarrow$ Formulas

\end{itemize}





% ----------------------------------------
% Page 2a

\newpage
\begin{center}
{\LARGE \bff  Accurate ${\cal BD}$ of Vandermonde and Cauchy}
\end{center}
\hrule
\bigskip

{\LARGE \bff

\begin{itemize}
\item \tb{$V=\left[
x_i^{j-1}\right]_{i,j=1}^n$} {\large \hskip0.5in(TP if $0<x_1<x_2<\cdots<x_n$)}

\large
\begin{eqnarray*}
\tr{D_{ii}}=\prod_{j=1}^{i-1}(x_i-x_j),
\hskip0.7cm
\tr{L_{i+1,i}^{(k)}}=\prod_{j=n-k}^{i-1}\frac{x_{i+1}-x_{j+1}}{x_i-x_j},
\hskip0.7cm \tr{U^{(k)}_{i,i+1}}=x_{i+n-k}
\end{eqnarray*}

\LARGE
\item
\tb{$\displaystyle C=\left[\frac{1}{x_i+y_j}\right]_{i,j=1}^n$}
\hskip0.1in{\large (TP if $0<x_1<\cdots<x_n,\;
0<y_1<\cdots <y_n$)}


\large

\begin{eqnarray*}
\tr{D_{ii}}& = & \prod_{k=1}^{i-1}\frac{(x_i-x_k)(y_i-y_k)}{(x_i+y_k)(y_i+x_k)}
\nonumber \\
\tr{L_{i,i+1}^{(k)}}&=&
\frac{x_{n-k}+y_{i-n+k+1}}{x_i+y_{i-n+k+1}}
\prod_{l=n-k}^{i-1}\frac{x_{i+1}-x_{l+1}}{x_i-x_l}
\cdot \prod_{l=1}^{i-n+k-1}\frac{x_i+y_l}{x_{i+1}+y_l}
\\
\tr{U^{(k)}_{i+1,i}}&=&
\frac{y_{n-k}+x_{i-n+k+1}}{y_i+x_{i-n+k+1}}
\prod_{l=n-k}^{i-1}\frac{y_{i+1}-y_{l+1}}{y_i-y_l}
\cdot \prod_{l=1}^{i-n+k-1}\frac{y_i+x_l}{y_{i+1}+x_l}
\nonumber
\end{eqnarray*}

\LARGE

\item Similar formulas for Cauchy--Vandermonde, confluent

      (Jos\'e Javier Mart\'inez)

\item \tb{No subtractive cancellation $\Rightarrow$ accurate}

\end{itemize}
}


% ------------------------------------------------------------
\slide{Representation of TP Matrices}

\vskip2.7in

\centerline{\tr{Every TP matrix $A$ represented by the entries of ${\cal BD}(A)$}}



%-------------------------------------------------------------
\slide{Idea in Accurate Computations}

\begin{itemize}

\item TP matrices represented by ${\cal BD}$, not entries
\item Work on ${\cal BD}(A)$, not on $A$

\item Use only {\em Elementary Elimination Transformations (EETs)}:
\begin{enumerate}
\item Positive diagonal scaling
\item Subtract a row from next to make a zero;
\item Add a positive multiple of row to next/previous;
\end{enumerate}

\item In matrix form
$$
\mbox{EET} = \bmat{cccc}
\tr +\\
&\tr + \\
&x&\tr +\\
&&&\tr+
\emat
$$



\item EETs preserve TN and
every operation that preserves total nonnegativity $=$
sequence of EETs.

\item Applying an EET to ${\cal BD}(A)$ \tb{accurate}, since it
involves no subtractions!



\end{itemize}


%-----------------------------------------------------------
\slide{ Why Can Subtractions be \textcolor{red}{Bad}?}

\begin{itemize}
\item if $\hat a\approx a>0$ and $\hat b\approx b>0$ to (say) 9 digits,
then
$$
\left.
\begin{array}{rcl}
\hat a\cdot \hat b & \approx & a\cdot b \\
\hat a+\hat b      & \approx & a+b\\
\hat a/\hat b      & \approx & a/b
\end{array}
\right\}\mbox{~~~to about 9 digits}
$$
\textcolor{red}{BUT}
$$
\hat a-\hat b
$$
may have \textcolor{red}{no correct digits} if $a\approx b$, e.g.,

\begin{center}
\begin{tabular}{rl}
   & $.123456789\color{red}{xxx}$ \\
$-$& $.123456789\color{red}{yyy}$ \\
\hline
   & $.000000000\color{red}{zzz}$
\end{tabular}
\end{center}
\item Some subtractions are OK, e.g.,
$$
x_i-x_j
$$
where $x_i$ are initial data.

\end{itemize}


% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- I}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\phantom{
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$
\end{itemize}

% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- II}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=}
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$

\end{itemize}

% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- III}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=}
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$
\bigskip

\noindent
$
=\phantom{
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}         }
\bmat{cccc}
1 \\
& 1 \\
& \tr 0 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$

\item Is equivalent to setting an entry of ${\cal BD}(A)$ to zero and performing
\tb{\em no arithmetic}.

\end{itemize}


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- I}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
}
$


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- II}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
}
$

\begin{eqnarray}
x'&=&x\nonumber \\
y'&=&y+kx\nonumber \\
z'&=&1/y'\nonumber \\
k'&=&kz/y_1\nonumber
\end{eqnarray}

\bigskip
\bigskip

... it's all qd recurrences



%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- III}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\underline{
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$









%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- IV}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\underline{
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&1\\
&x'''&1\\
\emat
}
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  &\tb{f'}
\emat
}
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- V}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\underline{
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\tr{
\bmat{cccc}
1\\
&1\\
&x'''&1\\
\emat
}
}
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  &\tb{f'}
\emat
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\underline{
\bmat{cccc}
 1 \\
b& 1\\
& \tb {c+x'''}& 1
\emat
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  & \tb {f'}
\emat
}
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\tb{Done.}


% -----------------------------------------------------------

\slide{The Story so Far}

\begin{itemize}

\item TP matrices represented as products of bidiagonals
\item We can perform EETs without subtractions $\Rightarrow$ accuracy
\item Remains to see that all TP linear algebra is a sequence of EETs

\end{itemize}


%-----------------------------------------------------------
\slide{ Idea in Accurate Eigenvalue Computations  }

\bigskip

{\large


$$
\bmat{cccc}
1 \\
& 1 \\
&&\!\! 1\\
&&\!\!\tr {l_{41}}& 1
\emat
\!\!
\bmat{cccc}
1 \\
&\!\! 1 \\
&\!\!\tr{l_{31}} &\!\! 1\\
&\!\!&\!\!\tr{l_{42}}& 1
\emat
\!\!
\bmat{cccc}
1 \\
\tr{l_{21}}& \!\!1 \\
&\!\! \tr{l_{32}}& \!\!1\\
&\!\!& \!\!\tr{l_{43}} &\!\! 1
\emat
\!\!
\bmat{cccc}
\tr {d_1} \\
&\!\! \tr {d_2} \\
&\!\! &\!\! \tr {d_3} \\
&\!\! &\!\!  &\!\! \tr {d_4}
\emat
\!\!
\bmat{cccc}
1 & \!\!\tr {u_{12}} \\
& 1 & \!\!\tr {u_{23}}\\
& & 1 & \!\!\tr {u_{34}}\\
&&  & 1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 &\!\! \tr {u_{13}}\\
&   &\!\! 1 & \!\!\tr {u_{24}}\\
&   &\!\!   & \!\! 1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 \\
& & 1 & \!\!\tr {u_{14}}\\
&&  & 1
\emat
$$
}

\bigskip

\hskip4.3in$\downarrow\quad$ (Well known EET similarity)

\bigskip

{\large
$$
\bmat{cccc}
1 \\
\tb{l_{1} }& 1 \\
& \tb{l_{2} }& 1\\
&& \tb{l_{3} } & 1
\emat
\!\!
\bmat{cccc}
\tb {d_1} \\
&\!\! \tb {d_2} \\
&\!\! &\!\! \tb {d_3} \\
&\!\! &\!\!  &\!\! \tb {d_4}
\emat
\!\!
\bmat{cccc}
1 & \tb{l_{1} } \\
& 1 & \tb {l_{2} }\\
& & 1 & \tb {l_{3} }\\
&&  & 1
\emat
$$
}

\hskip4.3in$\downarrow\quad$

{\large
$$
\hskip0.5in\mbox{\LARGE SVD} \left(
\bmat{cccc}
\tb {d_1} \\
&\!\! \tb {d_2} \\
&\!\! &\!\! \tb {d_3} \\
&\!\! &\!\!  &\!\! \tb {d_4}
\emat^{\frac{1}{2}}
\!\!
\bmat{cccc}
1 & \tb{l_{1} } \\
& 1 & \tb {l_{2} }\\
& & 1 & \tb {l_{3} }\\
&&  & 1
\emat
\right)
$$
}


%-----------------------------------------------------------------------

\slide{ Recall: Reduction of a nonsymmetric matrix to tridiagonal form }

\hskip2in
$
\phantom{\bmat{cccc}
1\\
&1\\
&&1\\
&&-&1\\
\emat  }
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
+ & + & + & +  \\
\tr + & + & + & +
\emat
\phantom{
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
}
$



%
%-----------------------------------------------------------
% Page 32
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 2 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&&1\\
&&-&1\\
\emat
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
\tr + & \tr + & \tr + & \tr +  \\
\tr + & \tr + & \tr + & \tr +
\emat
\phantom{\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat    }
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
+ & + & + & +  \\
0 & + & + & +
\emat
$


}


%
%-----------------------------------------------------------
% Page 33
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 3 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&&1\\
&&-&1\\
\emat
\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
$


}

%
%-----------------------------------------------------------
% Page 34
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 4 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&&1\\
&&-&1\\
\emat
\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +
\emat
$


}


%
%-----------------------------------------------------------
% Page 35
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 5 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\phantom{\bmat{cccc}
1\\
&1\\
&-&1\\
&&&1\\
\emat }
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
\tr + & + & + & +  \\
0 & + & + & +
\emat
\phantom{
\bmat{cccc}
1\\
&1\\
&+&1\\
&&&1\\
\emat
}
$


}

%
%-----------------------------------------------------------
% Page 36
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 6 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&-&1\\
&&&1\\
\emat
\bmat{cccc}
+ & + & + & +  \\
\tr + & \tr + & \tr + & \tr +  \\
\tr + & \tr + & \tr + & \tr +  \\
0 & + & + & +
\emat
\phantom{
\bmat{cccc}
1\\
&1\\
&+&1&\\
&&&1\\
\emat
}
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
\tr 0 & + & + & +  \\
0 & + & + & +
\emat
$


}


%
%-----------------------------------------------------------
% Page 37
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 7 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&-&1&\\
&&&1\\
\emat
\bmat{cccc}
+ & + & + & +  \\
\tr + & \tr + & \tr + & \tr +  \\
\tr + & \tr + & \tr + & \tr +  \\
0 & + & + & +
\emat
\bmat{cccc}
1\\
&1\\
&+&1\\
&&&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=
\bmat{cccc}
+ & \tr + & \tr + & + \\
+ & \tr + & \tr + & +  \\
0 & \tr + & \tr + & +\\
0 & \tr + & \tr + & +
\emat
\bmat{cccc}
1\\
&1\\
&+&1\\
&&&1\\
\emat
$


}
%
%-----------------------------------------------------------
% Page 37
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 8 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1\\
&1\\
&-&1&\\
&&&1\\
\emat
\bmat{cccc}
+ & + & + & +  \\
\tr + & \tr + & \tr + & \tr +  \\
\tr + & \tr + & \tr + & \tr +  \\
0 & + & + & +
\emat
\bmat{cccc}
1\\
&1\\
&+&1\\
&&&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=
\bmat{cccc}
+ & \tr + & \tr + & + \\
+ & \tr + & \tr + & +  \\
0 & \tr + & \tr + & +\\
0 & \tr + & \tr + & +
\emat
\bmat{cccc}
1\\
&1\\
&+&1\\
&&&1\\
\emat
$


\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
0 & + & + & +  \\
0 & + & + & +
\emat
$


}


%
%-----------------------------------------------------------
% Page 31
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 9 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\phantom{\bmat{cccc}
1&-\\
&1\\
&&1\\
&&&1\\
\emat  }
\bmat{cccc}
+ & + & + & \tr +  \\
+ & + & + & +  \\
0 & + & + & +  \\
0 & 0 & + & +
\emat
\phantom{
\bmat{cccc}
1\\
&1\\
&&1\\
&&+&1\\
\emat
}
$


}

%
%-----------------------------------------------------------
% Page 32
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 10 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\phantom{\bmat{cccc}
1&-\\
&1\\
&&1\\
&&&1\\
\emat  }
\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +  \\
0 & 0 & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1&-\\
&&&1\\
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & + & \tr 0  \\
+ & + & + & +  \\
0 & + & + & +  \\
0 & 0 & + & +
\emat
$


}


%
%-----------------------------------------------------------
% Page 33
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 11 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1&\\
&1\\
&&1&+\\
&&&1\\
\emat
\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +  \\
0 & 0 & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1&-\\
&&&1\\
\emat
$

\bigskip
\bigskip

\hskip1.78in
$
=\bmat{cccc}
1&\\
&1\\
&&1&+\\
&&&1\\
\emat
\bmat{cccc}
+ & + & + & 0  \\
+ & + & + & +  \\
\tr 0 &\tr + & \tr+ & \tr+  \\
\tr 0 &\tr 0 & \tr+ & \tr+
\emat
$


}
%
%-----------------------------------------------------------
% Page 33
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 12 }
\end{center}
\hrule
\bigskip

{\LARGE \bf

\hskip2in
$
\bmat{cccc}
1&\\
&1\\
&&1&+\\
&&&1\\
\emat
\bmat{cccc}
+ & + & \tr + & \tr +  \\
+ & + & \tr + & \tr +  \\
0 & + & \tr + & \tr +  \\
0 & 0 & \tr + & \tr +
\emat
\bmat{cccc}
1\\
&1\\
&&1&-\\
&&&1\\
\emat
$

\bigskip
\bigskip

\hskip1.78in
$
=\bmat{cccc}
1&\\
&1\\
&&1&+\\
&&&1\\
\emat
\bmat{cccc}
+ & + & + & 0  \\
+ & + & + & +  \\
\tr 0 &\tr + & \tr+ & \tr+  \\
\tr 0 &\tr 0 & \tr+ & \tr+
\emat
$

\bigskip
\bigskip

\hskip3.22in
$
=\bmat{cccc}
+ & + & + & 0  \\
+ & + & + & +  \\
0 & + & + & + \\
0 & 0 & + & +
\emat
$


}





%
%-----------------------------------------------------------
% Page 39
\newpage
\begin{center}
{\LARGE \bf Reduction of a nonsymmetric matrix to tridiagonal form -- 13 }
\end{center}
\hrule
\bigskip

\noindent $
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
+ & + & + & +  \\
\tr + & + & + & +
\emat
\Rightarrow
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
\tr + & + & + & +  \\
\tb 0 & + & + & +
\emat
\Rightarrow
\bmat{cccc}
+ & + & + & +  \\
+ & + & + & +  \\
\tb 0 & + & + & +  \\
\tb 0 & \tr + & + & +
\emat
\Rightarrow
\bmat{cccc}
+ & + & + & \tr +  \\
+ & + & + & +  \\
\tb 0 & + & + & +  \\
\tb 0 & \tb 0 & + & +
\emat
\Rightarrow
$

\bigskip

\noindent$
\bmat{cccc}
+ & + & \tr + & \tb 0  \\
+ & + & + & +  \\
\tb 0 & + & + & +  \\
\tb 0 & \tb 0 & + & +
\emat
\Rightarrow
\bmat{cccc}
+ & + & \tb 0 & \tb 0  \\
+ & + & + & \tr +  \\
\tb 0 & + & + & +  \\
\tb 0 & \tb 0 & + & +
\emat
\Rightarrow
\bmat{cccc}
+ & + & \tb 0 & \tb 0  \\
+ & + & + & \tb 0  \\
\tb 0 & + & + & +  \\
\tb 0 & \tb 0 & + & +
\emat
$

\vskip1in
\begin{itemize}

\item EETs performed implicitly $\Rightarrow$ high relative accurcy
\item The first example of a \tb{\em nonsymmetric} eigenvalue algorithm
      delivering high relative accuracy

\item Cost: $7n^3$
\end{itemize}


% ---------------------------------------------------------------------
\slide{ The SVD, QR Decompositions }

\begin{itemize}
\item Givens rotation $=$ product of 3 EETs
 $$
\bmat{cc}
c & s \\
-s & c
\emat
=
\bmat{cc}
1 & s/c \\
0 & 1
\emat
\bmat{cc}
1/c \\ & c
\emat
\bmat{cc}
1 & 0 \\
-s/c & 1
\emat
$$
\item Implies Hessenberg reduction, SVD, QR accurate
\end{itemize}


% -------------------------------------------------------------
\slide{${\cal BD}$(Product)}

\vskip1in

\begin{itemize}

\item Any TP matrix $=$ product of bidiagonals $=$ product of EETs
\item Thus ${\cal BD}(AB)$ equivalent to applying a number of
EETs to ${\cal BD}(A)$

\item All TP linear algebra $=$ sequence of EETs $\Rightarrow$ accurate

\end{itemize}



% ----------------------------------------
\slide{\LARGE \bff  Example }
\centerline{\resizebox{7.5in}{!}{
\includegraphics*{HilbertPascal.pdf}
      }}

% ----------------------------------------
\slide{\LARGE \bff  Extreme Example: eig(20th Schur Complement of Vand(1:40)) }
\centerline{\resizebox{7.5in}{!}{
\includegraphics*{SchurComplementVand40.pdf}
      }}


% ---------------------------------------------------------------
\slide{Bidiagonal have repercussions beyond accurate computations}

\begin{itemize}
\item Variation-diminishing property:

$$
\mbox{EET} \times \mbox{vector} =
\bmat{ccc} 1 \\ x&1\\ &&1 \emat \cdot \bmat{c} a \\ b\\ c \emat
=
\bmat{c} a \\ b+ax \\c \emat,
x>0
$$

\vskip0.5in

$$
\begin{array}{c c c}
\begin{array}{c} \tr{+} \\ \tr{+} \\ \tr{+} \end{array} \rightarrow
\begin{array}{c} \tr{+} \\ \tr{+} \\ \tr{+} \end{array}
&
\quad \quad\quad
\begin{array}{c} \tr{+} \\ ** \\ \tb{-} \end{array} \rightarrow
\begin{array}{c} \tr{+} \\ ** \\ \tb{-}\end{array}
\quad \quad\quad
&
\begin{array}{c} \tr{+} \\ \tb{-} \\ \tr{+} \end{array} \rightarrow
\begin{array}{c} \tr{+} \\ ? \\ \tr{+} \end{array}
\\
\\
\begin{array}{c} \tb{-} \\ \tb{-} \\ \tb{-} \end{array} \rightarrow
\begin{array}{c} \tb{-} \\ \tb{-} \\ \tb{-}\end{array}
&
\begin{array}{c} \tb{-} \\ ** \\ \tr{+} \end{array} \rightarrow
\begin{array}{c} \tb{-} \\ ** \\ \tr{+} \end{array}
&
\begin{array}{c} \tb{-} \\ \tr{+} \\ \tb{-} \end{array} \rightarrow
\begin{array}{c} \tb{-} \\ ? \\ \tb{-} \end{array}
\\
\hline
\\
\begin{array}{c} 0 \end{array} \rightarrow
\begin{array}{c} 0 \end{array}
&
\quad\quad\quad
\begin{array}{c} 1 \end{array} \rightarrow
\begin{array}{c} 1 \end{array}
\quad\quad\quad
&
\begin{array}{c} 2 \end{array} \rightarrow
\begin{array}{c} 0,2 \end{array}
\end{array}
$$
\bigskip


Therefore: $
\tr{\# \mbox{Sign Changes}(Az)\le  \# \mbox{Sign Changes}(z)}
$

\bigskip

\end{itemize}


% ----------------------------------------
% Page 2a

\newpage
\begin{center}
{\LARGE \bff  Oscillating Vectors and TP Matrices }
\end{center}
\hrule
\bigskip

{\LARGE \bff



\bigskip


Let $A$ be TP, $ A=V\cdot \Lambda \cdot V^{-1} $, then

\bigskip


{\large
$$
\mbox{\LARGE $V=$}
\bmat{cccc}
1 \\
& 1 \\
&&\!\! 1\\
&&\!\!\tr {+}& 1
\emat
\!\!
\bmat{cccc}
1 \\
&\!\! 1 \\
&\!\!\tr{+} &\!\! 1\\
&\!\!&\!\!\tr{+}& 1
\emat
\!\!
\bmat{cccc}
1 \\
\tr{+}& \!\!1 \\
&\!\! \tr{+}& \!\!1\\
&\!\!& \!\!\tr{+} &\!\! 1
\emat
\!\!
\bmat{cccc}
\tr {+} \\
& \tr {+} \\
& &\tr {+} \\
& &  & \tr{+}
\emat
\!\!
\bmat{cccc}
1 & \tb {-} \\
& 1 & \tb {-}\\
& & 1 & \tb {-}\\
&&  & 1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 & \tb {-}\\
&   & 1 & \tb {-}\\
&   &   &  1
\emat
\!\!
\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tb {-}\\
&&  & 1
\emat
$$
}


\bigskip

\LARGE
\begin{itemize}
\item \tr{Lowerly Totally Positive (LTP)} matrix

\item Variation Diminishing Property \hskip0.45in $\Rightarrow S(v_j)\le j-1$

\item $V^{-T}$ eigenvecs of $A^T\;\;\Rightarrow$ $V^{-T}$ LTP
$\Rightarrow S(v_j)\ge j-1$

\vskip1in

\item Call these \tr{LTP$^2$ matrices} ($V$ {\em and} $V^{-T}$ are LTP)

\item Thm (Dopico, K.): LTP$^2\; \Leftrightarrow S(v_j)=j-1$

\item Cor: $Q$ in $A=QR$ is LTP; $Q=Q^{-T}\;\Rightarrow S(q_j)=j-1$

\item Also works numerically

\end{itemize}

}

% ----------------------------------------
\slide{ Conclusions }

\vskip1in
\begin{itemize}

\item Virtually all linear algebra with TP (also nonsingular TN) matrices
done to high relative accuracy in $O(n^3)$ time

\item New: Understanding of oscillating properties of TP matrices

\item Key: Bidiagonal Decompositions

\item Slides, papers, software: Google('Plamen Koev')

\end{itemize}

\end{document}
