Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis

所需积分/C币:50 2017-07-19 11:30:49 27.71MB PDF
64
收藏 收藏
举报

集中分布式计算非常有价值的书籍,一个完整的PDF文件,如果大家想按照章节下载,可以下载免费的PDF文件,https://dspace.mit.edu/handle/1721.1/3719#files-area,希望没有积分的朋友也可以一起学习。当然有积分的朋友们可以选择资助一下我,1积分,不多
Parallel and Distributed Computation Numerical methods Dimitri P. bertsekas and John N. Tsitsiklis Massachusetts Institute of technology WWW site for book information and orders http://world.std.com/athe Athena. Scientific. Belmont Massachusett Athena scientific Post office box 391 Belmont Mass. 02178-9998 U.s.A Email:athenasc@world.std.com WwwinfoRmationandordershttp://world.std.com/athenasc/ Cover Design: Ann, Gallager C1997 Dimitri P. Bertsekas and John n. tsitsiklis All rights reserved. No part of this book may be reproduced by any elec tronic or mechanical means (including photocopying, recording or infor mation storage and retrieval) without the publishers permission in writing Originally published by Prentice-Hall, Inc in 1989. Corrections listed at the end Publisher's Cataloging-in-Publication Data Bertsekas. Dimitri P Parallel and Distributed Computation: Numerical methods Includes bibliographical references and index 1. Parallel processing Electronic computers I. John Tsitsiklis N, joint author. II. Title QA76.5.B4571997 004:35 9770648 ISBN1886529-01-9 To Joanna and Daphne Contents PREFACE 1 INTRODUCTION 1.1 Parallel and distributed architectures 2 L 1. The Need for Parallel and Distributed Computation, 2 1. 1. 2 Parallel Computing Systems and their classification, 3 1.2 Models, Complexity Measures, and Some Simple algorithms 8 12.I Models. 8 1.2.2 Complexity Measures, 10 4.2.3 Examples: Vector and Matrix Computations, 16 4.2.4 Parallelization of iterative Methods, 19 1.3 Communication Aspects of Parallel and Distributed Systems 27 1.3.1 Communication Links. 30 1.3.2 Data Link Control. 33 v Contents 1.3.3 Routing 37 1.3.4 Network Topologies, 39 1. 3. 5 Concurrency and Communication Tradeoffs 1.3.6 Examples of matrix-Vector Calculations, 71 1.4 Synchronization Issues in Parallel and Distributed Algorithms 88 1.4.1 Synchronous Algorithms, 88 1.4.2 Asynchronous Algorithms and the Reduction of the Synchronization Penalty, 9 Part 1 Synchronous Algorithms 109 2 ALGORITHMS FOR SYSTEMS OF LINEAR EQUATIONS AND MATRIX INVERSION 2.1 Parallel algorithms for Linear Systems with Special Structure 110 2.1.1 Triangular Matrices and Back Substitution, 110 2. 1.2 Tridiagonal Systems and Odd-Even Reduction, 113 2.2 Parallel Direct Methods for General Linear Equations 118 2.2.1 Gaussian Elimination. /19 2.2.2 Triangularization Using Givens Rotations, 124 2.3 A Fast Direct Matrix Inversion Algorithm 128 2.4 Classical Iterative Methods For Systems of Linear Equations 130 2.5 Parallel Implementation of Classical Iterative Methods 135 2. 5. 1 An Example: Poisson 's equation, 137 2. 5.2 Multigrid Methods, 139 2.6 Convergence Analysis of Classical Iterative Methods 143 2. 6. 1 Background on Maximum Norms and Nonnegative Matrices, 144 2. 6. 2 Convergence Analysis Using Marimum Norms, 15/ 2. 6. 3 Convergence Analysis Using a quadratic Cost Function, 153 2.6.4 The Poisson equation Revisited, 155 2.7 The Conjugate Gradient Method 158 2.7.1 Description of the Algorithm, 160 2.7.2 Speed of Convergence, 162 Co 2.7.3 Preconditioned Conjugate Gr 2.7.4 Parallel implementation, 165 2.8 Computation of the Invariant Distribution of a Markov Chain 166 2.9 Fast Iterative Matrix Inversion 173 3 ITERATIVE METHODS FOR NONLINEAR PROBLEMS 180 3.1 Contraction Mappings 18 3.I. General Results. 182 3.1.2 Con t Sets, 185 3.1.3 Some Useful Contraction MappingS, 191 3.2 Unconstrained Optimization 198 3. 2.I The Main Algorithms, 198 3.2.2 Convergence Analysis Using the Descent Approach, 202 3. 2. 3 The Case of a Convex Cost Function, 206 3. 2. 4 Nonlinear algorithms, 207 3.3 Constrained Optimization 210 3.3.1 Optimality Conditions and the Projection Theorem, 210 3.3.2 The Gradient Projection Algorithm, 212 3.3.3 Scaled gradient Projection Algorithms, 215 3. 3. 4 The Case of a Product Constraint Set: Parallel implementations, 217 3. 3. 5 Nonlinear algorithms, 219 3.4 Parallelization and Decomposition of Optimization Problems 224 3.4. Quadratic Programming, 225 3.4.2 Separable Strictly Convex Programming, 229 3.4.3 The Proximal Minimization algorithm, 232 3. 4. 4 Augmented lagrangian Methods, 243 3.5 Variational Inequalities 264 3. 5.1 Examples of Variational Inequality Problems, 264 3.5.2 Preliminaries. 267 3.5.3 The pre n Algorithm 269 3.5.4 Linearized AlgorithmS, 273 3.5. 5 The Cartesian Product Case: Parallel Implementations, 275 3.5.6 Nonlinear algorithmS, 278 3. 5. 7 Decomposition Methods for Variational inequalities, 28 Contents 4 SHORTEST PATHS AND DYNAMIC PROGRAMMING 291 4. 1 The Shortest path problem 293 4.1.1 The Bellman-Ford Algorithm, 294 4.1.2 Other Parallel shortest Path Methods, 302 4.2 Markov Chains with Transition Costs 308 4.3 Markovian Decision Problems 312 4.3. Discounted Problems. 316 4.3.2 Undiscounted Problems--Stochastic shortest Paths, 317 4.3.3 Parallel implementation of the Dynamic Programming Iteration. 323 5 NETWORK FLOW PROBLEMS 331 5.1 The Linear network flow Problem and its Dual 332 5.2 The Relaxation Method 340 5.2.1 Application to the Shortest Path Problem, 343 5.2. 2 multiple node relaxation method, 345 5.3 The E- Relaxation Method 355 5.3. 7 The Auction Algorithm for the Assignment Problem, 364 5.3.2 Parallel versions of the E-Relaxation and the auction Algorithms, 371 5.4 Complexity Analysis of the e-Relaxation Method and its Scaled Version 376 5.4.I The Scaled version of the Algorithm, 384 5. 4.2 Application to the Assignment Problem, 386 5.5 Network Flow Problems with Strictly Convex Cost 390 5.5.1 The Relaxation Method. 397 5.5.2 Convergence Analysis, 398 5.5.3 The problem without Arc Flow bounds, 406 5.5.4 An Example: Constrained Matrix Problems, 408 5.5.5 Parallel implementations of the Relaxation Method, 410 5.6 Nonlinear Multicommodity Flow Problems-Routing Applications 414

...展开详情
试读 127P Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis 50积分/C币 立即下载
1/127
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第1页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第2页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第3页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第4页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第5页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第6页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第7页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第8页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第9页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第10页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第11页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第12页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第13页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第14页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第15页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第16页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第17页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第18页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第19页
Parallel and distributed computation - numerical methods - Bertsekas, Tsitsiklis第20页

试读结束, 可继续阅读

50积分/C币 立即下载