\documentclass[10pt,leqno,twoside]{siamltex}

\usepackage{amsfonts,epsfig}

\setlength{\textheight}{190mm}
\setlength{\textwidth}{130mm}
\topmargin=20mm

\def\cvd{~\vbox{\hrule\hbox{%
\vrule height1.3ex\hskip0.8ex\vrule}\hrule}}

\newtheorem{remark}[theorem]{Remark}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{example}[theorem]{Example}

\usepackage{latexsym}
\usepackage{graphicx}
%\usepackage{bordermatrixs}
%\usepackage{showkeys}
%\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{pst-all}
\usepackage[psamsfonts]{amssymb}

%\setlength{\textheight}{8.5in}
%\addtolength{\oddsidemargin}{-0.75in}
%\setlength{\textwidth}{6.5in}
%\setlength{\topmargin}{-1in}

\newtheorem{1}{LEMMA}[section]

\newtheorem{2}[1]{THEOREM}

\newtheorem{3}[1]{COROLLARY}

\newtheorem{4}[1]{PROPOSITION}

\newtheorem{5}[1]{REMARK}

\newtheorem{10}{DEFINITION}

\newtheorem{20}{ASSUMPTION}



\newcommand{\lrn}{\langle n \rangle}
\newcommand{\s}{{\cal S}}
\setcounter{page}{1}
\newcommand{\al}{\alpha}
\newcommand{\ex}{\rm exp}
\newcommand{\lam}{\lambda}
\newcommand{\lf}{\lfloor}
\newcommand{\rf}{\rfloor}
\newcommand{\rc}{\rceil}
\newcommand{\lc}{\lceil}
%\newcommand{\dfrac}[2]{\displaystyle\frac{#1}{#2}}
\newcommand{\ls}{L^\#}
\newcommand{\ones}{{\bf 1}}
\newcommand{\its}{(I-T)^\#}
\newcommand{\mfp}{mean first passage}
\newcommand{\qs}{Q^{\#}}
\newcommand{\PS}{(I-P)^{\#} }
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\R}{\rm I\kern-.09emR}
\newcommand{\g} {{\cal G}}
\newcommand{\dd}{\tilde{d}}
\newcommand{\p} {{\cal P}}
\newcommand{\bi}{|\beta_{i}(e)|}
\newcommand{\bj}{|\beta_{j}(e)|}
\newcommand{\bif}{|\beta_{i}(f)|}
\newcommand{\bjf}{|\beta_{j}(f)|}
\newcommand{\bij}{|\beta_{i}(e_j)|}
\newcommand{\bii}{|\beta_{i}(e_i)|}

\newcommand{\bd}{\begin{displaymath}}
\newcommand{\ed}{\end{displaymath}}
\newcommand{\m} { \marginpar  }
\newcommand{\tp}{\tilde{\pi}}
\newcommand{\e} { \ = \ }
\newcommand{\leqs}{ \ \leq \ }
\newcommand{\geqs}{ \ \geq \ }

\newcommand{\A}{{\bf \cal A}}
\newcommand{\as}{A^\#}
\newcommand{\Are}{{\bf R}}
\newcommand{\Cee}{{\bf C}}
\newcommand{\Ceehat}{{\bf \hat C}}
\newcommand{\Sea}{{\cal C}}
\newcommand{\Dee}{{\bf D}}
\newcommand{\Em}{{\bf \cal M}}
\newcommand{\Ef}{{\bf \cal F}}
\newcommand{\intt}{\int\limits}
\newcommand{\Oh}{{\bf \cal O}}
\newcommand{\ftild}{\skew5\tilde f}
\newcommand{\Res}{{\rm Res}}
\newcommand{\Stild}{\skew4\tilde S}
\newcommand{\Mtild}{\skew4\tilde M}
\newcommand{\xtild}{\skew4\tilde x}
\newcommand{\Tee}{{\bf T}}
\newcommand{\aych}{{\bf H}}
\newcommand{\Zee}{{\bf Z}}
\newcommand{\Aut}{{\bf Aut\ }}
\newcommand{\See}{{\bf \cal C}}

\newcommand{\bp}{\underline{\bf Proof}:\ }
\newcommand{\ep}{{\hfill $\Box$}\\ }
\def\R{{\rm I\kern-.25em R}}
\def\N{{\rm I\kern-.25em N}}
\def\RR{\cal R}
\def\NN{\cal N}
           \def\C{{\rm\kern.24em
\vrule width.02em height0.4ex depth-.05ex \kern-.26em C}}

\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\thefigure}{\thesection.\arabic{figure}}

\def\reff#1{{\rm (\ref{#1})}}

%\newcommand{\nsubset}{\subseteq \mbox{\hspace{-.08in}} \setminus}


\begin{document}
\input{elaheader-vol13-9.tex}
\setcounter{page}{131}


\title{A Parallel Algorithm For Computing The Group Inverse Via
Perron Complementation\thanks{Received by the editors 20 December 2004.
Accepted for publication 5 April 2005. Handling Editor: Ravindra B. Bapat.}}
\author{Michael Neumann\thanks{Department of Mathematics,
University of Connecticut, Storrs,
Connecticut 06269--3009, USA (neumann@math.uconn.edu).
The work of this author was supported in part by NSF Grant No. DMS0201333.}
\and
Jianhong Xu\thanks{Department
of Mathematics and Statistics, University of West Florida,
Pensacola, Florida 32514, USA (jxu@uwf.edu).}}
%\date{}
\pagestyle{myheadings}
\markboth{M.\ Neumann and J.\ Xu}{Parallel Algorithm for Computing 
the Group Inverse}

\maketitle

\begin{abstract}
A parallel algorithm is presented for computing the group inverse of
        a singular M--matrix of the form $A=I-T$, where $T \in \mathbb R^{n
\times n}$ is irreducible and stochastic. The algorithm is constructed
in the spirit of Meyer's Perron
complementation approach to computing the Perron vector of an
irreducible nonnegative matrix.  
The asymptotic number of multiplication operations that
is necessary to implement the
algorithm is analyzed, which shows that the algorithm saves a significant
amount of computation over
the direct computation of the group inverse of $A$.
\end{abstract}

\begin{keywords}
Group inverses, M--matrices, Perron complements, Parallel algorithm.
\end{keywords}

\begin{AMS}
15A09, 15A48, 15A51, 65F30, 65C40.
\end{AMS}

\section{Introduction}
\label{sec.1}
\setcounter{equation}{0}

The {\it group inverse} of a matrix $A \in \mathbb R^{n \times n}$,
denoted by $\as$
when it exists, is the unique matrix $X \in \mathbb R^{n \times n}$
that satisfies
the matrix equations $AXA=A$, $XAX=X$, and $AX=XA$.
The group inverse has been utilized in a variety of applications
\cite{DuNe84, DuNe85, EiMaNi88, FuMe86, GoMe86, HaNe90, HaHe84, Kirk95,
KiNe94, KiNe99, KiNeSh98, KiNeXu01, KiNeXu04, Meye75, Meye80, Sene91},
mostly in the context of a singular M--matrix
\be
\label{AS}
A=\rho_S I - S,
\ee
where $S \in \mathbb R^{n \times n}$ is nonnegative and irreducible
and where $\rho_S$ is its Perron root.\footnote{For such a matrix
$A$, the existence of $A^\#$ is guaranteed by the structure
of the Jordan blocks of $S$ \cite{CaMe91, Meye75}.} In particular, these
applications include:


(i) For a finite ergodic Markov chain with a transition
matrix $T$, Meyer \cite{Meye75} has shown that
virtually all the important characteristics of the chain can be
determined from
the group inverse of $A=\rho_TI-T=I-T$. Furthermore,
      in
\cite{FuMe86, HaHe84, KiNeSh98, Meye80, Sene91} it has been shown that
the entries of $\as$ can be used to provide perturbation bounds on
the stationary
distribution vector of the chain.

(ii) In
\cite{DuNe84, DuNe85} it has been shown that for $A$ in \reff{AS},  the signs
of the entries of $\as$ give us qualitative information about the behavior
of the Perron root of $S$ as a function of the entries of $S$, namely
in addition to
it being known that the Perron root is a strictly increasing function of each
of the entries, the signs of the entries of
$\as$ answer the question whether the Perron root is a concave
or a
convex function
of each of the entries.
Results of this type have  been
applied in the study of matrix population models in  \cite{KiNe94, KiNeXu04}.


%(iii) Furthermore,  returning to the case when $S=T$, where $T$ is the
%transition matrix of a finite ergodic Markov chain,
% in
%\cite{FuMe86, HaHe84, KiNeSh98, Meye80, Sene91} it has been shown that
%the entries of $\as$ provide useful perturbation bounds for the stationary
%distribution vector of the chain.
%\\

%These perturbation bounds can be
%generalized to study the sensitivity of the Perron vectors of the
% irreducible nonnegative matrix $S$.

In view of the above--mentioned applications, a question of interest
is how to efficiently compute the group inverse
$A^\#$ of $A$ in (\ref{AS}). Several algorithms for computing $A^\#$
have been suggested in \cite{AnRo87, BeGr03, CaMe91, FuMe86, Grev72, Hart76,
Meye75}. These methods typically require $O(n^3)$ to $O(n^4)$ arithmetic
operations and so they can be quite expensive to
implement. However,
     the issue of
the parallel  computation of $A^\#$ has received little attention in the
literature.

In this paper we shall present an algorithm for computing $A^\#$ in parallel,
assuming that $A$ is given by (\ref{AS}). The numerical evidence which
we shall provide indicates that this
algorithm is more efficient compared with direct computation of $A^\#$. From
the examples that we have tested with MATLAB, the savings in the
number of flops (floating
point operations) are roughly 50\% for matrices of size ranging from $n=50$ to
$n=1600$. An asymptotic analysis shows that the algorithm saves
approximately 12.5\% of the multiplication operations if it
is implemented
in a purely serial fashion. 

A useful observation is that $A$ in (\ref{AS}) can be reduced, using
a diagonal similarity transformation
       (see, for example, \cite[Theorem
2.5.4]{BePl94}),
to the case where $A:=I-T$, with $T \in \mathbb R^{n \times n}$ being
irreducible
and stochastic. Consequently,
without loss of generality, we shall focus on this case from here on.

The key to constructing our algorithm is {\it Perron
complementation}. Let $\alpha$
and $\beta$ be nonempty subsets of the index set
$\langle n \rangle:=\{1, 2, \ldots, n\}$, both consisting of strictly
increasing integers. For any $X \in \mathbb R^{n \times n}$, we shall denote
by $X[\alpha, \beta]$ the submatrix of $X$ whose rows and columns are
determined by $\alpha$ and $\beta$, respectively. In the special case
when $\beta = \alpha$, we shall  use $X[\alpha]$
to denote $X[\alpha, \alpha]$.\footnote{We follow the notation in
\cite{HoJo85} for submatrices. This notation allows conclusions to be
readily extended to the case when $\alpha$ and $\beta$ consist
of nonconsecutive integers.}
Given the irreducible stochastic
matrix $T \in \mathbb R^{n \times n}$, the {\it Perron complement} of
$T[\alpha]$
is defined to be\footnote{The notion of Perron complement can be similarly
defined on an irreducible nonnegative matrix (see \cite{Meye89, Meye89a}).}
\be
\label{Per_Com}
P_{\alpha}:= T[\alpha]+
T[\alpha, \langle n \rangle \backslash \alpha]
(I-T[\langle n \rangle \backslash
\alpha])^{-1}T[\langle n \rangle \backslash \alpha, \alpha].
\ee

Meyer \cite{Meye89, Meye89a} proved that the Perron complement $P_\alpha$
resembles $T$.
Specifically, $P_\alpha$ is also irreducible and stochastic and, in addition,
on letting $\pi \in \mathbb R^n$ be the normalized left Perron vector of $T$,
viz. the column vector satisfying
\be
\label{new.1000}
\pi^t T \e \pi^t \ \ {\rm and} \ \ \|\pi\|_1 \e 1,
\ee
then
\be
\label{new.2000}
\pi_\alpha\e \frac{\pi[\alpha]}{\xi_\alpha}, \ \ \mbox{with} \ \
\xi_\alpha\e \|\pi[\alpha]\|_1,
\ee
where $\pi[\alpha]$ is the subvector of $\pi$ determined by
$\alpha$, turns out to be the normalized left Perron vector of $P_{\alpha}$.
Based on these results, Meyer introduced a parallel algorithm for
computing the left Perron vector via Perron complementation.

Note that the irreducible stochastic matrix $T$ can be thought of as the
transition matrix of some finite ergodic Markov chain $\{X_i\}_{i=0}^\infty$
on state space ${\cal S}=\{1, 2, \ldots, n\}$. The {\it mean first passage
time} from states $i$ to $j$, denoted by $m_{i,j}$, is defined to be the
expected number of time steps that the chain, starting initially from
state $i$, would take before it reaches state $j$ for the first time
\cite{KeSn60}, i.e.
\be
\label{new.3000}
m_{i,j}:= {\rm E}(F_{i,j})\e \sum_{k=1}^\infty k{\rm Pr}(F_{i,j}=k),
\ee
where $F_{i,j}:=\min\{\ell \ge 1:X_\ell=j | X_0=i\}$. The matrix
$M=[m_{i,j}] \in \mathbb R^{n \times n}$ is called the {\it mean first
passage matrix} of the chain or, simply, of $T$. Obviously the mean first
passage matrix of the Perron complement $P_\alpha$ can be similarly
defined since $P_\alpha$ can also be regarded as the transition matrix
of an ergodic chain with fewer states.

As a further development of Meyer's results on Perron complementation,
Kirkland, Neumann, and Xu \cite{KiNeXu01} showed that the mean first
passage matrix of $P_\alpha$ is closely related to $M[\alpha]$ and
$M[\langle n \rangle \backslash \alpha]$, i.e. the corresponding submatrices
of the mean first passage matrix of $T$. Accordingly,
the mean first passage matrix of the entire chain can be computed in
parallel via Perron complementation.

The interesting relationship between the irreducible stochastic matrix
$T$ and its Perron complement $P_\alpha$, as shown in \cite{KiNeXu01,
Meye89, Meye89a}, leads us to explore if Perron
complementation can be
exploited for the parallel computation of $A^\#$. Specifically, on letting
$B_\alpha:=I-P_\alpha$, we ask the following questions: (i) How are
$A^\#$ and $B_\alpha^\#$ related? (ii) Does the connection between $A^\#$
and $B_\alpha^\#$ allow the computation of $A^\#$ to be carried out in
parallel? These questions will be completely answered in this paper.
We point out that the relationship between $A^\#[\alpha]$ and $B_\alpha^\#$
has been shown in \cite{NeXu03} for the special case when  
$\alpha=\{1, 2, \ldots, n-1\}$. Furthermore, for the special case
when $T$ is periodic, Kirkland \cite{Kirk95} has developed, without
recourse to the terminology of Perron complementation, formulae for the
blocks of $A^\#$. Thus our results here will also generalize those in
\cite{Kirk95, NeXu03}.

The plan of this paper is as follows. In Section 2 we shall
summarize some necessary
results on Perron complementation from the literature. Our main
results on the
computation of the group inverse via Perron complementation will be
presented in Section 3.
Section 4 will be devoted to describing our parallel
algorithm for computing the group
inverse. Finally,   some concluding remarks are given in Section 5.

%The structure of this paper is as follows. In Section 2 we shall
%summarize some necessary
%results on Perron complementation from the literature. Our main
%results on the
%computation of the group inverse via Perron complementation will be
%presented in Section 3.
%Section 4 will be devoted to our parallel
%algorithm for computing the group
%inverse. Finally, we shall give some concluding remarks in Section 5.

%Throughout the sequel the letters $I$, $J$, and $e$ will
% represent the identity
%matrix, the matrix of all
%  ones, and the column vector of all ones, respectively, whose
%dimensions can be readily determined
%from the context in which they arise. We shall denote by $\pi$ the
%normalized left Perron vector
%for $T$, by $M$ the mean first passage matrix for (the finite ergodic
%Markov chain determined by)
%$T$, and by $W$ the matrix $e\pi^t$. The corresponding quantities
%related to the Perron complement
%$P_\alpha$ will be similarly denoted with a subscript $\alpha$, i.e.
%$\pi_\alpha$, $M_\alpha$, and
%$W_\alpha$. The cardinality of an index set $\alpha$ will be written as
%$|\alpha|$. We shall let $A=I-T$ and $B_\alpha=I-P_\alpha$. For any
%square matrix $X=(x_{i,j})
%\in
%\mathbb R^{n \times n}$, we shall use $X_d$ to represent the diagonal matrix
%${\rm diag}(x_{1,1},
%x_{2,2},\ldots,x_{n,n})$.

\section{Preliminaries}
\label{sec.2}
\setcounter{equation}{0}

Recall that the purpose of this paper is the computation in parallel
of the
group inverse of  $A:=I-T$, where $T \in
\mathbb R^{n
\times n}$ is irreducible and stochastic.

        Partition $T$ into a $k \times k ~(k \ge
2)$ block form as follows:
\be
\label{Par_T_k}
T\e \left[\begin{array}{cccc}
T[\alpha_1] & T[\alpha_1, \alpha_2] & \cdots & T[\alpha_1, \alpha_k]\\
T[\alpha_2, \alpha_1] & T[\alpha_2] & \cdots & T[\alpha_2, \alpha_k]\\
\vdots & \vdots & \ddots & \vdots\\
T[\alpha_k, \alpha_1] & T[\alpha_k, \alpha_2] & \cdots & T[\alpha_k]
\end{array}\right],
\ee
where $\alpha_1, \alpha_2, \ldots, \alpha_k$ are nonempty disjoint subsets of
the index set $\langle n \rangle:=\{1,\ldots, n\}$ which form a
partition of
$\langle n \rangle$. Define $W:=e\pi^t$, where $\pi$ is the left
      Perron vector of $T$ normalized so that
$\|\pi\|_1=1$ and
where
$e
\in
\mathbb R^n$ is a column vector of all ones.
The vector $\pi$ is   the {\it
stationary distribution vector}
of the underlying Markov chain. Let $M \in \mathbb R^{n
\times n}$ be the mean
first passage matrix of $T$ as defined in (\ref{new.3000}). We shall
always partition
$A^\#$, $W$, and $M$ in conformity with $T$.

Throughout the sequel, the letters $J$ and $e$ will represent a matrix of all
ones and a column vector of all ones, respectively, whose dimensions
can be determined from the
context. For any square matrix $X$,  we shall denote by $X_d$ the
diagonal matrix obtained from $X$
by setting  all its off--diagonal entries to zero.

We begin with the following two lemmas from \cite{CaMe91, Meye75}.

\begin{1}
{\rm (\cite[Theorem 8.5.5]{CaMe91})}
\label{new.12000}
\be
\label{pi_Aginv}
\pi^tA^\#\e 0.
\ee
\end{1}

\begin{1}
{\rm (\cite[Theorem 3.3]{Meye75})}
\label{MFP}
The mean first passage matrix $M$ of $T$ can be expressed as
\be
M\e \Big[I-A^\#+J(A^\#)_d\Big](W_d)^{-1}.
\ee
\end{1}

Lemma \ref{MFP} gives the relationship between $M$ and $A^\#$. For $i=1, 2,
\ldots, k$, let $P_{\alpha_i}$ be the Perron complement of $T[\alpha_i]$.
In what follows, we shall use the subscript $\alpha_i$ to denote quantities
associated with $P_{\alpha_i}$. Put
$B_{\alpha_i}:=I-P_{\alpha_i}$. Since $P_{\alpha_i}$ is also irreducible and
stochastic, its mean first passage matrix $M_{\alpha_i}$ is defined in the same
way as $M$. Let $\pi_{\alpha_i}$ be
the normalized left Perron vector of $P_{\alpha_i}$ and set
$W_{\alpha_i}:=e\pi_{\alpha_i}^t$.
The following corollary from Lemma \ref{MFP} characterizes the relationship
between $M_{\alpha_i}$ and $B_{\alpha_i}^\#$.

\begin{3}
\label{new.10000}
For $i=1, 2, \ldots, k$, the mean first passage matrix $M_{\alpha_i}$ of
$P_{\alpha_i}$ can be expressed as
\be
\label{MFP_alpha}
M_{\alpha_i}\e
\Big[I-B_{\alpha_i}^\#+J(B_{\alpha_i}^\#)_d\Big][(W_{\alpha_i})_d]^{-1}.
\ee
\end{3}

As already mentioned earlier, according to Meyer \cite[Theorem
2.1]{Meye89}, for $i=1, 2, \ldots,
k$, the normalized left Perron vector of $P_{\alpha_i}$ is given by
\be
\label{pi_alpha}
\pi_{\alpha_i}=\frac{\pi[\alpha_i]}{\xi_{\alpha_i}}
\ee
with $\xi_{\alpha_i}=\|\pi[\alpha_i]\|_1$. The number $\xi_{\alpha_i}$ is
called the $i$--th {\it coupling factor}. Note that $\sum_{i=1}^k
\xi_{\alpha_i}=1$. The next lemma, again due to Meyer,  points out how the
coupling factors can be
obtained without actually computing $\pi$.

\begin{1}
{\rm (\cite[Theorem 3.2]{Meye89})}
\label{Coup}
Let $C=[c_{i,j}] \in \mathbb R^{k \times k}$ be defined via
\be
c_{i,j}:\e \pi_{\alpha_i}^tT[\alpha_i, \alpha_j]e,
       \ \ i, j= 1, 2, \ldots, k.
\ee
Then $C$ is irreducible and stochastic. Moreover,
$\xi=[\xi_{\alpha_1}, \xi_{\alpha_2}, \ldots, \xi_{\alpha_k}]^t$ is
the normalized left Perron
vector of $C$.
\end{1}


The matrix $C$ is called the {\it coupling matrix}.

In the sequel we shall also require the following two lemmas
from Kirkland, Neumann, and Xu \cite{KiNeXu01} on the relationship between $M$
        and $M_{\alpha_i}$, the mean first passage
matrix of $P_{\alpha_i}$. In  the first lemma the principal submatrices of $M$
are determined, while in the second lemma, the off--diagonal blocks of
$M$ are determined.

\begin{1}
{\rm (\cite[Theorem 2.2]{KiNeXu01})}
\label{M_diag}
For $i=1, 2, \ldots, k$,
\be
\label{M_diag_i}
M[\alpha_i]\e \frac{1}{\xi_{\alpha_i}}M_{\alpha_i}+V_{\alpha_i},
\ee
where
\begin{eqnarray}
\label{V_i}
V_{\alpha_i} & := & B_{\alpha_i}^\#
T[\alpha_i, \langle n \rangle \backslash
        \alpha_i](I-T[\langle n \rangle \backslash \alpha_i])^{-1}J
       \nonumber \\
\ & & \nonumber \\
        & &\hspace*{1cm} -\Big[B_{\alpha_i}^\# T[\alpha_i, \langle n \rangle \backslash
\alpha_i](I-T[\langle n \rangle \backslash \alpha_i])^{-1}J\Big]^t.
\end{eqnarray}
\end{1}

The matrix $V_{\alpha_i}$ is clearly skew--symmetric and of rank at most 2.

\begin{1}
{\rm (\cite[Theorem 2.3]{KiNeXu01})}
\label{M_off}
For $i=1, 2, \ldots, k$,
\begin{eqnarray}
\label{M_off_i}
M[\langle n \rangle \backslash \alpha_i, \alpha_i] & =
& (I-T[\langle n \rangle
        \backslash \alpha_i])^{-1}\Big[T[\langle n \rangle \backslash
\alpha_i, \alpha_i]M[\alpha_i]+J
\nonumber \\
\ & & \nonumber \\
        & & \hspace*{1cm}-T[\langle n \rangle \backslash \alpha_i,
       \alpha_i](M[\alpha_i])_d\Big].
\end{eqnarray}
\end{1}

We comment that Corollary \ref{new.10000}, formula (\ref{pi_alpha}),
and Lemmas \ref{Coup}, \ref{M_diag}, and \ref{M_off} continue to hold
even when any subset $\alpha_i$ consists of nonconsecutive
indices.

\section{Main Results}
\label{sec.3}
\setcounter{equation}{0}

In this section we develop our main results in which we show how the blocks
of $\as$, where $A:=I-T$ with $T \in \mathbb R^{n \times n}$ being
irreducible and stochastic,
can be linked to the group inverses associated with
the smaller size irreducible transition matrices arising from
Perron complementation. Again we use a $k \times k$ partitioning
of $T$ which is given by (\ref{Par_T_k}).
%but we shall prove our main results for the case when $k=2$ since
%they can be extended without difficulty to the general case when
%$k >2$.

%Without loss of generality, we shall first consider the case when $T$ is
%partitioned into a $2 \times 2$ block form as
%\be
%\label{Par_T_2}
%T\e \left(\begin{array}{cc}
%T[\alpha_1] & T[\alpha_1, \alpha_2]\\
%T[\alpha_2, \alpha_1] & T[\alpha_2]
%\end{array}\right),
%\ee
%where $\alpha_1$ and $\alpha_2$, both nonempty, form a partition of
%$\langle n \rangle$. Our results, however, can be extended without difficulty
%to a general
%$k \times k ~(k > 2)$ partitioning of $T$ as in (\ref{Par_T_k}).\\

We construct a matrix $U \in \mathbb R^{n \times n}$ by
\be
\label{new.11000}
U:=(M-M_d)W_d,
\ee
where, as defined in the previous section, $M$ is the mean first
passage matrix of $T$ and $W:=e\pi^t$. As we shall see, $U$ turns out
to play a central role in
establishing the connection between $A^\#$ and quantities related
to Perron complementation and in constructing our parallel algorithm
for computing $A^\#$. It should be noted that $U$ is  known
in the literature to have several interpretations concerning Markov chains and
       concerning surfing
the Web. First, Kemeny and Snell \cite[Theorem 4.4.10]{KeSn60}  observed that
       $U$ has constant row sums $\sum_{j \ne i}\pi_j m_{i,j}=
{\rm tr}(A^\#)$, for $i=1, 2, \ldots, n$.
The quantity $K:={\rm tr}(\as)+1$ is known as the {\it Kemeny
constant}. In relation to the Web it measures the expected
number of links
a surfer would follow to exit a site, which he may have entered
because of being lost, and enter another random site (see
Levene and Loizou \cite{LeLo02}).
It is also called the {\it expected time to
mixing in a
Markov chain} (see Hunter \cite{Hunter03}).





The relationship between the diagonal entries of $A^\#$ and $U$ is given by
the lemma below, which shows that the diagonal entries of $A^\#$ can
be expressed in terms of $U$ as well as $\xi_{\alpha_i}$ and $\pi_{\alpha_i}$
arising from Perron complementation.


% We shall next find an
%alternative expression for $J(A^{\#}[\alpha_i])_d$ in order to
%explicitly represent the blocks of
%$A^\#$ with quantities related directly to the Perron complements
%$P_{\alpha_i}$'s.

\begin{1}
\label{Lem3}
Let $A^\#=[a^\#_{i,j}]$. Then
\be
\label{Aginv_diag_ii}
[a^\#_{1,1}, a^\#_{2,2}, \ldots, a^\#_{n,n}]
\e [\xi_{\alpha_1}\pi_{\alpha_1}^t, \xi_{\alpha_2}\pi_{\alpha_2}^t, \ldots,
\xi_{\alpha_k}\pi_{\alpha_k}^t]~U.
\ee
\end{1}

{\em Proof.}
First we observe that from Lemma \ref{MFP}, $m_{i,i}=1/\pi_i$,
for all $i$, i.e. $M_d=(W_d)^{-1}$.

Next, again by Lemma \ref{MFP}, we obtain that
$$\begin{array}{rcl}
\pi^tU & = & \pi^t(M-M_d)W_d\\
\\
       & = & \pi^t\Big[[I-A^\#+J(A^\#)_d](W_d)^{-1}-(W_d)^{-1}\Big]W_d\\
\\
       & = & -\pi^tA^\#+\pi^tJ(A^\#)_d\\
\\
       & = & [a^\#_{1,1}, a^\#_{2,2}, \ldots, a^\#_{n,n}],
\end{array}$$
where the last equality is due to Lemma \ref{new.12000}. This, together with
(\ref{pi_alpha}), yield (\ref{Aginv_diag_ii}).
%and that
%\be
%\label{Lem3_pf2}
%\xi_{\alpha_1}\pi_{\alpha_1}^tA^\#[\alpha_1,
%  \alpha_2]+\xi_{\alpha_2}\pi_{\alpha_2}^tA^\#[\alpha_2]\e 0.
%\ee
%On the other hand, by (\ref{Lem3_pf1}) and Lemmas \ref{Lem1} and
%\ref{Lem2}, we have that
%$$\begin{array}{l}
%\xi_{\alpha_1}\pi_{\alpha_1}^tA^\#[\alpha_1]+
%\xi_{\alpha_2}\pi_{\alpha_2}^tA^\#[\alpha_2, \alpha_1]\\[9pt]
%\ \\
%\e \xi_{\alpha_1}\pi_{\alpha_1}^tJ(A^\#[\alpha_1])_d+
%\xi_{\alpha_2}\pi_{\alpha_2}^tJ(A^\#[\alpha_1])_d-
%\xi_{\alpha_1}\pi_{\alpha_1}^tU[\alpha_1]-\xi_{\alpha_2}
%\pi_{\alpha_2}^tU[\alpha_2,
%\alpha_1]\\[9pt]
%\ \\
%\e (\xi_{\alpha_1}+\xi_{\alpha_2})(a^\#_{1,1},
%a^\#_{2,2}, \ldots,
%a^\#_{|\alpha_1|,|\alpha_1|})-\xi_{\alpha_1}
%\pi_{\alpha_1}^tU[\alpha_1]-\xi_{\alpha_2}\pi_{\alpha_2}^tU[\alpha_2,
%\alpha_1]\\[9pt]
%\ \\
% \e (a^\#_{1,1}, a^\#_{2,2}, \ldots,
%a^\#_{|\alpha_1|,|\alpha_1|})-\xi_{\alpha_1}
%\pi_{\alpha_1}^tU[\alpha_1]-\xi_{\alpha_2}\pi_{\alpha_2}^tU[\alpha_2,
%\alpha_1].
%\end{array}$$
%Thus, by (\ref{Lem3_pf1}), we find that
%\be
%(a^\#_{1,1}, a^\#_{2,2}, \ldots,
%a^\#_{|\alpha_1|,|\alpha_1|})
%\e
%\xi_{\alpha_1}\pi_{\alpha_1}^tU[\alpha_1]+
%\xi_{\alpha_2}\pi_{\alpha_2}^tU[\alpha_2,
%\alpha_1].
%\ee
%Similarly, one can show that
%\be
%(a^\#_{|\alpha_1|+1,|\alpha_1|+1},
%  a^\#_{|\alpha_1|+2,|\alpha_1|+2}, \ldots, a^\#_{n,n})\e
%\xi_{\alpha_1}\pi_{\alpha_1}^tU[\alpha_1,
%\alpha_2]+\xi_{\alpha_2}\pi_{\alpha_2}^tU[\alpha_2].
%\ee
\cvd

Suppose next that $A^\#$ and $U$ are partitioned in conformity with
$T$ in (\ref{Par_T_k}).
Our next lemma concerns the relationship between the blocks of $A^\#$
and those of $U$. 

\begin{1}
\label{new.13000}
For $i=1,2, \ldots, k$,
\be
\label{new.14000}
-A^\#[\alpha_i]+J(A^\#[\alpha_i])_d=U[\alpha_i]
\ee
and
\be
\label{new.15000}
-A^\#[\langle n \rangle \backslash \alpha_i, \alpha_i]+J(A^\#[\alpha_i])_d=
U[\langle n \rangle \backslash \alpha_i, \alpha_i].
\ee
\end{1}

{\em Proof.}
Similar to the proof of Lemma \ref{Lem3}, we see that
$$\begin{array}{rcl}
U & = & \Big[[I-A^\#+J(A^\#)_d](W_d)^{-1}-(W_d)^{-1}\Big]W_d\\
\\
       & = & -A^\#+J(A^\#)_d.
\end{array}$$
%In other words, $U$ can be thought of as a rank--one modification
%of $-A^\#$.\\

Without loss of generality, we consider here the case when $i=1$.
We put $\beta=\langle n \rangle \backslash \alpha_1$ for brevity.
On partitioning $U$, $A^\#$, and $J$ in conformity with $T$,
we obtain that
$$\begin{array}{rcl}
\left[\begin{array}{ccc}
U[\alpha_1] &\  &U[\alpha_1, \beta]\\
&  & \\
U[\beta, \alpha_1] & & U[\beta]
\end{array}\right] & = & -\left[\begin{array}{ccc}
A^\#[\alpha_1] & &A^\#[\alpha_1, \beta]\\
& & \\
A^\#[\beta, \alpha_1] & & A^\#[\beta]
\end{array}\right]\\
\\
 & & \hspace*{1cm}+\left[\begin{array}{ccc}
J(A^\#[\alpha_1])_d & &J(A^\#[\beta])_d\\
& & \\
J(A^\#[\alpha_1])_d & &J(A^\#[\beta])_d
\end{array}\right],
\end{array}$$
from which (\ref{new.14000}) and (\ref{new.15000}) follow.
\cvd
 
%With Lemmas \ref{Lem3} and \ref{new.13000},

We are now in a position to introduce our main results. For that
purpose recall that
$P_{\alpha_i}$ is the Perron complement of $T[\alpha_i]$, $B_{\alpha_i}
:=I-P_{\alpha_i}$,
$\xi_{\alpha_i}$ is the $i$--th coupling factor,
$W_{\alpha_i}:=e\pi_{\alpha_i}^t$, where $\pi_{\alpha_i}$ is the
normalized left Perron vector of $P_{\alpha_i}$, and $V_{\alpha_i}$ is
the skew--symmetric matrix given in (\ref{V_i}). In Lemma \ref{new.13000}
we showed how the blocks of $\as$ are related to the corresponding
blocks of $U$. We shall show next how the blocks
of $U$ can be obtained from the group inverses of the
$B_{\alpha_i}$'s   starting with the diagonal
blocks of  $U$.
 

\begin{2}
\label{Thm4}
For $i=1, 2, \ldots, k$,
\be
\label{Aginv_diag_level_k}
U[\alpha_i] \e -B_{\alpha_i}^\#+
J(B_{\alpha_i}^\#)_d+
\xi_{\alpha_i}V_{\alpha_i}(W_{\alpha_i})_d.
\ee
\end{2}


{\em Proof.}
%For simplicity's sake we shall take $k=2$ as the proof readily
%extends to all $k\geq 2$. Furthermore,
It
suffices to show the conclusion for the case when
$i=1$.  By Lemma \ref{MFP} and  on
partitioning $M$, $A^\#$,
and $W$ in conformity with $T$, we have, using \reff{pi_alpha}, that
\begin{eqnarray}
\label{Thm1_pf1}
M[\alpha_1] & = &
\Big[I-A^\#[\alpha_1]+J(A^\#[\alpha_1])_d\Big][(W[\alpha_1])_d]^{-1}
\nonumber \\
\ & & \nonumber \\
        & = &
\frac{1}{\xi_{\alpha_1}}\Big[I-A^\#[\alpha_1]+
J(A^\#[\alpha_1])_d\Big][(W_{\alpha_1})_d]^{-1}.
\end{eqnarray}
       On the other hand, by
       (\ref{MFP_alpha}) and
(\ref{M_diag_i}), we find that
\be
\label{Thm1_pf2}
M[\alpha_1]\e \frac{1}{\xi_{\alpha_1}}
\Big[I-B_{\alpha_1}^\#+J(B_{\alpha_1}^\#)_d\Big]
[(W_{\alpha_1})_d]^{-1}+V_{\alpha_1}.
\ee
It thus follows from (\ref{Thm1_pf1}) and (\ref{Thm1_pf2}) that
$$\frac{1}{\xi_{\alpha_1}}\Big[-A^\#[\alpha_1]+
J(A^\#[\alpha_1])_d\Big][(W_{\alpha_1})_d]^{-1}
\e \frac{1}{\xi_{\alpha_1}}\Big[-B_{\alpha_1}^\#
+J(B_{\alpha_1}^\#)_d\Big][(W_{\alpha_1})_d]^{-1}+V_{\alpha_1},$$
which, by (\ref{new.14000}), can be reduced to
$$\begin{array}{rcl}
U[\alpha_1] & = & -A^\#[\alpha_1]+J(A^\#[\alpha_1])_d\\
\\
       & \e &
-B_{\alpha_1}^\#+J(B_{\alpha_1}^\#)_d+\xi_{\alpha_1}
V_{\alpha_1}(W_{\alpha_1})_d.
\end{array}$$
This completes the proof.
\cvd


Having determined a representation for the diagonal blocks of $U$, we
now determine a representation
for the off--diagonal blocks of $U$.


\begin{2}
\label{Thm5}
For $i=1, 2, \ldots, k$,
\be
\label{Aginv_off_level_k}
\begin{array}{l}
U[\langle n \rangle \backslash \alpha_i, \alpha_i]
= (I-T[\langle n \rangle \backslash \alpha_i])^{-1}
\Big[T[\langle n \rangle
\backslash \alpha_i,
\alpha_i]U[\alpha_i]+\xi_{\alpha_i}J(W_{\alpha_i})_d\Big].
\end{array}
\ee
\end{2}

{\em Proof.}
It suffices for the sake of simplicity to set
$i=1$ and $\beta=\langle n \rangle \backslash \alpha_1$. Thus what we need
to show is the following:

$$
\begin{array}{l}
U[\beta, \alpha_1]
= (I-T[\beta])^{-1}
\Big[T[\beta,
\alpha_1]U[\alpha_1]+\xi_{\alpha_1}J(W_{\alpha_1})_d\Big].
\end{array}
$$

Again, by Lemma \ref{MFP} and  on
partitioning $M$, $A^\#$,
and $W$ in conformity with $T$, we have, using \reff{pi_alpha}, that
\begin{eqnarray}
\label{Thm2_pf1}
M[\beta, \alpha_1] & = & \Big[-A^\#[\beta,
\alpha_1]+J(A^\#[\alpha_1])_d\Big][(W[\alpha_1])_d]^{-1} \nonumber \\
& & \nonumber \\
        & = & \frac{1}{\xi_{\alpha_1}}\Big[-A^\#[\beta,
        \alpha_1]+J(A^\#[\alpha_1])_d\Big][(W_{\alpha_1})_d]^{-1}.
\end{eqnarray}
        On the other hand,
by (\ref{MFP_alpha}) and (\ref{M_diag_i}), we see that
\begin{eqnarray}
M[\alpha_1]-(M[\alpha_1])_d & = &
\frac{1}{\xi_{\alpha_1}}\Big[M_{\alpha_1}-(M_{\alpha_1})_d\Big]+
V_{\alpha_1}
\nonumber \\
& & \nonumber \\
        & = & \frac{1}{\xi_{\alpha_1}}
\Big[-B_{\alpha_1}^\#+J(B_{\alpha_1}^\#)_d\Big]
[(W_{\alpha_1})_d]^{-1}+V_{\alpha_1},
\nonumber
\end{eqnarray}
which, together with (\ref{M_off_i}), yield that
\begin{eqnarray}
\label{Thm2_pf2}
M[\beta, \alpha_1] & = & \frac{1}{\xi_{\alpha_1}}(I-T[\beta])^{-1}
\Big[T[\beta,
\alpha_1][-B_{\alpha_1}^\#+J(B_{\alpha_1}^\#)_d][(W_{\alpha_1})_d]^{-1}
\nonumber
\\
& & \nonumber \\
        & & \hspace*{2cm}+\xi_{\alpha_1}T[\beta,
\alpha_1]V_{\alpha_1}+\xi_{\alpha_1}J\Big] \nonumber \\
& & \nonumber \\
        & = & \frac{1}{\xi_{\alpha_1}}(I-T[\beta])^{-1}\Big[T[\beta,
\alpha_1]U[\alpha_1]
+\xi_{\alpha_1}J(W_{\alpha_1})_d\Big][(W_{\alpha_1})_d]^{-1}. \nonumber \\
        & &
\end{eqnarray}
The conclusion follows now from (\ref{new.15000}), (\ref{Thm2_pf1}), and
(\ref{Thm2_pf2}).
\cvd
 

Theorems \ref{Thm4} and \ref{Thm5} make it clear that $U$ can be completely
determined by quantities directly related to Perron complementation.
Furthermore, as shown by our next theorem, $A^\#$ can be completely
determined by $U$ and thus also by quantities directly related to Perron
complementation.
 

\begin{2}
\label{Thm6}
For $i=1, 2, \ldots, k$, the diagonal blocks of $\as$ are given by:
\be
\label{Aginv_diag_new_level_k}
\begin{array}{cl} A^\#[\alpha_i]  &  \e
e[\xi_{\alpha_1}\pi_{\alpha_1}^t,
\xi_{\alpha_2}\pi_{\alpha_2}^t, \ldots, \xi_{\alpha_k}\pi_{\alpha_k}^t]
~U[\langle n \rangle, \alpha_i]-U[\alpha_i]\\
     \ & \\
\ &
      \e \displaystyle e\sum_{\ell=1}^k \xi_{\alpha_\ell}\pi_{\alpha_\ell}^t~
U[\alpha_\ell, \alpha_i]-U[\alpha_i].
\end{array}
\ee
The off--diagonal blocks of $\as$ are given as follows: for $j\neq
i$, $1\leq i,j\leq k$,
\be
\label{Aginv_off_new_level_k}
\as[\alpha_j, \alpha_i] \e
e\sum_{\ell=1}^k\xi_{\alpha_\ell}\pi_{\alpha_\ell}^t~U[\alpha_\ell,
\alpha_i]-U[\alpha_j, \alpha_i].
\ee
\end{2}


%\bp
%As was the case in the proof of the two previous theorem, to
%keep the proof technically simple, we perform it for the case $k=2$.
%In this case we are required to show that
%  For $i=1, 2$,
%\be
%\label{Aginv_diag_new}
%A^\#[\alpha_i]\e e(\xi_{\alpha_1}\pi_{\alpha_1}^t,
%\xi_{\alpha_2}\pi_{\alpha_2}^t)~U[\langle n \rangle,
%  \alpha_i]-U[\alpha_i]
%\ee
%and
%\be
%\label{Aginv_off_new}
%A^\#[\langle n \rangle \backslash \alpha_i, \alpha_i]\e
%e(\xi_{\alpha_1}\pi_{\alpha_1}^t,
%\xi_{\alpha_2}\pi_{\alpha_2}^t)~U[\langle n \rangle,
%\alpha_i]-U[\langle n \rangle \backslash \alpha_i, \alpha_i].
%\ee


{\em Proof.}
 From (\ref{new.14000}) we know that
$$A^\#[\alpha_i]=J(A^\#[\alpha_i])_d-U[\alpha_i].$$
On the other hand, from (\ref{Aginv_diag_ii}), we have that
\be
\label{new.16000}
J(A^\#[\alpha_i])_d=e[\xi_{\alpha_1}\pi_{\alpha_1}^t,
\xi_{\alpha_2}\pi_{\alpha_2}^t, \ldots,
\xi_{\alpha_k}\pi_{\alpha_k}^t]~U[\langle n \rangle,
       \alpha_i].
\ee
Thus (\ref{Aginv_diag_new_level_k}) follows. 

Similarly, using (\ref{new.15000}) and (\ref{new.16000}), we see that
(\ref{Aginv_off_new_level_k}) holds.
\cvd


%\begin{3}
%\label{Lem4}
%For $i=1, 2$,
%\be
%\label{J_Aginv_diag_ii}
%J(A^\#[\alpha_i])_d\e e(\xi_{\alpha_1}\pi_{\alpha_1}^t,
%\xi_{\alpha_2}\pi_{\alpha_2}^t)~U[\langle n \rangle, \alpha_i].
%\ee
%\end{3}

%The above lemma shows how each diagonal block of $A^\#$ depends on
%the group inverse of
%the corresponding $B_{\alpha_i}$. Subsequently it will become clear
%that the term
%$J(A^\#[\alpha_i])_d$ in (\ref{Aginv_diag}) can actually be obtained
%without recourse to the
%diagonal entries of
%$A^\#[\alpha_i]$.\\

Theorems \ref{Thm4}, \ref{Thm5}, and \ref{Thm6} clearly illustrate how the
blocks of $A^\#$ can be assembled from quantities arising from Perron
complementation, namely from $\xi_{\alpha_i}$, $\pi_{\alpha_i}$,
$V_{\alpha_i}$,
and $B_{\alpha_i}^\#$. In the next
section we shall use this important fact to construct a
parallel algorithm for computing $A^\#$. 

We comment that according to \cite[Formulae (7) and (19)]{NeXu03},
if $\alpha_1$ is chosen
        to be $\{1, 2, \ldots, n-1\}$, then
\be
A^\#[\alpha_1]\e F+\xi_{\alpha_1}\Big[\mu
W_{\alpha_1}-FW_{\alpha_1}-W_{\alpha_1}F\Big]
\ee
and
\be
B_{\alpha_1}^\#\e
F+\frac{\mu}{\xi_{\alpha_1}}W_{\alpha_1}-FW_{\alpha_1}-W_{\alpha_1}F,
\ee
where $F=(I-T[\alpha_1])^{-1}$ and where
$\mu=\xi_{\alpha_1}\pi_{\alpha_1}^tFe$. This
result, which implies the close connection between $A^\#[\alpha_1]$
and $B_{\alpha_1}^\#$, can be
regarded as a special case of our Theorems \ref{Thm4}, \ref{Thm5}, and
\ref{Thm6}. 






Consider the case when $T$ is not only irreducible and
stochastic, but also $d$--periodic, that is,
\be
\label{T_d}
T=\left[\begin{array}{cccccc}
0 & T_1 & 0 & \cdots & \cdots & 0\\
0 & 0 & T_2 & 0 & \cdots & 0\\
\vdots & \vdots & \ddots & \ddots & \ddots & \vdots\\
\vdots & \vdots & & \ddots & \ddots & 0\\
0 & 0 & \cdots & \cdots & \ddots & T_{d-1}\\
T_d & 0 & \cdots & \cdots & \cdots & 0
\end{array}\right],
\ee
where the diagonal zero blocks are square and where $(I-T)^\#$ is
partitioned conformably with $T$ in (\ref{T_d}). For this case Kirkland
\cite[Theorem 1]{Kirk95} has shown how to compute the
blocks of $(I-T)^\#$ in terms of $(I-P_j)^\#$, where
$P_1:=T_1T_2 \cdots T_d$ and where, for $j=2, 3, \ldots, d$,
$P_j:=T_jT_{j+1} \cdots T_dT_1 \cdots T_{j-1}$.
It can be readily verified that for each $j$, $P_j$ is indeed
the Perron complement of the $j$--th diagonal block of $T$. This result
can also be regarded as a particular case of our Theorems \ref{Thm4},
\ref{Thm5},
and \ref{Thm6}. 

We finally remark that Theorems \ref{Thm4}, \ref{Thm5}, and
\ref{Thm6} apply to the
case when any $\alpha_i$
consists of nonconsecutive, but increasing, indices, provided that
$\alpha_1, \alpha_2, \ldots, \alpha_k$ form a partition of $\langle n
\rangle$.

%\begin{2}
%\label{Thm3}
%For $i=1, 2, \ldots, k$,
%\be
%\label{Aginv_diag_levelk_new}
%A^\#[\alpha_i]\e e(\xi_{\alpha_1}\pi_{\alpha_1}^t,
%\xi_{\alpha_2}\pi_{\alpha_2}^t, \ldots, \xi_{\alpha_k}
%\pi_{\alpha_k}^t)~U[\langle
%n \rangle,
%\alpha_i]-U[\alpha_i].
%\ee
%\end{2}

%\begin{2}
%\label{Thm4}
%For $i=1, 2, \ldots, k$,
%\be
%\label{Aginv_off_levelk_new}
%A^\#[\langle n \rangle \backslash \alpha_i,
%  \alpha_i]\e e(\xi_{\alpha_1}\pi_{\alpha_1}^t,
%\xi_{\alpha_2}\pi_{\alpha_2}^t, \ldots,
%\xi_{\alpha_k}\pi_{\alpha_k}^t)~U[\langle n \rangle,
%\alpha_i]-U[\langle n \rangle \backslash
%\alpha_i, \alpha_i].
%\ee
%\end{2}


\section{Parallel Algorithm}
\label{sec.4}
\setcounter{equation}{0}

In this section we shall provide a parallel algorithm for the
efficient computation of  $A^\#$ via Perron complementation.
The algorithm will be illustrated mainly by partitioning $T$
into a $2 \times 2$ block matrix as follows:
\be
\label{Par_T_2}
T\e \left[\begin{array}{cc}
T[\alpha_1] & T[\alpha_1, \alpha_2]\\
T[\alpha_2, \alpha_1] & T[\alpha_2]
\end{array}\right],
\ee
where $\alpha_1$ and $\alpha_2$, both nonempty, form a partition of
$\langle n \rangle$. 
%The extension of the algorithm to the general $k \times k ~(k > 2)$
%block form is easily achieved.

We begin the procedure by computing the Perron
complements $P_{\alpha_1}$ and $P_{\alpha_2}$. According to
\reff{Per_Com}, this requires certain
matrix inversions. We retain
the results of these   inversions since
they will be needed later in the  computation of  $V_{\alpha_1}$,
$V_{\alpha_2}$, and in the  computation of the
off--diagonal blocks of $U$ (see \reff{V_i} and
\reff{Aginv_off_level_k}, respectively) too. As shown in the proof of Theorem
\ref{Thm6},
the blocks of
$A^\#$ are determined by the blocks  of
$U$, the coupling factors $\xi_{\alpha_1}$ and $\xi_{\alpha_2}$,
and the normalized left Perron vectors $\pi_{\alpha_1}$
and $\pi_{\alpha_2}$. Among these quantities, each
     $\pi_{\alpha_i}$ can
be computed separately from
its respective $P_{\alpha_i}$, while
$\xi_{\alpha_1}$ and $\xi_{\alpha_2}$ can be obtained from
the coupling matrix $C$ once $\pi_{\alpha_1}$ and $\pi_{\alpha_2}$
are known. 

Continuing, concerning
the blocks of $U$, each diagonal
block $U[\alpha_i]$ is determined by $B_{\alpha_i}^\#$,
$V_{\alpha_i}$, $\xi_{\alpha_i}$, and $W_{\alpha_i}$
according to (\ref{Aginv_diag_level_k}).
Clearly each
$B_{\alpha_i}^\#$ can be computed separately from the corresponding
$P_{\alpha_i}$. As
soon as $B_{\alpha_i}^\#$
becomes available, $V_{\alpha_i}$ can be obtained
immediately from (\ref{V_i}).
Having found
$U[\alpha_i]$, we proceed with (\ref{Aginv_off_level_k}) so as to determine
$U[\langle n \rangle \backslash
\alpha_i, \alpha_i]$.

%\bd
%\label{fig.1}
%\begin{array}{c}
%\includegraphics[scale=.80]{ginvalgo_fig1.eps}\\
%\ \\
%\mbox{Figure\ 1: Computation on the Perron Complement
%$P_{\alpha_i}$}
%\end{array}
%\ed

\begin{figure}[ht]
%\label{fig.1}
\begin{center}
\vspace*{-1mm} \mbox{ \hspace*{-5mm}
\epsfig{file=ginvalgo_fig1.eps,height=45mm ,width=70mm ,clip=}}
\caption{Computation on the Perron Complement $P_{\alpha_i}$}
\end{center}
\end{figure}


%\vspace{.1in}


In summary, with a $2 \times 2$ partitioning scheme and Perron
complementation, the
        computation of $A^\#$ can be implemented by computing the following
components roughly in the
order as they appear: (i) $P_{\alpha_1}$ and $P_{\alpha_2}$; (ii)
$\pi_{\alpha_1}$ and
$\pi_{\alpha_2}$; (iii) $B_{\alpha_1}^\#$ and $B_{\alpha_2}^\#$; (iv)
$C$, $\xi_{\alpha_1}$, and
$\xi_{\alpha_2}$; (v) $V_{\alpha_1}$ and $V_{\alpha_2}$; (vi)
$U[\alpha_1]$ and $U[\alpha_2]$; and
(vii) $U[\alpha_2, \alpha_1]$ and $U[\alpha_1, \alpha_2]$. Each of
these components, except (iv),
consists of two separate subcomponents that can be computed concurrently and in
parallel. In addition,  steps (ii) and
(iii) may also be executed in parallel. The flow of the computation
on each
$P_{\alpha_i}$, as illustrated in Figure 4.1, can obviously be carried
out independently, with the
computation of $\xi_{\alpha_1}$ and $\xi_{\alpha_2}$ being the
only exception. 

According to our Theorems \ref{Thm4}, \ref{Thm5}, and \ref{Thm6}, the
above algorithm can be extended to the general $k \times k ~(k>2)$
partitioning scheme where $T$ is partitioned as in (\ref{Par_T_k}),
which would be an appropriate choice when the computation of $A^\#$ is to
be distributed over $k$ processors.
Specifically, we begin
with the computation of the Perron complements $P_{\alpha_i}$ for
$i=1, 2, \ldots, k$, then for each $i$ we proceed to calculating
$B_{\alpha_i}^\#$, $\pi_{\alpha_i}$ and $\xi_{\alpha_i}$, $V_{\alpha_i}$,
$U[\alpha_i]$, and $U[\langle n \rangle \backslash \alpha_i, \alpha_i]$ in the
order as
shown in Figure 4.1, and finally we recover the blocks of $A^\#$ using formulae
(\ref{Aginv_diag_new_level_k}) and (\ref{Aginv_off_new_level_k}).
Alternatively, similar to what was suggested in \cite{Meye89}, a higher level
partitioning scheme can also be achieved by following successive lower level
partitionings on the Perron complements. For example, we may partition $T$ into
a $2 \times 2$ block form and construct the Perron complements $P_{\alpha_1}$
and $P_{\alpha_2}$, but then for each $i$, we may compute the group inverse
$B_{\alpha_i}^\#$ using our parallel algorithm by further partitioning the
corresponding $P_{\alpha_i}$ into a $2 \times 2$ block form. In other words,
we may compute $B_{\alpha_i}^\#$ on the Perron complements of $P_{\alpha_i}$,
rather than directly computing it on $P_{\alpha_i}$.
 

%Consider, for example, an $8 \times 8$ irreducible stochastic matrix:
%\footnote{All numbers in this example are shown to the fourth decimal place.}
%$$T \e \left(\begin{array}{cccc|cccc}
%.1719 & .0015 & .0378 & .2635 & .1493 & .2148 & .0604 & .1007\\
%.0542 & .0535 & .1831 & .0544 & .2188 & .2063 & .2059 & .0238\\
%.0909 & .2462 & .0720 & .1019 & .2498 & .1573 & .0432 & .0386\\
%.1660 & .2348 & .1939 & .1006 & .0586 & .0286 & .0420 & .1756\\
%\hline
%.1036 & .0811 & .1431 & .2332 & .2592 & .0032 & .0931 & .0834\\
%.0997 & .0892 & .1598 & .1872 & .1382 & .2282 & .0660 & .0317\\
%.1453 & .0080 & .1060 & .2113 & .0710 & .1226 & .0831 & .2528\\
%.1583 & .2875 & .0756 & .0628 & .0028 & .2456 & .0586 & .1087
%\end{array}\right),$$
%with the indicated $2 \times 2$ partition. The Perron complements are
%found to be
%$$P_{\alpha_1} \e \left(\begin{array}{cccc}
%.2865 & .1123 & .1643 & .4369\\
%.2011 & .1674 & .3425 & .2890\\
%.1942 & .3380 & .1922 & .2756\\
%.2389 & .3231 & .2561 & .1818
%\end{array}\right)$$ and $$P_{\alpha_2}\e \left(\begin{array}{cccc}
%.4491 & .1676 & .1901 & .1932\\
%.3229 & .3877 & .1591 & .1303\\
%.2255 & .2617 & .1571 & .3558\\
%.2006 & .4307 & .1780 & .1906
%\end{array}\right)$$ with normalized left Perron vectors
%$$\pi_{\alpha_1}\e (.2300, .2407, .2404, .2888)^t \ \ {\rm and}
%  \ \ \pi_{\alpha_2}\e (.3221, .3037, .1725, .2016)^t.$$
%The coupling matrix is found to be
%$$C\e \left(\begin{array}{cc}
%.5160 & .4840\\
%.5425 & .4575
%\end{array}\right),$$
%from which the coupling factors are found to be $\xi_{\alpha_1}=.5285$
%and $\xi_{\alpha_2}=.4715$, while the group inverses corresponding to
%the Perron complements are
%found to be
%$$B_{\alpha_1}^\#\e \left(\begin{array}{rrrr}
%.8383 & -.3654 & -.3280 & -.1449\\
%-.2625 & .7030 & -.1463 & -.2942\\
%-.2696 & -.1498 & .7250 & -.3057\\
%-.2244 & -.1701 & -.2204 & .6150
%\end{array}\right)$$ and $$B_{\alpha_2}^\#\e \left(\begin{array}{rrrr}
%.8200 & -.4737 & -.1505 & -.1958\\
%-.3086 & .7757 & -.1870 & -.2801\\
%-.4520 & -.3086 & .8108 & -.0502\\
%-.4583 & -.1477 & -.1717 & .7777
%\end{array}\right).$$
%Next the skew--symmetric matrices are found to be
%$$V_{\alpha_1}\e \left(\begin{array}{rrrr}
%0 & -.3265 & -.0494 & .2712\\
%.3265 & 0 & .2771 & .5976\\
%.0494 & -.2771 & 0 & .3205\\
%-.2712 & -.5976 & -.3205 & 0
%\end{array}\right)$$ and $$V_{\alpha_2}\e \left(\begin{array}{rrrr}
%0 & .0748 & .1798 & .0917\\
%-.0748 & 0 & .1050 & .0168\\
%-.1798 & -.1050 & 0 & -.0882\\
%-.0917 & -.0168 & .0882 & 0
%\end{array}\right).$$ From the $B_{\alpha_i}$'s,
%the $\xi_{\alpha_i}$'s,
%the $\pi_{\alpha_i}$'s, and the $V_{\alpha_i}$'s, the
% diagonal blocks of $U$
%are found to be
%$$U[\alpha_1]\e \left(\begin{array}{rrrr}
%0 & 1.0269 & 1.0468 & .8013\\
%1.1405 & 0 & .9065 & 1.0004\\
%1.1139 & .8175 & 0 & .9696\\
%1.0298 & .7971 & .9047 & 0
%\end{array}\right)$$ and $$U[\alpha_2]\e \left(\begin{array}{rrrr}
%0 & 1.2601 & .9760 & .9823\\
%1.1172 & 0 & 1.0064 & 1.0595\\
%1.2447 & 1.0693 & 0 & .8196\\
%1.2644 & .9210 & .9897 & 0
%\end{array}\right),$$
%and then the off--diagonal blocks of $U$ are found to be
%$$U[\alpha_2, \alpha_2]\e \left(\begin{array}{rrrr}
%1.0797 & .9410 & .9443 & .8447\\
%1.0937 & .9455 & .9195 & .8863\\
%1.0261 & .9937 & .9943 & .8802\\
%1.0436 & .7795 & 1.0064 & 1.0233
%\end{array}\right)$$ and $$U[\alpha_1, \alpha_2]\e
%\left(\begin{array}{rrrr} 1.1469 & 1.0107 & 1.0248 & .9707\\
%1.0311 & 1.0322 & .8668 & 1.0505\\
%.9815 & 1.0820 & 1.0036 & 1.0599\\
%1.2017 & 1.1602 & 1.0110 & .9235
%\end{array}\right).$$
%Now from the $\xi_{\alpha_i}$'s, the $\pi_{\alpha_i}$'s, and $U$, the
%diagonal entries of
%  $A^\#$ are found to be
%$$(.9471, .7837, .8323, .7720, .9602, .9347, .9031, .8949).$$
%Finally, by Theorems \ref{Thm1} and \ref{Thm2}, the group inverse
%$A^\#$ is found to be
%$$\left(\begin{array}{rrrr|rrrr}
%.9471 & -.2432 & -.2144 & -.0293 & -.1867 & -.0760 & -.1216 & -.0759\\
%-.1934 & .7837 & -.0742 & -.2284 & -.0709 & -.0975 & .0364 & -.1556\\
%-.1668 & -.0338 & .8323 & -.1976 & -.0213 & -.1473 & -.1005 & -.1651\\
%-.0827 & -.0134 & -.0724 & .7720 & -.2415 & -.2255 & -.1078 & -.0286\\
%\hline
%-.1325 & -.1573 & -.1119 & -.0727 & .9602 & -.3254 & -.0729 & -.0874\\
%-.1466 & -.1618 & -.0871 & -.1143 & -.1570 & .9347 & -.1033 & -.1646\\
%-.0790 & -.2101 & -.1620 & -.1082 & -.2844 & -.1346 & .9031 & .0752\\
%-.0965 & .0042 & -.1741 & -.2513 & -.3042 & .0136 & -.0866 & .8949
%\end{array}\right).$$

It is natural to ask whether the above parallel algorithm for
computing $A^\#$ via
        Perron complementation is  less costly
than the direct computation of  $A^\#$,
considering that there are quite a few quantities, though all are
smaller than $n$ in size,  to compute.
To answer this question, we shall estimate the asymptotic number of
multiplications necessary to
implement the parallel algorithm and compare it with the case without
parallelism.

It should be  mentioned that for
general matrices,
there are actually very few numerically
viable methods for computing $A^\#$ because of the issue of numerical
instability. Specifically,  problems might arise in determining the
bases for $R(A)$ and $N(A)$ (\cite{BeGr03, CaMe91}) or the
characteristic polynomial of $A$ and the resolvent $(zI-A)^{-1}$
(\cite{Grev72, Hart76}). Under our assumption on $A$, namely that $A$ is an
irreducible singular M--matrix, however, there is a
quite reliable method for computing $A^\#$ proposed by Meyer
\cite[Section 5]{Meye75}, which can be implemented using the
conventional Gaussian eliminations on nonsingular matrices.
Here we shall adopt this method while counting the asymptotic
numbers of multiplications.


According to Meyer \cite[Theorem 5.5 and Table 2]{Meye75},
if $A^\#$ is computed directly from the formula
\be
\label{Aginv_formula}
A^\#\e (A+W)^{-1}-W
\ee
and if $\pi$ is computed first, then the number of multiplications
required is roughly $4n^3/3$. 

Suppose now that $n=2m$ and that $\alpha_1=\{1, 2, \ldots, m\}$ and
$\alpha_2=\{m+1, m+2, \ldots, n\}$. As shown
in Figure 4.1, the total
        number of multiplications required for the computation on each
$P_{\alpha_i}$ can be counted as
follows:
 

\begin{itemize}
\item[(i)]{$P_{\alpha_i}$. To find $(I-T[\langle n \rangle
        \backslash \alpha_i])^{-1}T[\langle n \rangle \backslash \alpha_i,
\alpha_i]$, it requires
$4m^3/3$ multiplications to solve
the matrix equation
$(I-T[\langle n \rangle \backslash \alpha_i])X=T[\langle n \rangle
\backslash \alpha_i,
\alpha_i]$ with Gaussian eliminations. An additional amount of $m^3$
multiplications is then needed
to premultiply $(I-T[\langle n
\rangle \backslash \alpha_i])^{-1}T[\langle n \rangle \backslash
\alpha_i, \alpha_i]$ by
$T[\alpha_i,\langle n \rangle \backslash \alpha_i]$.}
\item[(ii)]{$\pi_{\alpha_i}$ and $B_{\alpha_i}^\#$. Based on the result
in \cite{Meye75}, it requires $4m^3/3$ multiplications if
$\pi_{\alpha_i}$ is computed first and
then $B_{\alpha_i}^\#$ is computed from a formula similar to
(\ref{Aginv_formula}). We comment
that the computation of $\xi_{\alpha_1}$ and $\xi_{\alpha_2}$
is trivial and does not
require $O(m^3)$
multiplications.}
\item[(iii)]{$V_{\alpha_i}$. Due to the particular structure
       of $V_{\alpha_i}$,
        it is enough to compute the first column of the rank--one matrix
$B_{\alpha_i}^\#T[\alpha_i,\langle n \rangle \backslash
\alpha_i](I-T[\langle n \rangle \backslash
\alpha_i])^{-1}J$. This does not require $O(m^3)$ multiplications
since the $LU$ factorization in
(i) can be retained.}
\item[(iv)]{$U[\alpha_i]$. Clearly this does not require $O(m^3)$
multiplications.}
\item[(v)]{$U[\langle n \rangle \backslash \alpha_i, \alpha_i]$. The
computation of
        $\xi_{\alpha_i}(I-T[\langle n \rangle \backslash
\alpha_i])^{-1}J(W_{\alpha_i})_d$ does not
require $O(m^3)$ multiplications for exactly the same reason as
mentioned in (iii). It requires $m^3$
multiplications, however, to postmultiply $(I-T[\langle n
\rangle \backslash
\alpha_i])^{-1} \times $ $T[\langle n \rangle \backslash \alpha_i, \alpha_i]$ 
by
$U[\alpha_i]$.}
\item[(vi)]{$A^\#[\alpha_i]$ and $A^\#[\langle n \rangle \backslash
\alpha_i,\alpha_i]$.
        These can be obtained without multiplication operations from
(\ref{new.14000}) and
(\ref{new.15000}), respectively, when $J(A^\#[\alpha_i])_d$ is
known. Note that, according to (\ref{new.16000}), the computation of
$J(A^\#[\alpha_i])_d$ does not require
$O(m^3)$ multiplications.}
\end{itemize}

\vspace{.1in}

 From (i) through (vi), we conclude that the number of multiplications
necessary for implementing the parallel algorithm for computing
$A^\#$ is roughly
$28m^3/3=7n^3/6$. On the other hand,
to compute $A^\#$
directly from (\ref{Aginv_formula})
requires $4n^3/3=8n^3/6$
multiplications. Therefore the parallel algorithm
actually saves approximately
$1/8$ or 12.5\% of multiplication operations. 


\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\ \ \ \ \ \ $n$ \ \ \ \ \ \ & \ \ \ \ \ \ flops$_d$ \ \
       \ \ \ \ & \ \ \ \ \ \
        flops$_p$ \ \ \ \ \ \ & (flops$_d-$flops$_p$)/flops$_d$ \\
\hline
50 & 3,489,825 & 1,796,824 & 48.5\%\\
100 & 28,126,945 & 14,066,448 & 50.0\%\\
200 & 221,017,525 & 108,340,394 & 51.0\%\\
400 & 1.7449 $\times 10^9$ & 8.4711 $\times 10^8$ & 51.5\%\\
800 & 1.3551 $\times 10^{10}$ & 6.7867 $\times 10^9$ & 49.9\%\\
1600 & 1.0575 $\times 10^{11}$ & 5.3352 $\times 10^{10}$ & 49.5\%\\
\hline
\end{tabular}
\end{center}
\vspace{.1in}

\centerline{Table 1: Results of Numerical Tests}
\vspace{.15in}

We have tested with MATLAB several examples using randomly generated
dense matrices and counted the number of flops
with MATLAB's built--in
function {\tt flops}. The results are given in Table 1, where flops$_p$
        stands for the total number
of flops used in  the parallel algorithm for computing $A^\#$,
while flops$_d$ stands for
that from directly computing $A^\#$ by (\ref{Aginv_formula}).



The data in Table 1 confirms the efficiency
of the parallel algorithm in terms of a reduced
amount of computation\footnote{We
remark, however, that the flop--count in the table also
reflects the fact that our experiments were carried out using a
particular, in this case MATLAB, programming language.}.
The savings shown in the table are much greater than
the asymptotic estimate of a 12.5\% reduction in the number
of multiplications. The reason appears to be that
we have only tested matrices
of small to moderate size. There may be also some dependency on the
manner in which  MATLAB performs matrix operations (multiplications
and additions) at machine
level.

Finally we make a few comments on the numerical
accuracy of our parallel algorithm. Our parallel algorithm basically
involves two main tasks: to compute the Perron complements $P_{\alpha_i}$
and to compute
the group inverses $B_{\alpha_i}^\#$ associated with those Perron complements.
For the same
reason as we mentioned earlier, Meyer's method in \cite{Meye75} is
advisable for computing the $B_{\alpha_i}^\#$'s.
%, which are related to the irreducible
%singular M--matrices arising from Perron complementation.
This method can
be carried out with Gaussian eliminations as an inversion algorithm
on the nonsingular matrices
$B_{\alpha_i}+W_{\alpha_i}$ and therefore the standard results on round--off
analysis of Gaussian eliminations (see, for example, \cite{GoVaLo96}) apply.
It should be noted that
compared with that of $A+W$ in (\ref{Aginv_formula}), the inversion of
$B_{\alpha_i}+W_{\alpha_i}$ tends to be more stable because of the reduced
size of the problem \cite[Theorem 3.3.1]{GoVaLo96}. In addition, according to
\cite{NeXu03}, the computation of
$\pi_{\alpha_i}$ on $P_{\alpha_i}$ tends to be more stable than that
of $\pi$ on $T$; in particular, the bound on the relative errors in
$\pi_{\alpha_i}$ does not exceed that in $\pi$. On the other hand,
Gaussian eliminations can also be used to invert the matrices
$I-T[\alpha_i]$
arising from Perron complementation. Even though such nonsingular principal
submatrices of
$I-T$ could be poorly conditioned \cite{FuMe86}, various
partitioning schemes may be exploited so as to alleviate possible numerical
difficulties in calculating $(I-T[\alpha_i])^{-1}$. Consider, for example,
the following $4 \times 4$
irreducible stochastic matrix:
$$T=\left[\begin{array}{cccc}
.4332 & .5667 & .0001 & .0000\\
.4331 & .5668 & .0000 & .0001\\
.0000 & .0001 & .3667 & .6332\\
.0001 & .0000 & .3668 & .6331
\end{array}\right].$$
Using the condition number $\kappa_\infty(X):=
\|X\|_\infty \|X^{-1}\|_\infty$, where $X \in \mathbb R^{n \times n}$
is nonsingular, we obtain that for
$\alpha_1=\{1,2\}$ and $\alpha_2=\{3,4\}$,
$\kappa_\infty(I-T[\alpha_1]) \approx 1.1335 \times 10^4$ and
$\kappa_\infty(I-T[\alpha_2]) \approx 1.2665 \times 10^4$,
but for $\alpha_1=\{1,3\}$ and $\alpha_2=\{2,4\}$,
$\kappa_\infty(I-T[\alpha_1]) \approx 1.1175$ and
$\kappa_\infty(I-T[\alpha_2]) \approx 1.1810$.

\section{Concluding Remarks}

The goal of this paper was to present an efficient parallel algorithm for
computing the group
        inverse of the singular M--matrix $A=I-T$, where $T$ is an
irreducible stochastic matrix, via
Perron complementation. This algorithm can be easily modified to
handle the more general case that
$A=\rho_S I-S$, where $S$ is an irreducible nonnegative matrix and
where $\rho_S$ is the Perron root of $S$. 

As shown in Theorems \ref{Thm4}, \ref{Thm5}, and \ref{Thm6}, the group
inverse of $A$ is
        closely related to the group inverses associated with
the Perron complements of
$T$. This adds to
previous computational utilization of
Perron complementation
due to Meyer \cite{Meye89, Meye89a}
and Kirkland, Neumann, and Xu \cite{KiNeXu01}. It remains an interesting
question whether  the Perron complementation
approach is applicable to other computational problems relating to
irreducible stochastic matrices. 

In this  paper we have focused on implementing the parallel algorithm for
computing the group inverse of $A$ with a $2 \times 2$
partitioning scheme. We therefore remark
that even though any $2 \times 2$ block--partitioning may be used,
numerically it is more efficient to
choose
$\alpha_i$ and $\langle n
\rangle \backslash \alpha_i$ of roughly the same size since it balances
the workload between the processors. To see this note
that  as the size
of $\alpha_i$ decreases, it is less costly to compute
$(I-T[\alpha_i])^{-1}$, but at the same
time, the size of $\langle n \rangle \backslash \alpha_i$ increases
accordingly, and therefore it
is more costly to compute $(I-T[\langle n \rangle
       \backslash \alpha_i])^{-1}$.\\

%Our parallel algorithm provides a way of decomposing the computation
%of $A^\#$
%into a number of smaller tasks involving the computation of the group
%inverse associated
%with
%each Perron complement and therefore any
%method for computing the group inverse can be used to implement
%the algorithm.\\

The operational count presented in Table $1$  shows that the parallel
algorithm is
capable of significantly
reducing the amount of necessary multiplication operations as
       compared with
directly computing the group inverse of $A$. It is interesting to observe that
in \cite{KiNeXu01},
the computation of the mean first passage matrix of a finite
       ergodic Markov
chain with transition matrix $T$ is carried out in parallel on the
Perron complements of $T$. A crucial step there is the computation of
the group inverse associated with each Perron complement. When this step
is accomplished with the parallel algorithm for computing $\as$ developed here,
we can expect that in the parallel computation of the mean first passage
matrix
as suggested in \cite{KiNeXu01},  further
reductions in the  computational effort
can be achieved.

\begin{thebibliography}{99}

\bibitem{AnRo87}
K. M. Anstreicher and U. G. Rothblum.
\newblock Using Gauss--Jordan elimination to compute the index, generalized
nullspaces, and Drazin inverses.
\newblock {\em Lin. Alg. Appl.}, 85:221--239, 1987.

\bibitem{BeGr03}
A. Ben--Israel and T. N. E. Greville.
\newblock {\em Generalized Inverses: Theory and Applications, 2nd ed}.
\newblock Springer, New York, 2003.

\bibitem{BePl94}
A. Berman and R. J. Plemmons.
\newblock {\em Nonnegative Matrices in the Mathematical Sciences}.
\newblock SIAM, Philadelphia, 1994.

\bibitem{CaMe91}
S. L. Campbell and C. D. J. Meyer.
\newblock {\em Generalized Inverses of Linear Transformations}.
\newblock Dover Publications, New York, 1991.

%\bibitem{ChMe99}
%G.E. Cho, C.D. Meyer,
%Markov chain sensitivity measured by first mean passage times.
%\textit{Lin. Alg. Appl.} 2000; 316:21--28

%\bibitem{Draz58}
%M. P. Drazin,
%Pseudoinverses in associative rings and semigroups,
%Amer. Math. Monthly 65 (1958) 506--514.

\bibitem{DuNe84}
E. Deutsch and  M. Neumann.
\newblock Derivatives of the Perron root at an essentially nonnegative matrix
and the group inverse of an M--matrix.
\newblock {\em J. Math. Anal. Appl.}, 102:1--29, 1984.

\bibitem{DuNe85}
E. Deutsch and M. Neumann.
\newblock On the first and second order derivatives of the Perron vector.
\newblock {\em Lin. Alg. Appl.}, 71:57--76, 1985.

\bibitem{EiMaNi88}
M. Eiermann, I. Marek, and W. Niethammer.
\newblock On the solution of singular linear equations by 
semiiterative equations.
\newblock {\em Numer. Math.}, 53:265--283, 1988.

\bibitem{FuMe86}
R. Funderlic and C. D. Meyer.
\newblock Sensitivity of the stationary distribution vector for an 
ergodic Markov
chain.
\newblock {\em Lin. Alg. Appl.}, 76:1--17, 1986.

\bibitem{GoMe86}
G. Golub and C. D. Meyer.
\newblock Using the QR factorization and group inversion to compute, 
differentiate, and
estimate the sensitivity of stationary probabilities for Markov chains.
\newblock {\em SIAM J. Alg. Disc. Meth.}, 7:273--281, 1986.

\bibitem{GoVaLo96}
G. Golub and C. Van Loan.
\newblock {\em Matrix Computation, 3rd ed}.
\newblock The John Hopkins Univ. Press, Baltimore, Maryland, 1996.

\bibitem{Grev72}
T. N. E. Greville.
\newblock The Souriau--Frame algorithm and the Drazin pseudoinverse.
\newblock {\em MRC. Tech. Sum. Rep.}, 1182, 1972.

\bibitem{HaNe90}
M. Hanke and M. Neumann.
\newblock Preconditionings and splitting for singular systems.
\newblock {\em Numer. Math.}, 57:85--89, 1990.

\bibitem{Hart76}
R. E. Hartwig.
\newblock More on the Souriau--Frame algorithm and the Drazin inverses.
\newblock {\em SIAM J. Appl. Math.}, 31:42--46, 1976.

\bibitem{HaHe84}
M. Haviv and L. Van der Heyden.
\newblock Perturbation bounds for the stationary probabilities of a finite
Markov chain.
\newblock {\em Adv. Appl. Prob.}, 16:804--818, 1984.

\bibitem{HoJo85}
R. A. Horn and C. R. Johnson.
\newblock {\em Matrix Analysis}.
\newblock Cambridge Univ. Press, New York, 1985.


\bibitem{Hunter03}
J. J. Hunter.
\newblock Mixing times with applications to perturbed Markov chains.
\newblock {\em Preprint, Massey Univ., Auckland, New Zealand}, 2003.

%\bibitem{KaLiYa93}
%S. Karlin, B. Lindqvist, Y. Yao,
%Markov chains on hypercubes: spectral representation and several
%majorization relations.
%\textit{Random Structures and Algorithms} 1993; 4:1--36.

\bibitem{KeSn60}
J. G. Kemeny and J. L. Snell.
\newblock {\em Finite Markov Chains}.
\newblock Van Nostrand, Princeton, New Jersey, 1960.

\bibitem{Kirk95}
S. J. Kirkland.
\newblock The group inverse associated with an irreducible periodic nonnegative
matrix.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 16:1127--1134, 1995.

\bibitem{KiNe94}
S. J. Kirkland and M. Neumann.
\newblock Convexity and concavity of the Perron root and vector of Leslie
matrices with applications to a population model.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 15:1092--1107, 1994.

\bibitem{KiNe99}
S. J. Kirkland and M. Neumann.
\newblock Cutpoint decoupling and first passage times for random 
walks on graphs.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 20:860--870, 1999.

\bibitem{KiNeSh98}
S. J. Kirkland, M. Neumann, and B. Shader.
\newblock Application of Paz's inequality to perturbation bounds for Markov
chains.
\newblock {\em Lin. Alg. Appl.}, 268:183--196, 1998.

\bibitem{KiNeXu01}
S. J. Kirkland, M. Neumann, and J. Xu.
\newblock A divide and conquer approach to computing the mean first 
passage matrix
for Markov chains via Perron complement reduction.
\newblock {\em Numer. Lin. Alg. Appl.}, 8:287--295, 2001.

\bibitem{KiNeXu04}
S. J. Kirkland, M. Neumann, and J. Xu.
\newblock Convexity and elasticity of the growth rate in size--classified
population models.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 26:170--185, 2004.

\bibitem{LeLo02}
M. Levene and G. Loizou.
\newblock  Kemeny's constant and the random surfer.
\newblock {\em Amer. Math. Month.}, 109:741--745, 2002.

\bibitem{Meye75}
C. D. J. Meyer.
\newblock The role of the group generalized inverse in the theory of finite
Markov chains.
\newblock {\em SIAM Rev.}, 17:443--464, 1975.

\bibitem{Meye80}
C. D. Meyer.
\newblock The condition of a finite Markov chain and perturbation bounds for
the limiting probabilities.
\newblock {\em SIAM J. Alg. Disc. Meth.}, 1:273--283, 1980.

\bibitem{Meye89}
C. D. Meyer.
\newblock Uncoupling the Perron eigenvector problem.
\newblock {\em Lin. Alg. Appl.}, 114/115:69--94, 1989.

\bibitem{Meye89a}
C. D. Meyer.
\newblock Stochastic complementation, uncoupling Markov chains, and the theory
of nearly reducible systems.
\newblock {\em SIAM Rev.}, 31:240--272, 1989.

\bibitem{NeXu03}
M. Neumann and J. Xu.
\newblock On the stability of the computation of the
stationary probabilities
of Markov chains using Perron complements.
\newblock {\em Numer. Lin. Alg. Appl.}, 10:603--618, 2003.

\bibitem{Sene91}
E. Seneta.
\newblock Sensitivity analysis, ergodicity coefficients, and 
rank--one updates for
finite Markov chains.
\newblock (W. J. Stewart, ed.) {\em Numerical Solution of Markov 
Chains}, Marcel Dekker,
New York, 1991.

\end{thebibliography}

\end{document}

