Parallel Algorithms

G.W. Stewart and I proposed the use of the data-flow model for developing fine- and medium-grained algorithms for dense matrix problems on message-passing parallel machines; the computational model and several sample algorithms were developed [J19], and a detailed analysis of a parallel Cholesky algorithm was given [J22]. A similar analysis was given for the block conjugate gradient algorithm [J24].

Some ``coloring algorithms" were developed which make parallel iterative methods more efficient for certain network problems, including discretizations of elliptic differential equations [J18]. A different class of parallel iterative methods was developed in joint work with R.E. White, which proposed and analyzed the simultaneous use of several matrix splittings [J20]. These multisplitting algorithms have since been the subject of considerable work by other researchers and formed the basis for the preconditioning algorithms used in [C07] [J36].

More recently, I have worked on GPU algorithms [J89].

[C07]

Chiou-Ming Huang and Dianne P. O'Leary, ``Preconditioning Parallel Multisplittings for Solving Linear Systems of Equations,'' International Conference on Supercomputing (Washington, DC, July 1992) ACM Press, New York, 1992, 478-484.

[J18]

Dianne P. O'Leary, ``Ordering schemes for parallel processing of certain mesh problems,'' SIAM Journal on Scientific and Statistical Computing 5 (1984) 620-632.

[J19]

Dianne P. O'Leary and G. W. Stewart, ``Data-flow algorithms for parallel matrix computations,'' Communications of the ACM 28 (1985) 840-853.

[J20]

Dianne P. O'Leary and R. E. White, ``Multi-splittings of matrices and parallel solution of linear systems,'' SIAM Journal on Algebraic and Discrete Methods 6 (1985) 630-640.

[J22]

Dianne P. O'Leary and G. W. Stewart, ``Assignment and scheduling in parallel matrix factorization,'' Linear Algebra and Its Applications 77 (1986) 275-300.

[J24]

Dianne P. O'Leary, ``Parallel implementation of the block conjugate gradient algorithm,'' Parallel Computing 5 (1987) 127-139.

[J36]

Chiou-Ming Huang and Dianne P. O'Leary, ``A Krylov multisplitting algorithm for solving linear systems of equati ons,'' Linear Algebra and Its Applications, 194 (1993) 9-29.

[J89]

Jin Hyuk Jung and Dianne P. O'Leary, ``Implementing an Interior Point Method for Linear Programs on a CPU-GPU System," Electronic Transactions on Numerical Analysis, 28 (2008) 174-189. http://etna.mcs.kent.edu/vol.28.2007-2008/pp174-189.dir/pp174-189.pdf