Image reconstruction using Positron Emission Tomography (PET) involves estimating an unknown number of photon pairs emitted from the radiopharmaceuticals within the tissue of the patient's body. A significant amount of artifactual noise exists in the reconstructed image with the commonly used convolution back-projection method. It is known that a better estimate can be made for the unknown information using the Maximum Likelihood (ML) formulation. Despite the quality of images over the traditional method, the Expectation Maximization (EM) iterative algorithm is not being used in practice due to the tremendous processing time. This research proposes new techniques in designing parallel algorithms in order to speedup the reconstruction process. Using EM algorithm as an example, we studied several general parallel techniques for both distributed-memory architecture and message-passing programming paradigm. Our approach was to maximize latency-hiding for both intra- and inter-iteration computation. Dependency constraints that exist in and between iterations were reduced by overlapping communication and computation with MPI's non-blocking collective reduction operation. A performance model was established to estimate the processing time of the algorithms and was validated with the experimental results. A second strategy, a sparse matrix compaction technique, was developed to reduce both the computational time and the storage requirement of the computation-bound EM algorithm with better use of PET system geometry. The proposed techniques are generally applicable to many scientific computation problems whcih commonly involve sparse matrix operations as well as iterative type of algorithms.