Accession Number : ADA211570

Title :   Multiprocessor Sparse L/U Decomposition with Controlled Fill-In.

Descriptive Note : Final rept. 1 Jun 85-31 Aug 87,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Alaghband, Gita ; Jordan, Harry F

PDF Url : ADA211570

Report Date : Oct 1985

Pagination or Media Count : 40

Abstract : During L/U decomposition of a sparse matrix, it is possible to perform computation on many diagonal elements simultaneously. Pivots that can be processed in parallel are related by a compatibility relation and are grouped in a compatible set. The collection of all maximal compatibles yields different maximum sized sets of pivots that can be processed in parallel. Generation of the maximal compatibles is based on the information obtained from an incompatible table. This table provides information about pairs of incompatibles pivots. In this paper, generation of the maximal compatibles of pivot elements for a class of small sparse matrices is studied first. The algorithm involve a binary tree search and has a complexity exponential in the order of the matrix. Different strategies for selection of a set of compatible pivots based on the Markowitz criterion are investigated. The competing issues of parallelism and fill-in generation are studied and results are provided. A technique for obtaining an ordered compatible set directly from the ordered incompatible table is given. This technique generates a set of compatible pivots with the property of generating few fills. A new hueristic algorithm is then proposed that combines the idea of an ordered compatible set with a limited binary tree search to generate several sets of compatible pivots in linear time. Finally, an elimination set to reduce the matrix is selected. (KR)

Descriptors :   *PARALLEL PROCESSING, *COMPUTATIONS, *SPARSE MATRIX, ALGORITHMS, ELIMINATION, PIVOTS, SEARCHING, TIME, TREES

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE