Advances in Randomized Parallel Computing

Inbunden, Engelska, 1999

AvM. Pardalos Pardalos,Panos M. Pardalos,Sanguthevar Rajasekaran,Panos M Pardalos

2 009 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

The technique of randomization has become very prevalent since it offers superior performance and simplicity. Numerous researchers work in this area of vital importance. Parallel Computing is also very important since one can get excellent speedups using parallel computers. This book combines these two domains. It provides a summary of the state-of-the-art results and techniques in the area of randomized parallel computing. There are few texts in the area of randomized computing, and more surprisingly there is no text in the area of randomized parallel computing. Thus our book fills the void in this very important area. Audience: This is a reference book for researchers, educators, and students. It can also be used as a text for an advanced graduate course on randomized computing, parallel computing, or distributed computing.

Produktinformation

Utgivningsdatum1999-05-31
Mått155 x 235 x 19 mm
Vikt617 g
FormatInbunden
SpråkEngelska
SerieCombinatorial Optimization
Antal sidor287
Upplaga1999
FörlagKluwer Academic Publishers
ISBN9780792357148

Tillhör följande kategorier

1 Optimal Bounds on Tail Probabilities: A Study of an Approach.- 1.1 Introduction.- 1.2 Bounding Tail Probabilities with the Laplace Transform.- 1.3 When only the Mean is given: The Hoeffding Bound.- 1.4 When the Mean and the Variance are given: A Simple Proof of the Bennett Bound.- 1.5 When the First n Moments are Given: A Glimpse of the General Theory.- 1.6 An Application: Improved Bounds for the List Update Problem.- References.- 2 Parallelism in Comparison Problems.- 2.1 Introduction.- 2.2 Selection.- 2.3 Merging.- 2.4 Sorting.- 2.5 Conclusions.- References.- 3 Random Sampling.- 3.1 Introduction.- 3.2 Preliminaries.- 3.3 Partitioning I: Sorting.- 3.4 Partitioning II: List Ranking.- 3.5 Pruning I: Selection.- 3.6 Pruning II: Row maxima of monotone matrices.- 3.7 Pruning III: Graph Connected Components.- 3.8 Other examples.- 3.5 Bibliographic Notes.- References.- 4 Randomized Algorithms on the Mesh.- 4.1 Introduction.- 4.2 Preliminaries.- 4.3 Routing on the mesh.- 4.4 Sorting on the mesh.- 4.5 Selection on the mesh.- References.- 5 Efficient Randomized Algorithms.- 5.1 Introduction.- 5.2 Preliminaries.- 5.3 Randomized Routing.- 5.4 Randomized Selection.- 5.5 Randomized Sorting.- 5.6 Randomized PRAM Emulation.- 5.7 Selection and Sorting Schemes for Processing Large Distributed Files.- 5.8 Conclusions.- References.- 6 Ultrafast Randomized Parallel Algorithms for Spanning Forests.- 6.1 Introduction.- 6.2 Uitrafast Parallel Algorithms.- 6.3 Dense Instances.- 6.4 Ultrafast Algorithms for Spanning Forests.- 6.5 Open Problems and Further Research.- References.- 7 Parallel Randomized Techniques for Some Fundamental Geometric Problems.- 7.1 Introduction.- 7.2 Preliminaries and Definitions.- 7.3 The Use of Randomization in Computational Geometry.- 7.4 Applications to Fundamental Geometric Problems.- 7.5 Summary.- References.- 8 Capturing the Connectivity of High-Dimensional Geometric Spaces.- 8.1 Introduction.- 8.2 Basic Probabilistic Roadmap Planner.- 8.3 Other Sampling Strategies.- 8.4 Roadmap Coverage.- 8.5 Roadmap Connectedness.- 8.6 Current and Future Work.- Appendix: A. Proof of Theorem 1.- Appendix: B. Proof of Theorem 2.- Appendix: C. Proof of Theorem 3.- Appendix: D. Proof of Theorem 4.- References.- 9 Randomized Parallel Prefetching and Buffer Management.- 9.1 Introduction.- 9.2 Definitions.- 9.3 Read-Once Reference Strings.- 9.4 Read-Many Reference Strings.- 9.5 Concluding Remarks.- References.- 10 DFA Problems.- 10.1 Introduction.- 10.2 Membership Problem.- 10.3 Containment and Equivalence Problems.- 10.4 Ranking and Related Problems.- 10.5 Coarsest Partition Problems.- 10.6 Automata Testing Problems.- 10.7 Conversion from Regular Expression to NFA.- 10.8 Applications.- 10.9 Open Problems.- References.- 11 LAPACK90.- 11.1 Introduction.- 11.2 Interface Blocks for LAPACK 77.- 11.3 Interface Blocks for LAPACK 90.- 11.4 Code of LAPACK90 Routines.- 11.5 LAPACK90 Documentation.- 11.6 LAPACK90 Test Programs.- 11.7 LAPACK90 User Callable Routines.- References.- Appendix: A, Generic Interfaces.- A.1 LAPACK77 Generic Interface Blocks.- A.2 LAPACK90 Generic Interface Blocks.- Appendix: B, Interface Subroutines.- B.1 LA_GESV and LA_GETRI subroutines.- B.2 Auxiliary Routines.- Appendix: C.- C.1 Documentation of LA_GESV.- Appendix: D.- D.1 The LA_GESV test results.- Appendix: E.- E.1 LAPACK90 User Callable Routines.