
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 GaussJacobi over GaussSeidel 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