Technical reports

Parallel iterative solution method for large sparse linear equation systems

Rashid Mehmood, Jon Crowcroft

October 2005, 22 pages

DOI: 10.48456/tr-650

Abstract

Solving sparse systems of linear equations is at the heart of scientific computing. Large sparse systems often arise in science and engineering problems. One such problem we consider in this paper is the steady-state analysis of Continuous Time Markov Chains (CTMCs). CTMCs are a widely used formalism for the performance analysis of computer and communication systems. A large variety of useful performance measures can be derived from a CTMC via the computation of its steady-state probabilities. A CTMC may be represented by a set of states and a transition rate matrix containing state transition rates as coefficients, and can be analysed using probabilistic model checking. However, CTMC models for realistic systems are very large. We address this largeness problem in this paper, by considering parallelisation of symbolic methods. In particular, we consider Multi-Terminal Binary Decision Diagrams (MTBDDs) to store CTMCs, and, using Jacobi iterative method, present a parallel method for the CTMC steady-state solution. Employing a 24-node processor bank, we report results of the sparse systems with over a billion equations and eighteen billion nonzeros.

Full text

PDF (1.9 MB)

BibTeX record

@TechReport{UCAM-CL-TR-650,
  author =	 {Mehmood, Rashid and Crowcroft, Jon},
  title = 	 {{Parallel iterative solution method for large sparse linear
         	   equation systems}},
  year = 	 2005,
  month = 	 oct,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-650.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-650},
  number = 	 {UCAM-CL-TR-650}
}