Muutke küpsiste eelistusi

Introduction to Parallel Algorithms [Kõva köide]

(Louisiana State University, Baton Rouge, Louisiana), (St. Xavier College, Palayamkottai, India)
Teised raamatud teemal:
Introduction to Parallel AlgorithmsSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780471251828.html
Märksõnad:
Parallel algorithms Made Easy

The complexity of today's applications coupled with the widespread use of parallel computing has made the design and analysis of parallel algorithms topics of growing interest. This volume fills a need in the field for an introductory treatment of parallel algorithms-appropriate even at the undergraduate level, where no other textbooks on the subject exist. It features a systematic approach to the latest design techniques, providing analysis and implementation details for each parallel algorithm described in the book. Introduction to Parallel Algorithms covers foundations of parallel computing; parallel algorithms for trees and graphs; parallel algorithms for sorting, searching, and merging; and numerical algorithms. This remarkable book:
* Presents basic concepts in clear and simple terms
* Incorporates numerous examples to enhance students' understanding
* Shows how to develop parallel algorithms for all classical problems in computer science, mathematics, and engineering
* Employs extensive illustrations of new design techniques
* Discusses parallel algorithms in the context of PRAM model
* Includes end-of-chapter exercises and detailed references on parallel computing.

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.

Arvustused

"...an introduction to parallel algorithms..." (Zentralblatt fur Mathematik, Vol. 948, No. 23)

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


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.

S. S. 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.