New Parallel Algorithms for Direct Solution of Linear Equations

Rather than parallelizing sequential algorithms, the authors develop new backsubstitution free parallel algorithms, using a bidirectional elimination technique for the solution of both dense and sparse linear equations. They provide full coverage of bidirectional parallel algorithms based on Gaussian elimination. LU factorization. Householder reductions and modified Gram-Schmidt orthogonalization, Givens rotations, sparse Cholesky factorization, and sparse factorization, clearly demonstrating how the bidirectional approach allows for improved speedup, numerical stability. and efficient implementation on multiprocessor systems.

Plus, the book offers a useful survey of the vast literature on direct methods, introductory material on solving systems of linear equations, and exercises. It is an invaluable resource for computer scientists, researchers in parallel linear algebra, and anyone with an interest in parallel programming.

Contents

• Preface.....ix
  
• Chapter 1: Introduction.....1
  
• Chapter 2: Parallel Computational Model and Algorithm Design Issues.....8
  
• Chapter 3: Bidirectional Gaussian Elimination.....24
  
• Chapter 4: Bidirectional Lu Factorization.....51
  
• Chapter 5: Bidirectional Householder Reductions and Modified Gram-Schmidt Orthogonalization.....66
  
• Chapter 6: Bidirectional Givens Rotations.....83
  
• Chapter 7: Bidirectional Sparse Cholesky Factorization.....96
  
• Chapter 8: Bidirectional Sparse Factorization.....121
  
• Chapter 9: Bidirectional Elimination Algorithms Revisited.....131
  
• Bibliography.....152
  
• Index.....165