Design and Analysis of Scalable Parallel Algorithms 6. AUTHOR(S) Vipin Kumar

11. SUPPtEMEN.ARY NOTEST"ha views, opinions and/or findings contained in this report are those of the author(s) and should not be construed as an official Department of the Army position, policy, or decision, unless so designated by other documentation. Ila. OISTRIBUTION I AVAILABILITY STATEMWNT 12b. DISTRIBUTION COf Approved for public release; distribution unl 4mited. 13. ABSTRACT (MAaimum 1'O % words) The objective of this research is to develop efficient parallel algorithms for a variety of problems Mt and to analyze the scalability of new and existing parallel algorithms. Scalability analysis is an;M 4 important tool used for predicting the performance of an algorithm-architecture combination when • I one or more of the hardware related parameters (interconnection network, speed of processors, speed of communication channels, number of processors) are changed. The problems studied as a part of this project come from diverse domains such as solution of differential equations, discrete optimization, neural network based learning, sorting and graph algorithms. In particular, we have studied parallel algorithms for solving linear systems using the preconditioned conjugate gradient method, partitioning of finite element meshes, balancing load in unstructured tree search arising in discrete optimization, the backpropagation neural network learning algorithm, dynamic program