Introduction to Parallel Algorithms

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.

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.

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Introduction to Parallel Algorithms

Summary

Author Biography

Table of Contents

Supplemental Materials