A Multilevel Parallel Solver for Block Tridiagonal and Banded Linear Systems

Abstract

This paper describes an efficient algorithm for the parallel solution of systems of linear equations with a block tridiagonal coefficient matrix. The algorithm comprises a multilevel LU-factorization based on block cyclic reduction and a corresponding solution algorithm. The paper includes a general presentation of the parallel multilevel LU-factorization and solution algorithms, but the main emphasis is on implementation principles for a message passing computer with hypercube topology. Problem partitioning, processor allocation and communication requirements are discussed for the general block tridiagonal algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 25, 1989
Accession Number
ADA213151

Entities

People

  • Ibrahim N. Hajj
  • Stig Skelboe

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Boundary Value Problems
  • Classification
  • Computational Complexity
  • Computations
  • Computers
  • Differential Equations
  • Equations
  • Floating Point Operations
  • Linear Systems
  • Load Distribution
  • Partial Differential Equations
  • Security
  • Standards
  • Topology
  • Two Dimensional

Readers

  • Computational Modeling and Simulation
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Linear Algebra