TECHNICAL REPORT BU-CEIS-9620, BILKENT UNIVERSITY,
DEPARTMENT OF COMPUTER ENGINEERING AND INFORMATION SCIENCE

TITLE: Nonsymmetric Skyline versus Compressed Sparse Row Format in 
Direct Methods for Markov Chains

AUTHOR: Tugrul Dayar

ABSTRACT: This paper investigates the implementation of Gaussian
Elimination (GE) and Grassmann-Taksar-Heyman (GTH) algorithms for
Markov chains in nonsymmetric skyline (NSK) and compressed sparse
row (CSR) formats. Numerical experiments are carried out using three 
real life applications. Implementations that allocate space for both 
lower- and upper-triangular factors result in faster GTH solvers.
Specifically, the CSR implementation of the GTH algorithm for the
nontransposed linear system of equations gives the smallest run-time
among different GTH implementations considered. For GE, the experiments
suggest the CSR implementation for the transposed system of equations
as the appropriate choice.