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.