Accession Number : ADA195152

Title :   Reducing the Parallel Solution Time of Sparse Circuit Matrices Using Reordered Gaussian Elimination and Relaxation,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE MICROSYSTEMS RESEARCH CENTER

Personal Author(s) : Smart, David ; White, Jacob

PDF Url : ADA195152

Report Date : Mar 1988

Pagination or Media Count : 14

Abstract : Using parallel processors to reduce the execution times of classical circuit simulation programs like SPICE and ASTAP has been the focus of much current research. In these efforts, good parallel speed increases have been achieved for linearized system construction, but it has been difficult to get good parallel speed increases for sparse matrix solution. In this paper we examine two approaches for reducing parallel sparse matrix solution time; the first based on pivot ordering algorithms for Gaussian elimination, and the second based on relaxation algorithms. In the section on Gaussian elimination sparse matrix solution, we present a pivot ordering algorithm which increases the parallelism of Gaussian elimination compared to the commonly used Markowitz method. The performance of the new algorithm is compared to other suggested ordering algorithms for a collection of circuit examples. The minimum number of parallel steps for the solution of a tridiagonal matrix is derived, and it is shown that this optimum is nearly achieved by the ordering heuristics which attempt to maximize parallelism. In the section on relaxation, we present an optimality result about Gauss-Jacobi over Gauss-Seidel relaxation on parallel processors.

Descriptors :   *ALGORITHMS, *CIRCUITS, *SOLUTIONS(GENERAL), *SPARSE MATRIX, CONSTRUCTION, LINEARITY, PARALLEL ORIENTATION, PARALLEL PROCESSING, PARALLEL PROCESSORS, RELAXATION, SIMULATION, TIME, VELOCITY

Subject Categories : Electrical and Electronic Equipment
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE