A Simple Parallel Prefix Algorithm for Compact Finite-Difference Schemes

Abstract

A compact scheme is a discretization scheme that is advantageous in obtaining highly accurate solutions. However, the resulting systems from compact schemes are tridiagonal systems that are difficult to solve efficiently on parallel computers. Considering the almost symmetric Toeplitz structure, a parallel algorithm, simple parallel prefix (SPP), is proposed. The SPP algorithm requires less memory than the conventional LU decomposition and is highly efficient on parallel machines. It consists of a prefix communication pattern and AXPY operations. Both the computation and the communication can be truncated without degrading the accuracy when the system is diagonally dominant. A formal accuracy study has been conducted to provide a simple truncation formula. Experimental results have been measured on a MasPar MP-1 SIMD machine and on a Cray 2 vector machine. Experimental results show that the simple parallel prefix algorithm is a good algorithm for the compact scheme on high-performance computers.... High performance computing, Parallel numerical algorithms, Compact finite-difference scheme, SIMD computations, Almost Toeplitz tridiagonal schemes

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1993
Accession Number
ADA267094

Entities

People

  • Ronald D. Joslin
  • Xian-he Sun

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Boundary Layer
  • Computational Fluid Dynamics
  • Computational Science
  • Computations
  • Computers
  • Difference Equations
  • Differential Equations
  • Equations
  • Fluid Dynamics
  • High Performance Computing
  • Navier Stokes Equations
  • Parallel Computing
  • Parallel Processing
  • Partial Differential Equations
  • Truncation

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Parallel and Distributed Computing.