Sparse cholesky factorization on a simulated hypercube

ABSTRACT

Solutions to large systems of linear equations are used in a wide range of problems. Many of these systems can be represented by symmetric sparse positive definite matrices, and the Cholesky decomposition has been proved to be one of the best methods for solving symmetric positive definite matrices. Our work deals with the parallel Cholesky decomposition of such matrices and their implementation on a simulated hypercube. We decompose the solution into subtasks that have precedence relations among themselves. These precedence relations are expressed in the form of an elimination tree where each node represents a subtask assigned to a processor for execution. The scheduling of these tasks is based on the Highest Level First policy which has been proved to be an optimal one in case of static and deterministic scheduling. A flexible hypercube simulator is developed in C language under UNIX environment. The simulation studies indicate that this algorithm is very efficient for large and well ordered matrices.

REFERENCES

• 1: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 2: Alan George , Michael T. Heath , Joseph Liu , Esmond NG, Sparse Cholesky factorization on a local-memory multiprocessor, SIAM Journal on Scientific and Statistical Computing, v.9 n.2, p.327-340, March 1988 [doi>10.1137/0909021]
• 3: A. George, M.T. Heath and Joseph Liu, Parallel Cholesky Factorization on a Shared Memory Multiprocessor, Linear Algebra and its applications, 77, 1986, pp 165-187.
• 4: A. George, M.T. Heath and Joseph Liu, Symbolic Cholcsky factorization on a Local Memory M ultiprocessor, Parallel Computing, 5, 1987, pp 85-95.
• 5: J W H Liu, Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Computing, v.3 n.4, p.327-342, Oct. 1986 [doi>10.1016/0167-8191(86)90014-1]
• 6: Stephan 1I Friedberg and Arnold J lnsel, Introduction to Linear Algebra and its applications. Prentice tlall, Engelwood Cliffs N.J. 1986.
• 7: G.W.Stewart, Introduction to Matrix Computations, Academic Press, 1973.
• 8: V.M.Padakanti, Sparse Cbolesky Factorization on a Simulated Hypercube, Project Report, Dept of Computer Science and Engineering. Indian Institute of Science, Bangalore, lndia. April 1990.
• 9: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 10: R.P.Tewarson, Sparse matrices, Academic press, NY, 1973.