Introduction to Parallel Algorithms

by Xavier, C.; Iyengar, S. S.

• ISBN13: 9780471251828
• ISBN10: 0471251828
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-08-05
• Publisher: Wiley-Interscience
• More Book Details
• Purchase Benefits

Summary

This book enables universities to offer parallel algorithm courses at the senior undergraduate level in computer science and engineering. It is also an invaluable text/reference for graduate students, scientists, and engineers in computer science, mathematics, and engineering.

Author Biography

C. XAVIER teaches in the Department of Computer Science at St. Xavier College in Palayamkottai, India. He has published numerous papers on parallel algorithms and more than ten computer science textbooks.<br> <br> IYENGAR is Professor and Chairman of the Department of Computer Science at Louisiana State University. He has published several books and more than 220 papers on high-performance algorithms and data structures and has headed research projects for such organizations as the Office of Naval Research, the National Aeronautics and Space Administration, the National Science Foundation, and others. He is a Fellow of the IEEE for research contributions to data structures and algorithms and received the University Distinguished Faculty Award.

Table of Contents

PREFACE	xi	(2)
ACKNOWLEDGMENTS	xiii	(2)
ABOUT THE AUTHOR	xv
PART 1 FOUNDATIONS OF PARALLEL COMPUTING	1	(142)
0. Introduction	3	(15)
0.1 Introduction to Computers	3	(7)
0.2 Parallel Computers	10	(1)
0.3 Parallel Processing Concepts	11	(3)
0.4 High-Performance Computers	14	(2)
0.5 Organization and Scope of the Book	16	(1)
Bibliography	16	(2)
1. Elements of Parallel Computing	18	(41)
1.1 Levels of Parallelism	18	(2)
1.2 Taxonomy of Parallel Computers	20	(9)
1.2.1 Flynn's Classification	20	(3)
1.2.2 Erlangen Taxonomy (Handler's Taxonomy)	23	(1)
1.2.3 Giloi Taxonomy	24	(1)
1.2.4 Hwang-Brigg's Taxonomy	24	(1)
1.2.5 Duncan's Taxonomy	25	(4)
1.3 Models for Parallel Computation	29	(14)
1.3.1 Binary Tree Model	29	(3)
1.3.2 Network Model	32	(1)
1.3.3 Hypercubes (k-cubes)	33	(10)
1.4 PRAM Model	43	(4)
1.4.1 Language Structure for Parallel Algorithms	45	(2)
1.5 Some Simple Algorithms	47	(3)
1.6 Performance of Parallel Algorithms	50	(5)
1.7 Summary	55	(1)
Bibliography	55	(1)
Exercises	56	(3)
2. Data Structures for Parallel Computing	59	(49)
2.1 Arrays and Lists	59	(2)
2.2 Linked Lists	61	(4)
2.3 Graphs and Trees	65	(41)
2.3.1 Preliminaries	66	(4)
2.3.2 Euler and Hamiltonian Graphs	70	(1)
2.3.3 Trees	71	(12)
2.3.4 Graph Traversal	83	(2)
2.3.5 Connectivity	85	(3)
2.3.6 Planar Graphs	88	(4)
2.3.7 Coloring and Independence	92	(1)
2.3.8 Clique Covering	93	(1)
2.3.9 Intersection Graph	94	(1)
2.3.10 Chordal Graphs	94	(6)
2.3.11 Some More Intersection Graphs	100	(1)
2.3.12 Matching Problems in Graphs	101	(2)
2.3.13 Centrality in Graphs	103	(1)
2.3.14 Domination Theory	104	(1)
2.3.15 Some Graph Problems	105	(1)
Bibliography	106	(2)
3. Paradigms for Parallel Algorithm	108	(15)
3.1 Binary Tree Paradigm	108	(4)
3.2 Growing by Doubling	112	(1)
3.3 Pointer Jumping	112	(4)
3.4 Divide and Conquer	116	(1)
3.5 Partitioning	117	(4)
3.6 Summary	121	(1)
Bibliography	121	(1)
Exercises	121	(2)
4. Simple Algorithms	123	(20)
4.1 Scalar Product of Two Vectors	123	(1)
4.2 Matrix Multiplication	124	(1)
4.3 Partial Sums	125	(6)
4.4 Binomial Coefficients	131	(3)
4.5 Range Minima Problem	134	(6)
Bibliography	140	(1)
Exercises	140	(3)
PART 2 ALGORITHMS FOR GRAPH MODELS	143	(106)
5. Tree Algorithms	145	(39)
5.1 Euler Circuits	145	(2)
5.2 Rooting a Tree	147	(1)
5.3 Post Order Numbering	148	(3)
5.4 Number of Descendants	151	(1)
5.5 Level of Each Vertex	151	(1)
5.6 Lowest Common Ancestor	151	(4)
5.7 Tree Contraction	155	(5)
5.8 Arithmetic Expression Evaluation	160	(2)
5.9 Root Finding Problem in a Forest	162	(3)
5.10 Paths to the Root	165	(3)
5.11 Converting a Tree into a Binary Tree	168	(7)
5.12 Diameter of All the Vertices	175	(4)
5.13 Furthest Neighbors	179	(3)
Bibliography	182	(1)
Exercises	183	(1)
6. Graph Algorithms	184	(29)
6.1 Simple Graph Algorithms	184	(4)
6.2 Parallel Connectivity Algorithms	188	(13)
6.2.1 Breadth-First Search (BFS)	189	(2)
6.2.2 Connected Components Using BFS	191	(5)
6.2.3 Transitive Closure Matrix	196	(1)
6.2.4 Vertex Collapse	196	(5)
6.3 Biconnected Components	201	(3)
6.4 Spanning Trees	204	(2)
6.5 Shortest Path Problem	206	(4)
Bibliography	210	(1)
Exercises	211	(2)
7. NC Algorithms for Chordal Graphs	213	(36)
7.1 Chordal Graph Recognition	213	(10)
7.2 Maximal Cliques of Chordal Graphs	223	(4)
7.3 Characterization of CV Graphs	227	(1)
7.4 Path Graph Recognition	228	(19)
7.4.1 Some Definitions and Facts	229	(5)
7.4.2 Outline of the Algorithm	234	(2)
7.4.3 Union of Two UV Graphs	236	(8)
7.4.4 Correctness and Complexity	244	(3)
Bibliography	247	(2)
PART 3 ARRAY MANIPULATION ALGORITHMS	249	(26)
8. Searching and Merging	251	(11)
8.1 Sequential Searching	251	(1)
8.2 Parallel Search in CREW PRAM	252	(1)
8.3 Parallel Search with More Data	253	(2)
8.4 Searching in Unsorted Array	255	(1)
8.5 Merging by Ranking	255	(3)
8.6 Bitonic Merging	258	(3)
Bibliography	261	(1)
9. Sorting Algorithms	262	(13)
9.1 Sequential Sorting Algorithms	262	(7)
9.1.1 Bubble Sort	263	(1)
9.1.2 Insertion Sorting	264	(1)
9.1.3 Shell's Diminishing Increment Sort	265	(1)
9.1.4 Heap Sort	266	(3)
9.2 Merge Sort	269	(1)
9.3 Sorting Networks	270	(2)
Bibliography	272	(1)
Exercises	273	(2)
PART 4 NUMERICAL ALGORITHMS	275	(77)
10. Algebraic Equations and Matrices	277	(42)
10.1 Algebraic Equations	277	(3)
10.1.1 Geometrical Interpretation	277	(1)
10.1.2 Bisection Method	278	(2)
10.2 Determinant of a Matrix	280	(4)
10.3 System of Linear Equations	284	(8)
10.3.1 Gauss Elimination Method	287	(2)
10.3.2 Given's Rotation	289	(3)
10.4 Fourier Transforms	292	(10)
10.5 Polynomial Multiplication	302	(3)
10.6 Matrix Inversion	305	(3)
10.7 Toeplitz Matrix	308	(3)
10.7.1 Lower Triangular Toeplitz Matrix	310	(1)
10.8 Tridiagonal Systems	311	(6)
10.8.1 Gauss Elimination	312	(1)
10.8.2 Odd-Even Reduction Method	313	(4)
Bibliography	317	(1)
Exercises	318	(1)
11. Differentiation and Integration	319	(16)
11.1 Differentiation	319	(2)
11.2 Partial Differentiation	321	(5)
11.3 Definite Integrals	326	(2)
11.4 Interpolation	328	(5)
11.4.1 Linear Interpolation	329	(2)
11.4.2 Quadratic Interpolation	331	(1)
11.4.3 Lagrange's Interpolation	331	(2)
Bibliography	333	(1)
Exercises	333	(2)
12. Differential Equations	335	(17)
12.1 Euler's Formula	335	(1)
12.2 Partial Differential Equations	336	(1)
12.3 Parabolic Equations	337	(14)
12.3.1 Schmidt Method	338	(6)
12.3.2 Laasonen Method	344	(3)
12.3.3 Crank-Nicholson Method	347	(1)
12.3.4 Three-Level Difference Methods	348	(3)
Bibliography	351	(1)
ANSWERS TO SELECTED EXERCISES	352	(8)
INDEX	360