Alternating Direction Methods on Multiprocessors

Abstract

This document proposes a few implementation of the Alternating Direction Method for solving parabolic partial differential equations on multiprocessors. A careful complexity analysis of these implementations shows that, contrary to what is generally believed, the method can be made highly efficient on parallel architectures by using pipelining and variations of the classical Gaussian elimination algorithm for solving tridiagonal systems. In an earlier work the authors showed that they could obtain linear speedups for moderate numbers of processors in a ring architecture. This paper discusses extensions to a large number of processors in a 2-D grid architecture and a hypercube.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1985
Accession Number
ADA161973

Entities

People

  • Martin H. Schultz
  • S. L. Johnsson
  • Youcef Saad

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Arrays
  • Bandwidth
  • Computational Complexity
  • Computations
  • Computer Science
  • Differential Equations
  • Elimination
  • Embedding
  • Equations
  • Linear Arrays
  • Multiprocessors
  • Partial Differential Equations
  • Three Dimensional
  • Two Dimensional

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.